java - 如何提高大量的字符串比较速度

Answer 1

私はアルゴリズムバカですが、たまたま利用可能なコンピューティング リソースがあるので、元のアイデア (暴力的な頭脳のない並列コンピューティング フロー) に従って、質問の例を実行します。

run.py

リーリー

単純にポイントデータを生成する

リーリー

さて、10000 で動作する candidates.txt と 1000000 bg_db.txt で動作する
を作成し、それを実行して時間を確認します。

リーリー

対象の実際のデータは数千万行candidates.txt、数十億行bg_db.txtです。
16*1000/(60*24) = 11.11
は11日であると計算されます。使用されたノード構成

リーリー

非常に時間がかかるため、至急最適化が必要です

Answer 2

@武合之zon のアイデアに基づいて、2 倍のスペースを使用し、4 種類の文字を表すのに 4 ビットを使用することで、その後の一貫性のない文字番号の検索を簡素化できます

Answer 3

座ってマスターが現れるのを待ちます

Answer 4

アイデアは次のとおりです。
最初: たとえば、4 つの異なるデータを比較します
**TGACGGGTGACACCCA (文字列の特定の 4 つの位置にある文字を削除)、文字長を次のように変更します。 16、全く同じ文字列と一致する
マップなどを使ってキー値としてTGACGGTGACACCCAを保存し、4つの差分を値として保存します

2 番目: 3 つの異なるデータを比較します
上記を元に、上記の値を比較して、長さ 3 の同じ文字列を比較します

その他

Answer 5

CUDA などの並列コンピューティングについて学ぶことができ、単純な操作を多数繰り返すとパフォーマンスが向上するのは明らかです。

Answer 6

リーリー

Answer 7

4 つの文字を 00、01、10、11 に簡略化するアイデアを提供してください。
比較する場合は、最初に XOR を実行し、一致する場合は 00 になり、一致しない場合は 01、10、または 11 になります。
次に、XOR 結果の隣接する各ペアに対して OR を実行し、00 が 0 になり、01、10、または 11 が 1 になります。最後に1の数を数えます。これらはすべてビット演算であるため、理論的には非常に高速になるはずです。

しかし、私は C を学ぶのが苦手なので、コードを投稿できません。