2

コレクションの最後に文字列を追加し、最初に文字列を削除するアルゴリズムを実装しています。まれに、最後にプッシュするためにランダム アクセスの削除を実行します。私は主に C++ の開発者ですが、Java の重要なループで何を使用すればよいかわかりません。Java リストがこのタスクに適しているとは思えません。確かにうまくいきますが、私はすでにパフォーマンスの問題に苦しんでいます。

リンクリスト？ベクター？提案？

4

6 に答える 6

4

を使用することをお勧めします 、これはおよびインターフェイスArrayDequeを実装しますが、実装しません(おそらく必要ないでしょう):QueueDequeList

インターフェイスのサイズ変更可能な配列の実装Deque。配列両端キューには容量制限がありません。使用をサポートするために必要に応じて拡張されます。それらはスレッドセーフではありません。外部同期がない場合、複数のスレッドによる同時アクセスはサポートされません。null 要素は禁止されています。このクラスはStack、スタックとして使用する場合よりも高速でありLinkedList 、キューとして使用する場合よりも高速である可能性があります。

削除についても言及しました：

このインターフェイスは、内部要素を削除する 2 つのメソッドを提供し removeFirstOccurrenceますremoveLastOccurrence。

ArrayDeque必要なすべてのメソッドを提供します - addFirst(E e), addLast(E e), removeFirst().

の詳細については、この質問も参照してくださいArrayDeque。

PSそして、ここに上記のリンクからのいくつかのコレクションベンチマークArrayDequeがLinkedListありArrayList、他の人が言及しています;）

于 2012-08-30T18:00:29.190 に答える
1

個々の操作のすべてを にする必要がない限り、ArrayList で Vector を使用しても意味がありsynchronizedません。

頭と尾の挿入/削除のみを行う場合は、LinkedList が最も理にかなっています。ただし、リストが大きく、ランダムアクセス検索を行う必要がある場合、リストをトラバースする必要があるのは大きな苦痛になる可能性があります。

一方、ArrayList は非常に安価なランダム アクセスを提供しますが、リストの先頭から要素を挿入または削除するには、バッキング配列の残りを移動する必要があります。JDK 実装は、System.arraycopy()非常に安価に実行できる を呼び出すことによってこれを行います。

このような場合の最善の方法は、両方の実装を使用してベンチマークを行い、結果を比較することです。問題のアルゴリズムを a だけを使用するように記述すれば、ベンチマークのListさまざまな実装を簡単に交換できます。List

頭/尾の削除/挿入を自分でコーディングし、サイズが容量を超えたときに配列のサイズ変更に対処する必要があるため、ArrayList で通常の配列を使用する目的が何であるかわかりません。 ArrayList はすでにあなたのために行っています。

于 2012-08-30T17:56:08.957 に答える
1

Queue (LIFO) を実装しようとしているようです。 http://docs.oracle.com/javase/6/docs/api/java/util/Queue.html。ソース コードとその実装方法を確認して、より多くのアイデアを得ることができます。

于 2012-08-30T17:51:27.723 に答える
1

キューが必要なようですね。Queueインターフェイスをチェックしてください。

Queue<String> strQueue = new LinkedList<String>();
strQueue.offer("Hello");
strQueue.offer("World");
System.out.println(strQueue.poll());
System.out.println(strQueue.poll());

版画:

Hello
World
于 2012-08-30T17:52:40.170 に答える
1

java.util.ArrayDeque循環バッファーを使用したキュー操作をサポートします。これはおそらく最後に追加し、最初に削除するための最も効率的なアプローチですが、インデックスによるランダムアクセスはサポートしていません-インデックスn以外のエントリを削除することはできませんイテレータをトラバースします。特定の値の最初/最後の出現を削除する方法がありますが、これらは内部的に線形検索を行います。

于 2012-08-30T18:00:04.557 に答える
1

Javaリストの意味がわかりません。あなたが説明する問題は、LinkedList の典型的なケースのように聞こえます。ドキュメントには、「すべての操作が双方向リンク リストで期待されるとおりに実行される」と明記されています。これは、最初からオブジェクトを削除するだけでなく、最後にオブジェクトを挿入することも O(1) で行われることを意味します。つまり、リストに要素がいくつあっても同じ時間がかかります。ただし、ランダム アクセスはより難しく、O(N) で実行する必要があります。つまり、時間はリスト内の実際の要素数に比例します。

もちろん、持っている要素の数によっては、O(1) のリンク リストでは最適な時間が得られない場合があります。たとえば、リストにいくつかの要素しかないと予想する場合、O(N) の追加/削除時間を持つデータ構造が、より高速なアクセサーのほうが実際にはパフォーマンスが向上する可能性があります。しかし、より大きな構造の場合は、おそらく LinkedList クラスが出発点となります。

于 2012-08-30T18:03:32.820 に答える