4

動的に増加するリスト (C++ ベクトル、Java ArrayList、C# リストなどの連続したメモリ) で動作するアルゴリズムがあります。最近まで、これらのアルゴリズムはリストの途中に新しい値を挿入していました。もちろん、これは通常、非常に遅い操作でした。アイテムが追加されるたびに、それ以降のすべてのアイテムをより高いインデックスにシフトする必要がありました。これをアルゴリズムごとに数回行うと、処理が非常に遅くなります。

新しいアイテムをリストの最後に追加し、後で位置を変えることができることに気づきました。それは一つの選択肢です！

後ろからアイテムを回転させる

もう 1 つのオプションは、追加するアイテムの数が事前にわかっている場合、その数のアイテムを後ろに追加し、既存のアイテムをシフトしてから、自分で作成した穴の中でアルゴリズムをインプレースで実行することです。欠点は、リストの最後にデフォルト値を追加してから上書きする必要があることです。

穴をあける

これらのオプションを簡単に分析した結果、2 番目のオプションの方が効率的であるという結論に達しました。私の推論は、最初のオプションを使用したローテーションではインプレース スワップが発生するというものでした (一時的なスワップが必要です)。2 番目のオプションに関する私の唯一の懸念は、捨てられるだけのデフォルト値を大量に作成していることです。ほとんどの場合、これらの既定値は null または mem で満たされた値の型になります。

ただし、アルゴリズムに精通している他の人に、どのアプローチがより高速になるか教えてもらいたいと思います。あるいは、私が考えていなかったさらに効率的な解決策があるかもしれません。

4

3 に答える 3

2

配列は、配列の終わり以外の場所への大量の挿入または削除には効率的ではありません。別のデータ構造（他の回答の1つで提案されているものなど）を使用する方が効率的かどうかを検討してください。解決しようとしている問題を知らなければ、データ構造を提案することはほぼ不可能です（すべての問題に対する1つの解決策はありません）。そうは言っても...

2番目のオプションは間違いなく2つのより良いオプションです。やや優れたオプション（デフォルト値の問題を回避）：最後までコピーし、中央を。789で上書きするだけです。したがって、唯一の中間ステップはです。7894560123789789

ただし、デフォルト値の懸念は（一般的に）大きな問題ではありません。

  • たとえば、Javaでは、（私の知る限り）0またはnullで埋められていない配列にメモリを割り当てることさえできません。C ++ STLコンテナもこれを強制します（C ++自体は強制しません）。

  • 中程度のサイズのクラスと比較したポインタのサイズは最小限です（したがって、デフォルト値に割り当てるのにかかる時間も最小限です）（JavaおよびC＃ではすべてがポインタですが、C ++ではポインタ（boost::shared_ptrまたはポインタベクトルなど）を使用できますストレートポインタよりも優先されます）（開始するのが小さいプリミティブにはN / Aなので、一般的にはそれほど大きな問題ではありません）。

また、配列の最後に挿入を開始する前に、指定されたサイズに再割り当てを強制することをお勧めします（JavaArrayList::ensureCapacityまたはC ++ vector::reserve）。あなたが知らなかった場合-可変長配列の実装は、size()（値を挿入または削除するときにメモリが常に再割り当てされるのを防ぐために）返されるものやアクセス可能なものよりも大きい内部配列を持つ傾向があります。

また、forループ（Javaなど）を使用して手動で行うよりも、配列の一部をコピーする方が効率的な方法があることに注意してくださいSystem.arraycopy。

于 2013-01-12T12:58:03.440 に答える
1

リストの表現を動的配列の使用から他の構造の使用に変更することを検討することをお勧めします。これらの操作を効率的に実装できるようにする 2 つのオプションを次に示します。

  1. 順序統計ツリーは、O(log n) 時間での挿入と選択、および O(log n) 時間でのルックアップをサポートする、修正されたタイプのバイナリ ツリーです。これにより、ポインターのオーバーヘッドと追加の簿記のためにメモリ使用量がかなり増加しますが、挿入は劇的に高速化されます。ただし、ルックアップが少し遅くなります。

  2. 挿入ポイントが常に事前にわかっている場合は、配列ではなくリンク リストに切り替え、挿入が行われるリンク リスト セルへのポインターを保持することを検討できます。ただし、これにより O(n) へのランダム アクセスが遅くなり、セットアップで問題になる可能性があります。

  3. または、挿入がどこで行われるかを常に知っている場合は、配列を 2 つのスタックとして表すことを検討できます。1 つのスタックは挿入ポイントの左側に配列の内容を保持し、もう 1 つは挿入ポイントの右側に要素の (反転) を保持します。挿入ポイント。これにより挿​​入が高速になり、適切なタイプのスタック実装があれば、ランダムアクセスを高速に保つことができます。

お役に立てれば！

于 2012-12-26T19:53:06.353 に答える
0

HashMapsとリンクリストは、あなたが抱えている問題のために設計されました。番号付きのアイテムを含むインデックス付きのデータ構造を考えると、中央にアイテムを挿入するのが難しい場合は、リスト内のすべてのアイテムの番号を付け直す必要があります。

O(1)挿入を一定の複雑さにするために最適化されたデータ構造が必要です。HashMapsは、データセットのサイズに関係なく、挿入および削除操作を非常に高速にするように設計されています。

私はそれを説明することによってHashMapサブジェクトジャスティスを行うふりをすることはできません。ここに良いイントロがあります：http：//en.wikipedia.org/wiki/Hash_table

于 2012-12-26T19:31:17.850 に答える