9

私はJavaソリューションを探していますが、一般的な答えもOKです。

Vector / ArrayListは、追加と取得の場合はO（1）ですが、追加の場合はO（n）です。

LinkedList（Javaでは二重リンクリストとして実装）は、追加と追加の場合はO（1）ですが、取得の場合はO（n）です。

Deque（ArrayDeque）は、上記のすべてに対してO（1）ですが、任意のインデックスの要素を取得することはできません。

私の考えでは、上記の要件を満たすデータ構造には、2つの拡張可能なリスト（1つは追加用、もう1つは追加用）があり、取得時に要素を取得する場所を決定するためのオフセットも格納されます。

4

6 に答える 6

9

両端キューを探しています。これは、C ++ STLで希望する方法で実装されます。つまり、インデックスを作成できますが、Javaでは実装できません。2つの配列を使用し、「ゼロ」がどこにあるかを格納することで、標準コンポーネントから独自の配列を作成できると考えられます。これは、ゼロから長い距離を移動することになった場合にメモリを浪費する可能性がありますが、行き過ぎた場合は、リベースしてdequeを新しい配列にクロールさせることができます。

2つの配列を管理するのにそれほど凝ったことを必要としない、より洗練されたソリューションは、事前に割り当てられた配列に循環配列を課すことです。これには、push_front、push_back、およびその背後にある配列のサイズ変更を実装する必要がありますが、サイズ変更などの条件ははるかにクリーンになります。

于 2009-06-12T04:15:15.410 に答える
5

すべての実装が提供するわけではありませんが、これらすべての操作をO（1）時間で提供するために、 deque（両端キュー）を実装できます。私はJavaのArrayDequeを使用したことがないので、ランダムアクセスをサポートしていないことについて冗談を言っていると思いましたが、あなたは絶対に正しいです。理由はわかりますが、それは確かに迷惑です...

私にとって、非常に高速な両端キューを実装する理想的な方法は、循環バッファーを使用することです。特に、前面と背面に削除を追加することにのみ関心があるためです。私はJavaで1つをすぐに認識していませんが、オープンソースフレームワークの一部としてObjective-Cで1つ作成しました。コードをそのまま使用することも、独自のコードを実装するためのパターンとして使用することもできます。

これは、コードと関連ドキュメントへのWebSVNポータルです。本物の肉はCHAbstractCircularBufferCollection.mファイルにあります—とメソッドを探してください。カスタム列挙子（Javaでは「イテレータ」）も定義されています。本質的な循環バッファロジックはかなり些細なものであり、次の3つの集中型マクロに取り込まれます。appendObject:prependObject:#define

#define transformIndex(index) ((headIndex + index) % arrayCapacity)
#define incrementIndex(index) (index = (index + 1) % arrayCapacity)
#define decrementIndex(index) (index = ((index) ? index : arrayCapacity) - 1)

メソッドでわかるようobjectAtIndex:に、両端キューのN番目の要素にアクセスするために行うことはすべてですarray[transformIndex(N)]。tailIndex最後に保存された要素の1つ先のスロットを常に指すようにすることに注意してください。したがって、の場合headIndex == tailIndex、配列はいっぱいになり、サイズが0の場合は空になります。

お役に立てば幸いです。Java以外のコードを投稿してしまったことをお詫びしますが、質問の作者は一般的な回答は受け入れられると言っていました。

于 2009-06-12T05:25:55.553 に答える
3

Vector / ArrayListへの追加をO（1）として扱う場合-実際にはそうではありませんが、実際には十分に近い可能性があります-
（編集-明確にするために-追加は一定時間で償却される可能性があります-平均して-加算はO（1）になりますが、スパイクではかなり悪化する可能性があります。コンテキストと関連する正確な定数によっては、この動作は致命的となる可能性があります）。

（これはJavaではありませんが、いくつかの作り上げられた言語です...）。

「転送」と呼ばれる1つのベクトル。「後方」と呼ばれる2番目のベクトル。

追加を求められたとき- Forward.Append()。

付加するように求められたとき- Backwards.Append()。

問い合わせを求められたとき-

if ( Index < Backwards.Size() )
{
    return Backwards[ Backwards.Size() - Index - 1 ]
}
else
{
    return Forward[ Index - Backwards.Size() ]
}

（また、インデックスが範囲外であることを確認します）。

于 2009-06-12T04:24:39.380 に答える
2

あなたのアイデアはうまくいくかもしれません。これらがサポートする必要のある唯一の操作である場合、必要なのは2つのベクターだけです（ヘッドとテールと呼びます）。付加するには、頭に付加し、付加するには、尾に付加します。要素にアクセスするには、インデックスがhead.Lengthより小さい場合は、head [head.Length-1-index]を返します。それ以外の場合は、tail[index-head.Length]を返します。これらの操作はすべて明らかにO（1）です。

于 2009-06-12T04:14:27.860 に答える
1

これは、O（1）の追加、追加、最初、最後、およびサイズをサポートするデータ構造です。やAbstractList<A>などから他のメソッドを簡単に追加できますdeleteupdate

import java.util.ArrayList;

public class FastAppendArrayList<A> {
    private ArrayList<A> appends = new ArrayList<A>();
    private ArrayList<A> prepends = new ArrayList<A>();

    public void append(A element) {
        appends.add(element);
    }

    public void prepend(A element) {
        prepends.add(element);
    }

    public A get(int index) {
        int i = prepends.size() - index;
        return i >= 0 ? prepends.get(i) : appends.get(index + prepends.size());
    }

    public int size() {
        return prepends.size() + appends.size();
    }

    public A first() {
        return prepends.isEmpty() ? appends.get(0) : prepends.get(prepends.size());
    }

    public A last() {
        return appends.isEmpty() ? prepends.get(0) : appends.get(prepends.size());
    }
于 2016-02-05T19:11:18.797 に答える
0

Javaには何らかの理由がないため、必要dequeなのはSTLのような両端キュー（ ）です。ここにいくつかの良い提案と実装へのリンクがありました：ArrayDequeget()

于 2009-06-12T04:30:41.987 に答える