3

約 600 万の一意の配列を生成する C 関数があります。これらの配列には常にそれぞれ 17 の要素があり、各要素は 0 から 16 までの整数です。また、同じ種類の約 600 万の一意の配列を生成する、その関数のわずかに変更されたバージョンもあります。私の問題は、2 番目の結果が最初の結果よりも約 45,000 少ないことです。これらの結果がどのようなものかを確認したいと思います。

したがって、私のアプローチは、2番目の関数のすべての結果を単純に保存し（電卓は、メモリ内に保持するのに十分な400 mbを超えてはならないことを示しています）、最初の結果を調べて、存在しません。

一般的なアプローチが理にかなっていると仮定すると（そうでない場合は教えてください）、私が探しているのは、約600万の一意の順列を保持できる適切なデータ構造です（理想的にはCで適切に実装されています）

[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

(またはその何らかの変換) を実行し、それらに対して高速メンバーシップ テストを実行します。タイトルが示すように、私はどのデータ構造が機能するかについていくつかの疑いを持っていますが、試行またはハッシュマップがこれに最適な選択であるとは確信していません.

これは、別のアルゴリズムの欠陥を検出するためのアルゴリズムであり、本番環境で使用されるものではありません。私はこれをコード化して人間の言葉で比較的迅速に結果を返す方法でこれを行うことに興味があります.

4

6 に答える 6

5

最適性は、順列がどのように分散されているか、および検索に対する挿入の比率に依存します。あなたは最適性に関心がないので、結果を一晩待つことなく仮説をテストする簡単な方法が欲しいだけです、私の腸は言います：

整数[0,16]は5ビットの数値として表すことができるため、そのうちの17個は85ビット（11バイト）の2進文字列として表すことができます。したがって、メンバーシップテストを含む文字列のソート/ハッシュセットを格納するために使用できる多くのライブラリの1つを使用するだけで、実行できます。調整されたトライほど高速でもキャッシュコヒーレントでもありませんが、数秒で66 MBのデータを処理するのに十分であり、昼食までに完了します。

そのようなライブラリが手元になく、最初から作業する必要がある場合は、文字列のソートされたリストを作成してから、バイナリ検索を介してメンバーシップテストを実行します。これは、O（n log n + m（n log n））= O（2× mn log n）のようなものになります。たとえば、m→nとしての2次時間です。これが本番環境でオフラインジョブとして1回または2回だけ実行されている場合は、それで十分かもしれません。これを1日に2回以上行う場合は、キャッシュの局所性について心配し、トライまたはBツリーを使用します。

于 2011-06-19T07:03:45.747 に答える
3

コミュニケーションを避けるために、Cでこれを行う価値を比較検討する必要があると思います。

C の各配列を、スペースで区切られた整数として行ごとに出力します。次に、それをファイルからロードして、次のような一連のバイト配列を作成します (F# コード):

let load file =
  System.IO.File.ReadAllLines file
  |> Array.Parallel.map (fun s -> s.Split[|' '|] |> Array.map (int >> byte))
  |> set

次に、次のように 2 つのファイル間の差集合を計算します。

load "file1.txt" - load "file2.txt"

実行にはおそらく数分かかります。

于 2012-07-18T09:36:58.053 に答える
2

シンプルに保つ：

  • 各順列を 17 バイトの配列として表す
  • 小さいセット全体を上記の配列として保存します (17*6M < 98MB)
  • 辞書順に並べ替えて、qsort呼び出しだけのコンパレーターmemcmp(left, right, 17)
  • より大きなセットの各要素について、バイナリ チョップを使用して並べ替えられた配列で検索します (以前と同じコンパレータを使用します。今回は を使用しますbsearch)。

最後の 2 つのステップはそれぞれ、6M * log(6M) のオーダーの比較を実行します。これは約 138M です。これはおそらく、コードを記述するのにかかる時間よりも短い時間です。すべてがとてもシンプルなので、長くはありません:-)

于 2011-06-19T10:31:49.933 に答える
1

@Steve Jessop検索対象の配列の不要な値を削除することで、よりスマートな検索を行い、線形時間で最後のステップを実行できます。

n を A のサイズ、m を B のサイズとすると、

int counter_A = 0;
int counter_B = 0;
int counter_C = 0;
while(counter_A != n){
    int temp = A[counter_A];
    counter_A++;
    //Removes all elements at the beginning of B since they are inferior than all
    //elements in A because they are inferior than the minimum of A
    for(;counter_B < m && B[counter_B] < temp;counter_B++);
    if((counter_B < m && B[counter_B] > temp) || counter_B == m){
        C[counter_C] = temp;
        counter_C++;
    }
}

アルゴリズムのすべてのステップで少なくとも 1 つのカウンターのインクリメントが実行されるため、これは O(n+m) 時間で実行されます。

于 2011-08-02T03:54:54.900 に答える
1

あなたのケースのどちらがより良いメモリパフォーマンスを得るかによって異なります。また、使用するハッシュ関数、衝突をどのように解決するかなど。Hash Array Mapped Trie (HAMT)をチェックしてみてはいかがでしょうか

于 2011-06-19T06:51:42.137 に答える
0

a) 2 つの 64 ビット int を含む構造体を作成する

b) 各結果には 17 の要素があるため、最初の 8 を乗算して結果を最初の int に入れ、他の 7 を乗算して結果を 2 番目の int に入れます。

c）構造体の演算子 < を作成します

d）構造体のセットを作成し、最初の実行からのすべての結果を挿入します

e) 2 回目の実行結果を反復し、set::find() を実行します

class Result
{
public:
    Result(int arr[17]);              // Fill-in _n1 and _n2

    bool operator < (const Result& r) const  // Compare
    { 
        if (_n1 != r._n1)
           return _n1 < r._n1;
        return _n2 < r._n2;
    }

protected:
    int _n1;
    int _n2;
};

typedef std::set< Result > SetResult;
SetResult setResult;

エドウィン

于 2013-05-23T18:24:11.000 に答える