26

私が取り組んでいるプロジェクトの一環として、重複した行エントリを生成したファイルをクリーンアップしたいと考えています。ただし、これらの重複は、多くの場合、互いに近くには発生しません。私はJavaでこれを行う方法を思いつきました（基本的にファイルのコピーを作成し、ネストされたwhileステートメントを使用して、1つのファイルの各行を他のファイルと比較しました）。問題は、生成されたファイルがかなり大きく、テキストが重い (約 225k 行のテキスト、約 40 MB) ことです。現在のプロセスには 63 時間かかると見積もっています。これは絶対に受け入れられません。

ただし、これには統合ソリューションが必要です。できればJavaで。何か案は？ありがとう！

4

15 に答える 15

39

うーん... 40 MB は十分に小さくSet、行を作成してからすべてを印刷し直すことができます。これは、O(n 2 ) I/O 作業を行うよりもはるかに高速です。

次のようになります (例外は無視します)。

public void stripDuplicatesFromFile(String filename) {
    BufferedReader reader = new BufferedReader(new FileReader(filename));
    Set<String> lines = new HashSet<String>(10000); // maybe should be bigger
    String line;
    while ((line = reader.readLine()) != null) {
        lines.add(line);
    }
    reader.close();
    BufferedWriter writer = new BufferedWriter(new FileWriter(filename));
    for (String unique : lines) {
        writer.write(unique);
        writer.newLine();
    }
    writer.close();
}

順序が重要な場合は、 a のLinkedHashSet代わりに a を使用できますHashSet。要素は参照によって格納されるため、追加のリンク リストのオーバーヘッドは、実際のデータ量と比較して重要ではありません。

編集:ワークショップ アレックスが指摘したように、一時ファイルを作成することを気にしない場合は、行を読みながら単純に印刷することができます。HashSetこれにより、 の代わりに単純な を使用できますLinkedHashSet。しかし、このような I/O バウンド操作の違いに気付くとは思いません。

于 2009-06-15T13:18:08.817 に答える
16

さて、ほとんどの答えは、ハッシュセットなどに行を追加してから、そのセットから再度移動する必要があるため、少しばかげて遅いです。疑似コードで最適なソリューションを示しましょう。

Create a hashset for just strings.
Open the input file.
Open the output file.
while not EOF(input)
  Read Line.
  If not(Line in hashSet)
    Add Line to hashset.
    Write Line to output.
  End If.
End While.
Free hashset.
Close input.
Close output.

皆さん、必要以上に難しくしないでください。:-) 並べ替えについても気にしないでください。その必要はありません。

于 2009-06-15T13:52:24.650 に答える
10

同様のアプローチ

public void stripDuplicatesFromFile(String filename) {
    IOUtils.writeLines(
        new LinkedHashSet<String>(IOUtils.readLines(new FileInputStream(filename)),
        "\n", new FileOutputStream(filename + ".uniq"));
}
于 2009-06-16T20:30:07.057 に答える
4

このようなもの、おそらく：

BufferedReader in = ...;
Set<String> lines = new LinkedHashSet();
for (String line; (line = in.readLine()) != null;)
    lines.add(line); // does nothing if duplicate is already added
PrintWriter out = ...;
for (String line : lines)
    out.println(line);

LinkedHashSet挿入順序を維持しますが、HashSet（ルックアップ/挿入の方がわずかに高速ですが）すべての行を並べ替えます。

于 2009-06-15T13:20:46.877 に答える
3

コレクション ライブラリの Set を使用して、ファイルを読み取るときに表示される一意の値を格納できます。

Set<String> uniqueStrings = new HashSet<String>();

// read your file, looping on newline, putting each line into variable 'thisLine'

    uniqueStrings.add(thisLine);

// finish read

for (String uniqueString:uniqueStrings) {
  // do your processing for each unique String
  // i.e. System.out.println(uniqueString);
}
于 2009-06-15T13:18:23.857 に答える
3

順序が問題にならない場合、最も簡単な方法はシェル スクリプトです。

<infile sort | uniq > outfile
于 2009-06-15T13:26:08.377 に答える
2
  • ファイルを読み込み、行番号と次の行を保存します：O（n）
  • アルファベット順に並べ替えます：O（n log n）
  • 重複を削除：O（n）
  • 元の行番号順に並べ替えます：O（n log n）
于 2009-06-15T13:23:35.810 に答える
2

すでに読んだ行を格納する単純な HashSet を試してください。次に、ファイルを反復処理します。重複に遭遇した場合、それらは単純に無視されます (Set にはすべての要素を 1 回しか含めることができないため)。

于 2009-06-15T13:19:18.863 に答える
1

ハッシュセットのアプローチは問題ありませんが、すべての文字列をメモリに保存する必要がないように調整できますが、ファイル内の場所への論理ポインタを使用して、必要な場合にのみ実際の値を読み取ることができます。

別の創造的なアプローチは、各行に行番号を追加し、すべての行を並べ替え、重複を削除し（番号である必要がある最後のトークンを無視して）、最後のトークンでファイルを再度並べ替えてストライピングすることです。出力で。

于 2009-06-15T13:21:39.713 に答える
0

UNIXシェルコマンドを使用できる場合は、次のようなことを行うことができます。

for(i = line 0 to end)
{
    sed 's/\$i//2g' ; deletes all repeats
}

これにより、ファイル全体が繰り返され、sed呼び出しごとに1回だけ一意のオカレンスが渡されます。このようにして、以前に行った一連の検索を実行していません。

于 2009-06-15T13:21:39.713 に答える
0

2つのスケーラブルなソリューションがあります。スケーラブルとは、手順が安定しているかどうかに応じて、メモリベースではなくディスクを意味します。安定とは、重複を削除した後の順序が同じであることを意味します。スケーラビリティが問題にならない場合は、同じ種類の方法でメモリを使用するだけです。

安定していないソリューションの場合は、最初にディスク上のファイルを並べ替えます。これは、ファイルを小さなファイルに分割し、メモリ内の小さなチャンクを並べ替えてから、並べ替えられた順序でファイルをマージすることによって行われます。ここで、マージは重複を無視します。

マージ自体は、各ファイルの現在の行のみを比較することにより、ほとんどメモリを使用せずに実行できます。これは、次の行がより大きくなることが保証されているためです。

安定したソリューションは少し注意が必要です。まず、以前と同じようにファイルをチャンクに並べ替えますが、各行に元の行番号を示します。次に、「マージ」中に結果を保存する必要はなく、削除する行番号だけを保存します。

次に、上記で保存した行番号を無視して、元のファイルを1行ずつコピーします。

于 2009-06-15T13:25:17.663 に答える
0

線がどの順番で来るか、そしていくつの重複が見られることを期待しているかは重要ですか？

そうでない場合、および多くの重複を期待している場合（つまり、書き込みよりも読み取りが多い場合）、共有リソースとしてハッシュセットを使用して、ハッシュセットソリューションを並列化することも検討します。

于 2009-06-15T13:45:28.253 に答える
0

この効率的なソリューションについて、次の 2 つの仮定を立てました。

  1. line に相当する Blob があるか、バイナリとして処理できます
  2. 各行の先頭へのオフセットまたはポインターを保存できます。

これらの仮定に基づく解決策は次のとおりです。 1. 行を読み取り、ハッシュマップの長さを key として保存します。キーで指定された長さを持つすべての行について、ハッシュマップのエントリとしてリストを保存します。このハッシュマップを構築するのは O(n) です。ハッシュマップ内の各行のオフセットをマッピングする際に、エントリ -1 をオフセットとして除いて、このキーの長さの行 (オフセット) のリスト内のすべての既存のエントリと行ブロブを比較します。重複が見つかった場合は、両方の行を削除してオフセットを保存します -リスト内のそれらの場所で 1 です。

したがって、複雑さとメモリ使用量を考慮してください。

ハッシュマップ メモリ、スペースの複雑さ = O(n) n は行数

時間の複雑さ - 重複はなく、各行の長さ = m を考慮してすべての行の長さが等しい場合、行数 = n を考慮すると、O(n) になります。blob を比較できると仮定しているので、 m は問題ではありません。それは最悪のケースでした。

ハッシュマップに必要な余分なスペースはほとんどありませんが、比較を節約する場合もあります。

さらに、サーバー側で mapreduce を使用して、セットを分割し、後で結果をマージできます。長さまたは行頭をマッパーキーとして使用します。

于 2015-05-16T00:00:01.230 に答える
0 
void deleteDuplicates(File filename) throws IOException{
    @SuppressWarnings("resource")
    BufferedReader reader = new BufferedReader(new FileReader(filename));
    Set<String> lines = new LinkedHashSet<String>();
    String line;
    String delims = " ";
    System.out.println("Read the duplicate contents now and writing to file");
    while((line=reader.readLine())!=null){
        line = line.trim(); 
        StringTokenizer str = new StringTokenizer(line, delims);
        while (str.hasMoreElements()) {
            line = (String) str.nextElement();
            lines.add(line);
            BufferedWriter writer = new BufferedWriter(new FileWriter(filename));
            for(String unique: lines){
                writer.write(unique+" ");               
            }
            writer.close();
        }
    }
    System.out.println(lines);
    System.out.println("Duplicate removal successful");
}
于 2015-09-02T19:00:52.850 に答える