1

重複したオブジェクトを含む可能性のある配列があります。配列内の重複を見つけて削除できるかどうか疑問に思います:-並べ替えなし(厳密な要件)-一時的なセカンダリ配列を使用せずに-おそらくO(N)で、Nは配列内の要素のnbです

私の場合、配列はテーブルを含む Lua 配列です。

t={
{a,1},
 {a,2},
 {b,1},
 {b,3},
 {a,2}
}

私の場合、t[5] は t[2] の複製ですが、t[1] はそうではありません。

4

4 に答える 4

3

要約すると、次のオプションがあります。

  • 時間: O(n^2)、余分なメモリはありません - 配列内の各要素について、等しいものを直線的に探します
  • 時間: O(n*log n)、余分なメモリなし - 最初に並べ替え、その後線形に配列をウォークスルー
  • time: O(n), memory: O(n) - ルックアップ テーブルを使用します (編集: 私が覚えている限り、テーブルを他のテーブルのキーにすることはできないため、おそらくオプションではありません)

一つを選ぶ。余分なメモリがなければ、O(n) 時間でやりたいことを行う方法はありません。

于 2010-07-08T21:53:16.397 に答える
2

O(n)ではできませんが...

あなたにできることは

  • 配列を反復処理する
  • 繰り返しを検索するメンバーごとに、それらを削除します。

最悪のシナリオの複雑さは O(n^2)

于 2010-07-08T18:50:25.990 に答える
0

配列を繰り返し、すべての値をハッシュに貼り付け、最初に存在するかどうかを確認します。元の配列から削除する場合 (または新しい配列に書き込まない場合)。メモリ効率はあまり高くありませんが、配列を 1 回だけ反復しているため、0(n) のみです。

于 2010-07-08T18:44:45.050 に答える
0

はい、見方次第です。

オブジェクトの挿入をオーバーライドして、重複するアイテムの挿入を防ぐことができます。これは、オブジェクトの挿入ごとに O(n) であり、配列が小さいほど高速に感じる場合があります。

ソートされたオブジェクトの挿入と削除を提供する場合、それは O(log n) です。基本的に、要素の検索がバイナリ検索になるように、挿入および削除するときに常にリストをソートしたままにします。ここでのコストは、要素の取得が O(1) ではなく O(log n) になることです。

これは、赤黒ツリーやマルチツリーなどを使用して効率的に実装することもできますが、追加のメモリを犠牲にします。このような実装は、特定の問題に対していくつかの利点を提供します。たとえば、ネストされたツリーを使用することで、小さなメモリ フットプリントを持つ非常に大きなテーブルでも、O(log n) タイプの動作を行うことができます。最上位のツリーは、データセットの一対の概要を提供し、サブツリーは必要に応じてより洗練されたアクセスを提供します。

たとえば、これを確認するには、N 個の要素があるとします。それを n1 グループに分割できます。次に、これらのグループのそれぞれをさらに n2 個のグループに分割し、それらのグループを n2 個のグループに分割することができます。したがって、N/n1n2 の深さがあります...

ご覧のように、n の積は、n が小さい場合でも非常に急速に大きくなる可能性があります。N = 1 兆要素で、n1 = 1000、n2 = 1000、n3 = 1000 の場合、アクセス時間あたり 1000 + 1000 + 1000 + 1000 秒 = 4000 しかかかりません。また、ノードあたりのメモリ フットプリントは 10^9 回しかありません。

これを、直接線形検索に必要な平均 5000 億アクセス時間と比較してください。二分木よりも 1 億倍以上速く、メモリは 1000 分の 1 ですが、速度は約 100 分の 1 です。(もちろん、ツリーの一貫性を維持するためのオーバーヘッドはいくらかありますが、それでも削減できます)。

二分木を使用する場合、深さは約 40 になります。問題は、約 1 兆個のノードがあるため、大量のメモリが追加されることです。ノードごとに複数の値を格納することにより (上記の場合、各ノードは実際には値と他のツリーの部分的な値です)、メモリ フットプリントを大幅に削減できますが、それでも優れたパフォーマンスを維持できます。

基本的に線形アクセスは低い数値で優勢であり、ツリーの優勢は高い数値で優勢です。木。ツリーはより多くのメモリを消費します。マルチツリーを使用することで、少数の線形アクセスを使用し、ノードあたりの要素数を (バイナリ ツリーと比較して) 増やすことで、両方の長所を組み合わせることができます。

このようなツリーは簡単に作成できるものではありませんが、基本的には、標準のバイナリ ツリー、赤黒ツリー、AVL ツリーなどと同じアルゴリズムの性質に従います。

したがって、大規模なデータセットを扱っている場合、パフォーマンスとメモリの大きな問題にはなりません。基本的に、ご存じのとおり、一方が上がると他方が下がります。マルチツリーは、最適な媒体を見つけるようなものです。(ノードサイズを正しく選択したと仮定します)

マルチツリーの深さは N/product(n_k,k=1..m) です。メモリ フットプリントは、product(n_k,k=1..m) であるノードの数です (通常は 1 桁、または n_m の桁まで減らすことができます)。

于 2012-07-29T00:21:01.433 に答える