5

文字列の（並べ替えられていない）配列から重複を削除するための最善の方法を検討しています-配列には数百万または数千万のstringzが含まれています..配列はすでに事前入力されているため、最適化の目標は重複を削除することだけであり、重複を防ぐことではありません最初の人口から！

私は、ソートを実行してからバイナリ検索を実行して、n（線形）検索の代わりにlog（n）検索を取得することを考えていました。これにより、nlogn + n検索が得られますが、ソートされていない（n ^ 2）検索=よりも優れていますが、それでも遅いようです。（ハッシュの方針に沿って検討していましたが、スループットについてはわかりませんでした）

助けてください！Collections APIを使用せずに何百万もの文字列が関係しているため、速度とメモリの両方に対応する効率的なソリューションを探しています。

4

7 に答える 7

7

あなたの最後の文まで、答えは私には明白に思えました：順序を維持する必要がある場合は aHashSet<String>または aを使用してください：LinkedHashSet<String>

HashSet<String> distinctStrings = new HashSet<String>(Arrays.asList(array));

コレクション API を使用できない場合は、独自のハッシュ セットを作成することを検討してください。ただし、コレクション API を使用したくない理由を説明するまでは、より具体的な答えを出すことは困難です。理由は、他の答えも除外する可能性があります。

于 2012-04-06T15:31:59.247 に答える
5

分析

いくつかの分析を実行しましょう。

  1. ハッシュセットの使用。時間計算量 - O(n)。空間複雑度 O(n)。約 8 * 配列サイズ バイト (8 ～ 16 バイト - 新しいオブジェクトへの参照) が必要であることに注意してください。

  2. クイックソート。時間 - O(n*log n)。スペース O(log n) (それぞれ最悪のケース O(n*n) と O(n))。

  3. マージソート (二分木/TreeSet)。時間 - O(n * log n)。スペース O(n)

  4. ヒープソート。時間 O(n * log n)。スペース O(1)。(ただし、2 および 3 よりも遅い)。

ヒープ ソートの場合、その場で重複を取り除くことができるため、ソート後に最終パスを保存します。

結論

  1. 時間が問題で、HashSet に 8 * array.length バイトを割り当ててもかまわない場合は、このソリューションが最適と思われます。

  2. スペースが問題になる場合は、QuickSort + 1 パスを使用します。

  3. スペースが大きな懸念事項である場合は、その場で重複を破棄してヒープを実装します。それはまだ O(n * log n) ですが、追加のスペースはありません。

于 2012-04-06T16:18:39.777 に答える
2

配列で変更されたマージソートを使用することをお勧めします。マージ ステップ内で、重複する値を削除するロジックを追加します。このソリューションは n*log(n) の複雑さであり、必要に応じてインプレースで実行できます (この場合、インプレース実装は通常のマージソートよりも少し難しくなります。これは、隣接する部分に削除された重複からのギャップが含まれる可能性があるためです。マージ時に閉じられます）。

マージソートの詳細については、http://en.wikipedia.org/wiki/Merge_sortを参照してください。

于 2012-04-06T15:42:28.970 に答える
1

このタスクを処理するハッシュセットを作成するのは、コストがかかりすぎます。実際、彼らがコレクション API を使用しないように言っているのは、ハッシュという言葉を聞きたくないからです。したがって、コードは次のとおりです。

配列をソートした後にバイナリ検索を提供したことに注意してください。これは意味がありません。提案が拒否された理由かもしれません。

オプション1：

public static void removeDuplicates(String[] input){
    Arrays.sort(input);//Use mergesort/quicksort here: n log n
    for(int i=1; i<input.length; i++){
        if(input[i-1] == input[i])
            input[i-1]=null;
    }       
}

オプション 2:

public static String[] removeDuplicates(String[] input){
    Arrays.sort(input);//Use mergesort here: n log n
    int size = 1;
    for(int i=1; i<input.length; i++){
        if(input[i-1] != input[i])
            size++;
    }
    System.out.println(size);
    String output[] = new String[size];
    output[0]=input[0];
    int n=1;
    for(int i=1;i<input.length;i++)
        if(input[i-1]!=input[i])
            output[n++]=input[i];
    //final step: either return output or copy output into input; 
    //here I just return output
    return output;
}

オプション 3: (オプション 1 に基づいて 949300 によって追加)。これは入力配列を台無しにすることに注意してください。それが受け入れられない場合は、コピーを作成する必要があります。 

public static String[] removeDuplicates(String[] input){
    Arrays.sort(input);//Use mergesort/quicksort here: n log n
    int outputLength = 0;
    for(int i=1; i<input.length; i++){
        // I think equals is safer, but are nulls allowed in the input???
        if(input[i-1].equals(input[i]))
            input[i-1]=null;
        else
           outputLength++;
    }  

    // check if there were zero duplicates
    if (outputLength == input.length)
       return input;

    String[] output = new String[outputLength];
    int idx = 0;
    for ( int i=1; i<input.length; i++) 
       if (input[i] != null)
          output[idx++] = input[i]; 

    return output;   
}
于 2012-04-06T23:13:09.600 に答える
0

こんにちは、それらを配列に入れる必要がありますか。セットのようなハッシュ値を使用したコレクションを使用する方が高速です。ここでは、ハッシュ値により、各値は一意です。

すべてのエントリをセット コレクション タイプに入れる場合。を使用できます。

 HashSet(int initialCapacity)

実行時のメモリ拡張を防ぐためのコンストラクタ。

  Set<T> mySet = new HashSet<T>(Arrays.asList(someArray))

メモリを拡張する必要がない場合、Arrays.asList() にはランタイム O(n) があります。

于 2012-04-06T15:34:37.717 に答える
0

これはインタビューの質問なので、set api を使用する代わりに、独自の実装を考え出すことを望んでいると思います。

最初に並べ替えて再度比較する代わりに、バイナリ ツリーを構築し、空の配列を作成して結果を格納できます。

配列の最初の要素がルートになります。

  1. 次の要素がノードと等しい場合は、戻ります。->これにより、重複する要素が削除されます

  2. 次の要素がノードより小さい場合は左と比較し、そうでない場合は右と比較します。

ツリーの最後に到達するまで、上記の 2 つの手順を繰り返します。その後、新しいノードを作成し、これにはまだ重複がないことがわかります。この新しいノード値を配列に挿入します。

元の配列のすべての要素をトラバースした後、元の順序で重複していない配列の新しいコピーを取得します。

トラバースには O(n) が必要で、バイナリ ツリーの検索には O(logn) が必要です (挿入には O(1) しかかからないはずです。これは、ツリーをアタッチするだけで、ツリーの再割り当てやバランス調整を行っていないためです)。したがって、合計は O(nlogn) になります。 .

于 2012-04-06T16:11:42.813 に答える
0

超高速が必要な場合は、可能な限り文字列のハッシュコードを使用しましょう。

  1. 配列をループして、各文字列のハッシュコードを取得し、お気に入りのデータ構造に追加します。Collection の使用は許可されていないため、BitSet を使用します。ポジティブ用とネガティブ用の 2 つが必要であり、それぞれが巨大になることに注意してください。

  2. 別の BitSet を使用して、配列を再度ループします。True は、文字列が通過することを意味します。文字列のハッシュコードがビットセットに存在しない場合は、それを true としてマークできます。それ以外の場合は、重複の可能性がある、false としてマークします。その間、可能な重複の数を数えます。

  3. 可能性のあるすべての重複を、possibleDuplicates という名前の大きな String[] に収集します。並べ替えます。

  4. 次に、元の配列で可能な重複を調べ、可能な重複でバイナリ検索を行います。存在する場合、まあ、あなたはまだ立ち往生しています。なぜなら、一度だけ含めたいのですが、それ以外の場合は含めたくないからです。したがって、どこかにさらに別の配列が必要です。ぐちゃぐちゃ、夕食を食べに行かないといけないけど、これが始まり…

于 2012-04-07T00:01:15.073 に答える