1

私はアルゴリズムの問​​題について読んでいましたが、その1つは次のとおりです。

数百万行のデータを含むファイルがある場合、同一の2行があります。行が非常に長いため、メモリに収まらない可能性があります。2つの同一の線を見つけます。

提案された解決策は、部分的に行を読み取り、各行にハッシュを作成することでした。
たとえば、行1のパート1のハッシュ（メモリで読み取ることができます）を作成してから、行1のパート2から行1のパートNまでのハッシュを作成して、行1
のハッシュを作成します。ファイルまたはハッシュテーブル。同じハッシュ値について、行を比較します。線が同じであれば、それを解決しました。

私はこのソリューションを大まかに理解していますが、これをどのように実装できるかわかりません。ハッシュをファイル内の特定の行に関連付けるにはどうすればよいですか？この言語実装の詳細ですか？
たとえば、Javaでは、これにどのように対処しますか？

4

3 に答える 3

2

本当の答えは、より多くのメモリを購入することです。Java 2 GBで使用できる最長の文字列で、最近のマシンに適合します。32GBを200ドル未満で購入できます。

しかし、問題を解決するために、私はあなたに提案します

  • 各線のオフセットを見つけます。
  • 同じ長さの線を見つける（オフセットの差を使用）
  • 同じ長さの行の64ビット以上のハッシュを計算します。
  • 同じハッシュを持つ行については、バイトごとの比較を行います。

注：ファイル全体をキャッシュするのに十分なメモリがない場合、これには非常に長い時間がかかります。32GBのマシンと64GBのファイルがある場合、各パスには約20分かかり、これには複数のパスがあります。

1）オフセットを見つけるためのAPIはどれですか？

読み取ったバイト数を数えます。これがオフセットです。

2）本当の答えは、より多くのメモリを購入することです。プロジェクトマネージャーは、実際の製品についてこれに同意しません。別の経験がありますか？

私は彼らに、リソースの有効活用であると彼らが考える場合、1000ドル以上の費用がかかる可能性がある1日を過ごすことができることを指摘します（それが私が支払われるものではない場合でも）100ドルの再利用可能なメモリを節約します。私は彼らに決めさせました;）

私の8歳の息子は、メモリのコストが24ポンドだったので、彼が作成したPCに8GBを搭載しています。それでも、8 GBは、1時間あたりのコストがかかる専門家には多すぎると考えるプロジェクト管理者がいるのは正しいです！？私はPCに16GBを持っていますが、256 GBのマシンで作業をしているので、深刻なことを実行するために使用することはありません。最近では2TBのマシンを購入できますが、これはほとんどのアプリケーションにとってやり過ぎです。;）

于 2013-01-14T18:54:26.457 に答える
0

私は解決策が現代の技術を利用し、最近のメモリの安さを活用することであることに同意しますが、問題は心を動かし、与えられた制約の下で問題を解決する方法を理解することを目的としています。

あなたが話したハッシュはかなり単純です。Javaソリューションは、実際に何が起こっているのかを曖昧にする可能性のあるいくつかのことを内部で活用できるため、最初にソリューションを説明し、次にJava実装について説明します。

一般的な解決策：

SHA1、MD5などのハッシュは、入力を圧縮することによって整数を生成します。各行の最初のMB文字のみを格納できるとしましょう。

  • 各行を繰り返し処理し、最初のMBの文字を取得して、それをハッシュアルゴリズム（MD5など）に渡します。
  • 次に、ハッシュをキーとしてマップし、行番号のリスト/配列を値としてマップします。
  • 最初のパスの後、最初のMBの文字が一致する行はすべて同じハッシュになり、マップ内の同じリストに含まれます。
  • 2番目のパスの準備をするには、マップを検索し、行番号が1つしかないリストをカリングします。
  • 次に、マップの残りのエントリから行番号をコンパイルして行番号のリストを作成します。これらの行は、2番目のパスでチェックされる唯一の行になります。
  • 2番目のパスでは、行リストの各行から2番目のMBの文字を取得し、それらをハッシュして、パス1と同じ方法でマップに配置します。
  • マップ内のエントリを繰り返し処理し、行番号が1つしかないハッシュエントリをカリングします。
  • 手順2を繰り返しますが、パス番号と一致するように文字ブロック（MB）をインクリメントします。
  • 複数の行番号を持つハッシュが1つだけで、そのハッシュに要素が2つしかないパスに到達すると、それらの行は同じ2つになります。

これは本質的にツリー検索です。

Javaメソッド：Javaには、キーを自動的にハッシュするHashMapというクラスがあります。を使用して

HashMap<String,ArrayList<Integer>>

マスターマップの場合、各呼び出しを行う必要があるのはすべて

  • map.get（mbBlock）.add（lineNumber）; もちろん、このキーが初めて使用されるかどうかを確認して、nullポインタ例外が発生しないようにする必要があります。
  • 各パスの後で、1行のみを含むエントリをカリングします。
  • 行番号が2つだけになるまで、残りの行を繰り返します。
于 2013-01-14T19:32:11.167 に答える
0

  1. 各行の最初のk文字を取得します。ここで、kは構成可能です。ハッシュを実行して、同じ行を持つ可能性のある行のいくつかのグループを見つけます。

  2. 検索範囲を大幅に絞り込む最初のステップの結果に基づいて、次のk文字の小さなグループごとにアルゴリズムを実行します。

  3. 最悪の場合ではないにしても、各ラウンドの後に検索範囲が劇的に絞り込まれます。

アルゴリズムの秘訣は、大きな問題を小さな問題に分割し、前の手順の結果を最大限に活用することです。

于 2013-01-18T16:55:08.250 に答える