3

このJavaコードの使用：

    // create the items list
    List<Item> items = new ArrayList<Item>();
    // ... (add some elements into the list so that it is not empty)

    // iterating ArrayList<Item> from right to left we find the position
    // based on the `if` condition satisfied for an item property
    int pos = 0;
    for (int j = items.size() - 1; j >= 0; j--) {
        Item item = items.get(j);
        if (item.property <= 7) {
            pos = j + 1; break;
        }
    }

    // add new item on the found above position
    Item it = new Item();
    if (pos == items.size()) {
        items.add(it);
    } else {
        items.add(pos, it);
    }

使用されているため、このステートメントItem item = items.get(j);の実行に余分な時間がかかるかどうか疑問に思ってArrayListいます。たとえば、新しいアイテムを最後に追加する必要があると想像してください。次にget()、アイテムリストを呼び出すことにより、左からのみ反復します。これは冗長です。Dequeの代わりに構造体を使用することを期待しますArrayList。

目標は右側から左側に繰り返すことですが、最初に新しい要素を追加することもできるので、私が間違っているかもしれませんが、何をお勧めしますか。

4

3 に答える 3

9

Getin ArrayList は一定時間で実行されます。証明: javadoc .

size、isEmpty、get、set、iterator、および listIterator 操作は一定時間で実行されます。

getですから、パフォーマンスについて心配する必要はありません。はArrayList連結リストではありません。プレーンなJava配列でバックアップされていると思います。

于 2012-07-22T09:59:04.883 に答える
1

の場合、（右）端ArrayListの操作、反復、および追加/削除は安価です（基本的にO（1）または償却されたO（1））。get(i)ただし、反対側 (左) の端で要素を追加/削除すると、非常にコストがかかり、バッキング配列全体を毎回コピーする必要があります。

したがって、両端で追加および削除する必要がある場合は、必ずArrayDeque. これは基本的に for all 操作と同じくらい安価ですArrayListが、安価な方法で両端での追加をサポートします。

リストの最後ではなく最初にのみ追加/削除したい場合でも、 を使用してArrayList、それを「逆方向に」使用できることに注意してください (したがって、最初に何かを追加したい場合は、次の場所に追加するだけです)。右から左に反復したい場合は、実際には左から右に反復します)。

メソッドを使用した要素の挿入add(Object, int)は、両方のデータ構造で O(n) です (挿入された要素の右側にあるすべての要素を配列内で移動する必要があります)。

代わりに使用することもできますLinkedList（これは も実装していますDeque）。get(int)これは O(n) であるため、インデックスを int として渡す他のメソッドを使用しないようにする必要があります。ただし、追加/削除/挿入操作は、リスト内のすべての位置で O(1) です (その位置を指す反復子が既にある場合)。したがって、コード内のループについては.listIterator()、リストを呼び出し、適切に反復し、ListIterator.add(Object)メソッドを使用して要素を挿入します。これは、コード全体にとって最も安価なソリューションです。

編集

ArrayDeque要素を途中に挿入する方法が提供されていないことに気づきませんでした（ただし、のように可能ですArrayList）。(Thanks AH) したがって、これらすべての操作 (先頭、中間、末尾への挿入) が本当に必要な場合は、 and を使用LinkedListしListIteratorます。

于 2012-07-22T10:15:17.683 に答える
0

いいえ、おそらくそうではありません。おそらく最速の実装であれば、forループを右から左に繰り返します。

LinkedListを使用している場合、答えは「はい」になります。LinkedListの.get（i）は遅いため、listIterator（）を使用して逆方向に反復する必要があります。ArrayListにはlistIterator（）もありますが、それを使用することと、逆方向に反復する単純なforループとの間におそらくほとんど違いはありません。

すべてのミリ秒について本当に心配している場合は、この質問について人々が言うすべてのことと、インターネットで読んだベンチマークをほんの少しの塩で取り、多くの負荷テストを実行し、VisualVMで多くのプロファイリングを行って、実際のパフォーマンスがどこにあるかを通知する必要がありますシステムのボトルネックは次のとおりです。

于 2012-07-22T10:41:49.860 に答える