0

2 つの大きな整数配列があります。これらの配列の違いを取得する必要があります（つまり、1番目の配列ではなく2番目の配列の要素、またはその逆）。線形検索を実装し、違いを配列に格納しています。より速くできる方法はありますか（線形時間）？

4

6 に答える 6

2

1 つの配列をハッシュ セットに入れ、別の配列を実行してハッシュ セットを調べれば、O(n+m) 時間は簡単に得られます。もちろん、配列がソートされていれば、直接 O(n+m) を持つことができます。

于 2012-07-23T21:09:07.820 に答える
0

あなたの過度のニーズに応じて、私はおそらく言うでしょう。リストを小さなセットに分割し、スレッドを使用して各セットを処理し、結果をまとめて集中プールに戻すことができます。

それほど難しくはありませんが、結果を正しい順序に整理し直し (スレッド 2 がスレッド 1 の前に終了する場合があるため)、プロセスを監視してプロセスがいつ完了したかを知るために、ある程度の管理が必要になります。

詳細については、Executors チュートリアルをご覧ください。

于 2012-07-23T21:11:06.760 に答える
0

派手なものは必要ありません。配列がソートされている場合、各配列を 1 回通過するだけで差分を取得できます。各配列にインデックスを保持するだけで、インデックスが等しい要素を指している場合は両方のインデックスをインクリメントし、そうでない場合は、戻り配列に下位の要素を追加してそのインデックスをインクリメントします。

Go でこれを行うコードを次に示します: http://play.golang.org/p/VZgGWmu-aO

このソリューションには O(n+m) 時間と O(n+m) スペースが必要であり、それ以上のことはできません。また、ハッシュ テーブルを含むソリューションのようなオーバーヘッドもありません。

于 2012-07-23T22:00:54.070 に答える
0

ハッシュは良いですが、セットのデータ構造はどうでしょうか?

stromberg@aw50 ~ $ /usr/local/pypy-1.9/bin/pypy
Python 2.7.2 (341e1e3821ff, Jun 07 2012, 15:38:48)
[PyPy 1.9.0 with GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
And now for something completely different: ``<arigato> the AI state is indeed
close''
>>>> s1 = set(range(10))
>>>> s2 = set(range(5,15))
>>>> s1
set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>>> s2
set([5, 6, 7, 8, 9, 10, 11, 12, 13, 14])
>>>> s1 - s2
set([0, 1, 2, 3, 4])
>>>> s2 - s1
set([10, 11, 12, 13, 14])
>>>> s1 & s2
set([8, 9, 5, 6, 7])
>>>> s1 | s2
set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14])
>>>>

これは便利な方法であり、同時にメモリに収まるリストの場合は高速だと思います。

オンディスク BTree やブルーム フィルターなどもあります。

BTree を使用すると、すべてをメモリに収める必要がなくなり、マージ ソートのマージ ステップと同様に差分を取得できます。それらは基本的に順序付けられたデータベース テーブルです。

ブルーム フィルターの場合、考慮する必要があるものの数を絞り込む必要がある場合に最適です。それらは確率論的であり、「これは間違いなくセットに含まれていない」や「これはほぼ確実にセットに含まれている」などの回答を与えることができます。ブルーム フィルターの主な利点は、必要なメモリが非常に少ないことです (要素ごとにわずか 1 ビットの場合もあります)。優れた実装では、最大許容エラー確率を指定できます。EG、*ix ハード リンクの検出は、ブルーム フィルターが非常に適しているセット メンバーシップの問題です。実際のファイルの数が膨大であっても、小さくする必要があります。

于 2012-07-23T21:42:32.857 に答える
0

2 つの配列がソートされていると仮定すると、2 つのスリンディング ポインターを使用して違いを見つけることができます。時間の計算量は O(n+m) で、スペースは O(max(n,m)) です。

    void set_difference(std::vector<int> & array1,std::vector<int> & array2,std::vector<int> & output ) 
{
    auto index1 =  0 ;
    auto index2 = 0 ;
    while (index1 != array1.size() & index2 != array2.size()) 
    {       //since the arrays are sorted, we can stop looking right when we find a number bigger
        while ((array1[index1] < array2[index2]) & index2 != array2.size() )  
            index2++ ;
        if (array1[index1] != array2[index2]) //array1[index1] is not array2
            output.push_back(array1[index1]);
        index1++ ;
    }
}
于 2012-07-23T23:29:46.253 に答える
0

これは、目標を達成するための率直な方法です。

public static Set<Integer> foundInFirstButNotSecond(int[] first,
        int[] second) {
    Set<Integer> secondSet = new HashSet<Integer>(second.length);
    for (Integer i :
            second) {
        secondSet.add(i);
    }
    Set<Integer> resultSet = new HashSet<Integer>(first.length);
    for (Integer j :
            first) {
        if (!secondSet.contains(j)) {
            // Current integer from first not found in second
            resultSet.add(j);
        }
    }
    return resultSet;
}

配列ではなく Set を返すことに注意してください。ただし、このコードを簡単に変更して、代わりに配列を生成することができます。

例として、このコードを呼び出す場合:

public static void main(String[] args) {
    int[] first = new int[]{1, 2, 3, 4, 5, 6};
    int[] second = new int[]{5, 6, 7, 8};
    System.out.println("In first but not second: " + ArrayCompare.
            foundInFirstButNotSecond(first, second));
}

内容が [1, 2, 3, 4] の Set が得られます。(HashSet は特定の順序を保証しないことに注意してください。したがって、これの無秩序なバリエーションを取得することもできます。)

于 2012-07-23T22:04:53.750 に答える