1

ArrayList と LinkedList の 2 つのデータ構造から選択する必要があります。op_one、op_two という 2 つの操作があります。

ArrayList を選択した場合 - 最終的には

for op_one ------ O(n), and at maximum n re-allocations
for op_two ------ O(1), and at maximum n re-allocations

LinkedListを選択した場合-最終的には

for op_one ------ O(n), and zero re-allocations
for op_two ------ O(n), and zero re-allocations

何百万もの同等の要素を保存します。そして、私は両方の操作を同じように行う予定です。どちらを選ぶべきですか。

4

3 に答える 3

3

それらを合わせて現実的な方法で時間を計って、どちらが速いかを確認することをお勧めします。それらに大きな違いがない場合は、最も単純であると思われるアプローチを使用します。

ArrayList と LinkedLIst の順序は空間的には同じですが、ArrayList ははるかに小さくなっています。

パフォーマンスの問題があることがわかっていない限り、通常はすべて同じ明快さが最も重要です。

于 2012-09-08T07:36:35.333 に答える
0

(スペースを無視した時間の複雑さとして最初に理解された質問。コメントで行われた説明の要求)

時間の複雑さだけでなく、より単純で、アイテムごとに新しいノードを構築しないため、(LinkedList よりも) ArrayList を使用します。

どちらの場合も、全体的な複雑さは O(n) になることに注意してください。の上）。

複雑さが等しい場合 ( O(n) )、実際の実行時間を調べるか、実装または保守が容易な方を選択する必要があります。

于 2012-09-08T07:33:01.267 に答える
0

最新のアーキテクチャでは、メモリ帯域幅がしばしばボトルネックになることを考慮してください。したがって、結果の計算は、事前に計算された値を保存して読み取るよりも高速な場合があります。つまり、計算の複雑さは、メモリの複雑さと一緒に考慮する必要があります。計算に費用がかからず、キャッシュ内で機能する場合は、メモリ使用量を小さく保ちます。

しかし、最終的には、テストする必要があります...

于 2012-09-08T12:25:44.473 に答える