1

LinkedList はメモリ オーバーヘッドの点で悪夢であり、要素を反復するときにも遅いため、int poiter データ構造のようなものが必要です。

だから私はintのリストを持っていて、最初から真ん中に要素を挿入してそれを形成します。リストの準備ができたら、左から 1 つずつ繰り返します。それが私の問題の制約です。

4

4 に答える 4

2

Gaplistを試してください。多くのユース ケースで ArrayList のようなパフォーマンスとメモリ フットプリントを提供します。挿入がほとんどシーケンシャル (任意のインデックス) である場合、挿入は O(1) に近くなります。

于 2012-08-17T11:13:08.060 に答える
2

プロファイリングして、さまざまなデータ構造を試してみました。

そうは言っても、使用してみませんかArrayList; O(n)では、キャッシュ内の連続するデータの移動が非常に高速であるため、反復や挿入も高速です。(挿入中にリストを反転させると、さらに高速になります!)

ArrayList私の仲間のプログラマーは、この特定の問題に対して私が推奨する理由を理解していないため、更新します。

問題は要素の挿入ではありません。その場合、リンクされたリストが直接勝ちます (配列リストの O(n) に対して O(1))。問題は、それらを挿入する場所を見つけることです。この場合、LinkedListは非常に遅いです。「良い問題」でメモリを割り当てないため、挿入する場所を見つけるには大きなオーバーヘッドがあります。キャッシュミスが多い！

OP はコードを投稿していないため、OP が何を望んでいるかはわかりますが、2 つのケース ( C * は定数)のアルゴリズム分析を次に示します。

LinkedList、挿入する各要素に対して:

  • O(C1 * n)の繰り返し
  • O(1)の挿入

ArrayList、挿入する各要素に対して:

  • O(C2 * n)の繰り返し
  • O(C3 * n)の挿入

したがって、両方のアルゴリズムはO(n)にありますが、定数をよく見ると、C1は非常に大きいです (上記で説明)。一方、C2とC3は小さく、キャッシュ内での反復と移動が高速です。

したがって、十分なメモリがある場合は、ArrayList!

于 2012-08-17T10:56:04.950 に答える
2

LinkedListリストを何度もトラバースしないように、常に代わりにlist.get(index);
Use を使用すると、実際にひどいパフォーマンスが得られます。また、リストの途中に要素を追加する必要がある場合は、 (要素を移動する必要がないため) よりもはるかに優れたパフォーマンスが得られます。ListIterator
ArrayList O(1)

更新:
リストを反復処理する適切な方法は、反復子 (暗黙的または明示的) を使用することです。暗黙の反復子の使用例: 

for(E e:list){  
}

絶対にしないでください: 

for(int i = 0; list.size(); i++{  
    E e = list.get(i);  
}

リストが の場合、LinkedListこの操作は、ループの各反復で最初からリストをトラバースするのとO(N^2)同じです。 イテレータで最初のフォームを使用することは、イテレータがアクセスされた最後の要素を「記憶」し、そこから開始するという事実により、ほとんど同じです。list.get(i)
O(N)ArrayList

于 2012-08-17T10:59:14.200 に答える
0

最初のステップ: 要素を挿入するLinkedList

ArrayList2 番目のステップ:反復するために要素をコピーします。

ところで、「悪夢」は少し誇張されていLinkedListます:)

于 2012-08-17T11:00:57.667 に答える