2

2 GB の大きなテキスト ファイルがあり、タブで区切られた 5 つの列があります。行は、5 つの列のうち 4 つが一致する場合にのみ重複と呼ばれます。

現在、最初に各列を別々の List にロードし、次にリストを反復処理し、重複した行を削除して集計することにより、dduping を行っています。

問題: 1 つのファイルを処理するのに 20 時間以上かかっています。 処理するファイルが 25 個あります。

誰かが自分の経験を共有してもらえますか?

この dduping は使い捨てコードになります。そのため、できるだけ早く仕事を終わらせるために、迅速で汚い解決策を探していました。

これが私の擬似コードです（大まかに）

Iterate over the rows
  i=current_row_no.    
    Iterate over the row no. i+1 to last_row
                    if(col1 matches  //find duplicate
                        && col2 matches
                        && col3 matches  
                        && col4 matches)
                        { 
                           col5List.set(i,get col5); //aggregate 
                        }

重複例

A と B は重複し、A=(1,1,1,1,1)、B=(1,1,1,1,2)、C=(2,1,1,1,1) となり、出力はbe A=(1,1,1,1,1+2) C=(2,1,1,1,1) [B が追い出されたことに注意]

4

5 に答える 5

3

HashMap が最善の策です。1 回の一定時間の操作で、重複をチェックし、適切な集計構造 (私のコードでは Set) をフェッチすることができます。これは、O(n) でファイル全体をトラバースできることを意味します。コード例を次に示します。

public void aggregate() throws Exception
  {
    BufferedReader bigFile = new BufferedReader(new FileReader("path/to/file.csv"));

    // Notice the paramter for initial capacity. Use something that is large enough to prevent rehashings.
    Map<String, HashSet<String>> map = new HashMap<String, HashSet<String>>(500000);

    while (bigFile.ready())
    {
      String line = bigFile.readLine();
      int lastTab = line.lastIndexOf('\t');
      String firstFourColumns = line.substring(0, lastTab);

      // See if the map already contains an entry for the first 4 columns
      HashSet<String> set = map.get(firstFourColumns);

      // If set is null, then the map hasn't seen these columns before
      if (set==null)
      {
        // Make a new Set (for aggregation), and add it to the map
        set = new HashSet<String>();
        map.put(firstFourColumns, set);
      }

      // At this point we either found set or created it ourselves
      String lastColumn = line.substring(lastTab+1);
      set.add(lastColumn);
    }
    bigFile.close();

    // A demo that shows how to iterate over the map and set structures
    for (Map.Entry<String, HashSet<String>> entry : map.entrySet())
    {
      String firstFourColumns = entry.getKey();
      System.out.print(firstFourColumns + "=");

      HashSet<String> aggregatedLastColumns = entry.getValue();
      for (String column : aggregatedLastColumns)
      {
        System.out.print(column + ",");
      }
      System.out.println("");
    }
  }

いくつかのポイント:

  • HashMap の initialCapaticy パラメーターは重要です。エントリ数が容量を超えると、構造が再ハッシュされますが、これは非常に遅くなります。デフォルトの初期容量は 16 です。これにより、多くの再ハッシュが発生します。最初の 4 列の一意のセットの数よりも大きいことがわかっている値を選択します。
  • 集約で順序付けされた出力が重要な場合は、HashSet を TreeSet に切り替えることができます。
  • この実装は大量のメモリを使用します。テキスト ファイルが 2GB の場合、おそらく jvm に大量の RAM が必要になります。jvm 引数-Xmx4096mを追加して、最大ヒープ サイズを 4GB に増やすことができます。少なくとも 4 GB を持っていない場合、これはおそらく機能しません。
  • これも並列化可能な問題なので、必死ならスレッド化できます。ただし、それは使い捨てコードにとっては大変な作業です。[編集: コメントで指摘されているように、この点はおそらく真実ではありません]
于 2012-04-10T15:45:31.847 に答える
1

レコードの HashSet を使用します。これにより、O(n^2) ではなく O(n) タイミングが発生する可能性があります。行ごとに 1 つのインスタンスを持つ各フィールドを持つクラスを作成できます。

十分な量のメモリが必要ですが、最近では 16 ～ 32 GB がかなり安価です。

于 2012-04-10T15:42:58.350 に答える
1

リスト全体を最初の 4 列で並べ替えてから、すべての重複がまとめられていることを認識して、リストをトラバースします。これにより、ネストされたループの O(N^2) ではなく、ソートの O(NlogN) とトラバースの O(N) が得られます。

于 2012-04-10T15:31:35.323 に答える
0

Eric のソリューションと同様のことを行いますが、実際の文字列を HashMap に格納する代わりに、行番号のみを格納します。したがって、特定の 4 列のハッシュについては、その値にハッシュされる行番号のリストを保存します。次に、データの 2 番目のパスで、それらの行番号の重複を削除したり、必要に応じて +x を追加したりできます。

このようにして、メモリ要件が大幅に小さくなります。

于 2012-04-10T15:58:28.050 に答える
0

十分な (無料の) RAM がある場合は、既に投稿されているソリューションが適しています。Java はスワッピングが頻繁に行われている場合でも「まだ動作する」傾向があるため、RAM が制限要因である可能性があると推定される場合は、スワップ アクティビティが多すぎないように注意してください。

実際に RAM が少なすぎる場合の簡単な「使い捨て」ソリューションは、最初の 4 列のデータに応じて、最初にファイルを複数のファイルに分割することです (たとえば、3 番目の列の値が多かれ少なかれ均一に分散されている場合、その列の最後の 2 桁）。ファイルを 1 回調べて、パーティションの値に応じて、レコードを 100 個の異なるファイルに読み込んで書き込みます。これには最小限の RAM が必要であり、残りのファイル (パーティショニング値が十分に分散されている場合、それぞれ約 20MB のみ) を必要なメモリを大幅に削減して処理し、結果を再度連結できます。

明確にするために：十分なRAMがある場合（OSがディスクキャッシュとバックグラウンドアクティビティにもいくつか必要であることを忘れないでください）、このソリューションは遅くなります（おそらく2倍になるため、データを読み書きする必要があります)、しかし、スワップを死に至らしめる場合は、はるかに高速になる可能性があります:-)

于 2012-04-10T17:25:58.990 に答える