7

数十億の文字列行を調べて、それぞれが一意であるかどうかを確認するタスクがあります。すべての行自体を PC の RAM メモリ内に収めることはできません。また、行数が Integer.MAX_VALUE よりも多くなる可能性があります。

この量のデータを処理する最善の方法は、各文字列のハッシュ コードを何らかの HashTable に入れることだと思います。

だから、ここに私の質問があります：

  1. の代わりに何を使用すればよいString.hashCode()ですか? (戻り値はintですが、おそらくlongが必要です)
  2. このサイズのリストを操作するための最速の方法/フレームワークは何ですか? 私が最も必要としているのは、リストに要素が含まれているかどうかをすばやく確認する機能です
4

2 に答える 2

4

あなたは問題を考えすぎています、これはすべてをメモリに保持する代わりにディスクにデータを保存する1つのMySQLテーブルで非常に簡単に行うことができます。これだけのデータは、スタンドアロンアプリケーションで効率的に処理されることを意図したものではありませんでした。

CREATE TABLE TONS_OF_STRINGS
(
  unique_string varchar(255) NOT NULL,
  UNIQUE (unique_string)
)

値をループして（ここではコンマ区切りのリストを想定）、各トークンを挿入してみてください。失敗した各トークンは重複しています。

public static void main(args) {
  Connection con = DriverManager.getConnection("jdbc:mysql://localhost/database","username","password");
  FileReader file = new FileReader("SomeGiantFile.csv");
  Scanner scan = new Scanner(file);
  scan.useDelimiter(",");
  String token;
  while ( scan.hasNext() ) {
    token = scan.next();
    try {
      PreparedStatement ps = con.prepareStatement("Insert into TONS_OF_STRING (UNIQUE_STRING) values (?)");
      ps.setString(1, token);
      ps.executeUpdate();
    } catch (SQLException e) {
      System.out.println("Found duplicate: " + token );
    }
  }
  con.close();
  System.out.println("Well that was easy, I'm all done!");
  return 0;
}

ただし、完了したらテーブルをクリアすることを忘れないでください。これには大量のデータが含まれます。

于 2011-10-02T00:05:43.177 に答える
3

単純に 32 ビットまたは 64 ビットのハッシュコードを格納するだけでは十分ではありません。これは、2 つの異なる文字列 (数十億のうちの 1 つ) が簡単に同じハッシュコードを持つ可能性があるためです。同じハッシュコードを持つ 2 つの文字列を取得したら、実際の文字列を比較して、それらが実際に等しいかどうかを確認する必要があります。

この問題を解決する方法は次のとおりです。

  1. ファイル/文字列のストリームを読み取ります。

    1. 各行を読む

    2. 行のハッシュ コードを計算する

    3. ハッシュコードと文字列を一時ファイルに書き込み、その間に適切なフィールドセパレーターを挿入します

  2. 適切な外部ソート プログラムを使用して、ハッシュコード フィールドをプライマリ ソート キーとして使用し、文字列フィールドをセカンダリ ソート キーとして使用して一時ファイルをソートします。

  3. 一時ファイルを 1 行ずつ読み取ります。2 つの連続する行に同じハッシュコード フィールドと異なる文字列フィールドがある場合、重複した文字列が見つかりました。

注: このアプローチは、32 ビットまたは 64 ビットのハッシュコードで同様に機能します。

于 2011-10-01T23:36:38.960 に答える