7

私は非常に多くのアイテムで機能する並べ替え/ランク付けアルゴリズムに取り組んでおり、それを機能させるために効率的な方法で次のアルゴリズムを実装する必要があります。

番号のリストは2つあります。それらは同じくらい長く、約10万から50万のアイテムです。これから、これらのリストの中でn番目に大きい製品を見つける必要があります。上部に1つのリストがあり、側面にもう1つのリストがあるマトリックスを作成すると、各セルは上の数値と側面の数値の積になります。

例：リストはとA=[1, 3, 4]ですB=[2, 2, 5]。次に、製品は[2, 2, 5, 6, 6, 15, 8, 8, 20]です。それから3番目に大きいものが必要な場合は8になります。

単純な解決策は、これらの数値を生成し、並べ替えてから、n番目に大きい数値を選択することです。しかし、O(m^2 * log m^2)ここでmは小さなリストの要素の数であり、それは十分に高速ではありません。

私が必要としているのは、最初に2つの小さなリストを並べ替えることだと思います。それはO(m * log m)です。それなら私は確かに最大のものがA[0]*B[0]であることを知っています。2番目に大きいのはA[0]*B[1]またはA[1]*B[0]のいずれかです...

O(f(n))これは、マトリックスのサイズに関係なく、段階的に実行できると思います。しかし、私はこの部分を行うための効率的な方法を理解することはできません。

編集：削除された回答がありました。これは、2つの並べ替えられたセットの位置を覚えてから、A [a] * B [b+1]とA[a+ 1] * B [b]を見て、大きい方とa/bをインクリメントします。削除される前にこのコメントを投稿するつもりでした：

これは機能しません。2つのリストA=B=[3,2,1]を想像してみてください。これにより、[9,6,3;のようなマトリックスが得られます。6,4,2; 3,2,1]。したがって、（0,0）= 9から開始し、（0,1）= 6に移動すると、（0,2）= 3または（1,1）=4が選択されます。ただし、これは両方よりも大きい（1,0）=6を見逃します。したがって、2つの隣人だけに目を向けることはできませんが、後戻りする必要があります。

4

3 に答える 3

4

でできると思いますO(n log n + n log m)。これが私のアルゴリズムのスケッチです。うまくいくと思います。少し荒いです。

  1. Aを降順に並べ替えます。(かかるO(m log m))
  2. Bを降順に並べ替えます。(かかるO(m log m))
  3. しましょsうmin(m, n)。(かかるO(1))
  4. を介してs遅延シーケンス反復子を作成します。 値、、 ...、を反復処理します。(かかる)L[0]L[s-1]L[i]sA[i]*B[0]A[i]*B[1]A[i]*B[s-1]O(s)
  5. イテレータを優先キューに入れますq。イテレータは、現在の値に従って優先順位が付けられます。（O(s)最初はすでに順番に並んでいるのでかかります）
  6. nから値を引き出しますq。最後にプルされた値が目的の結果になります。qイテレータがプルされると、次の値を新しい優先度として使用して再挿入されます。イテレータが使い果たされた場合は、再挿入しないでください。(かかるO(n log s))

全体として、このアルゴリズムは になりますがO(m log m + (s + n)log s)、または のいずれかsに等しくなります。mn

于 2012-05-17T15:24:39.227 に答える
0

m に依存しない O(f(n)) のアルゴリズムはないと思います。

しかし、比較的高速な O(n*logm) アルゴリズムがあります。

まず、2 つの配列を並べ替え、A[0] > A[1] > ... > A[m-1] および B[0] > B[1] > ... > B[m- 1]。(もちろん、これは O(mlogm) です。)

次に、要素が A[0]*B[0]、A[0]*B[1]、... A[0]*B[m-1] である最大ヒープを構築します。そして、「ポインタ配列」P[0]、P[1]、... P[m-1] を維持します。P[i]=x は、B[i]*A[x] が現在ヒープにあることを意味します。すべての P[i] は最初はゼロです。

各反復で、次の最大の積であるヒープから max 要素をポップします。それが B[i]*A[P[i]] から来ると仮定すると (B[i] から来るヒープ内の要素を記録できます)、対応するポインタを前方に移動します: P[i] += 1,新しい B[i] * A[P[i]] をヒープにプッシュします。(P[i] が範囲外 (>=m) に移動した場合、単純に -inf をヒープにプッシュします。)

n 回目の繰り返しの後、n 番目に大きい積が得られます。

n 回の繰り返しがあり、それぞれが O(logm) です。

編集：いくつかの詳細を追加

于 2012-05-17T15:08:36.197 に答える
0

上位 3 を取得するために 500 000 の要素を並べ替える必要はありません。

最初の 3 つを取り、それらを SortedList に入れ、リストを反復処理し、3 つの要素のうち最小のものを新しい値に置き換えて (値が大きい場合)、結果のリストを並べ替えます。

両方のリストに対してこれを行うと、3 番目の値を簡単に取得できる 3*3 マトリックスで終了します。

これは scala での実装です。

n が m よりも小さく、A=[1, 3, 4] および B=[2, 2, 5] であると仮定すると、n=2:

(3, 4) => 並べ替え (4,3)
次に (2,5) => 並べ替え (5, 2)

圧縮検索を実行できるようになりました。もちろん、現在の最大の積は (5, 4) です。しかし、次のものは (4*2) または (5*3) のいずれかです。より長いリストについては、4*2 の結果が何であったかを念頭に置いて、それを次の製品とのみ比較してください。そうすれば、1 つの製品だけを計算しすぎてしまいます。

于 2012-05-17T14:27:27.893 に答える