私は大学からプログラミングのタスクを持っています。これは、何百ものファイル (1 メガバイト未満の良いファイルと悪いファイル) をバイト単位で比較して、一定の長さの共有文字列を見つける必要があります。
比較の全体をカバーしようとしていて、実際に各ファイルを他のファイルと比較するとします。実際にこのタスクを数分以内に完了することは可能でしょうか?
私は素朴なアルゴリズムを試し、数日間改善してきましたが、数時間以内に収まるようには見えません。
私がこれまでにやったこと：
CPU：
さまざまな比較とバッファ サイズをローカルでベンチマークして、ニーズに最も適したものを確認しました。
署名自体は保持せず、署名への参照のみを保持します（ファイルと同じサイズのブール配列を介して-除外されたインデックスを再度比較しないようにするのにも役立ちます）。
現在、呼び出し可能な比較タスクをシステムにインストールしていますが、オーバーヘッドや同期の問題が発生しすぎないことを願っています。
仮想メモリ:
スラッシングを防ぐために、使用可能な空きメモリ (System.freeMemory()手動で指定した後は約 2GB) に応じてバッファ サイズを決定しています。ファイルごとに保存された情報の間で合理的な (私の見解では) トレードオフに落ち着いています。
アルゴリズム：
ファイルの構造を静的に分析した後、疑わしい場所にあるバイトのサブセットのみを比較しようとしました (JAR ファイル。バイトコードから関連性を推定する方法がわからないため、バイトコードには入りませんでした。 "classes.dex")。
これは一般的なタスクでなければならないことを考えると、非常に明白な何かが欠けていますか? 署名をハッシュする方が高速になる可能性があると言われましたが、比較が終了するのを待って後で参照を介して保存するよりも高速であるとは思えません (ボトルネックである比較自体が終了すると、これは非常に高速です)。 . 私には、ハッシュは大きな VM 占有リスクのように思えます。
これは「合理的な時間」内に実行する必要があると言われ、その目的は、ファイル (またはそれに近い) の最良の (最小の) スーパーセット (ほとんどの不良ファイルをカバーし、正常なファイルをカバーしない) を見つけることです。それを完了したと主張する何人かの人々を聞いた後、私は途方に暮れているように思えます。
さらに情報が必要な場合は、お問い合わせください。投稿に編集します。
これを更新するのを忘れた場合に備えて、Trie のこの実装を使用する予定です。これに遭遇した場合は、必要に応じてそれ (またはこのプロジェクトの他のユーザー) を利用できることを願っています!