問題タブ [hamming-distance]

古い投稿には、次のコードが含まれていました。

背後にある理由は何if len(num[item:]) > dist - 1ですか？

リストtransに格納されたn（〜1000000）文字列（DNAシーケンス）のセットがあります。リスト内のすべてのシーケンスの最小ハミング距離を見つける必要があります。私は単純なブルート フォース アルゴリズムを実装しましたが、これは 1 日以上実行されており、まだ解決策が示されていません。私のコードは

これを行うためのより効率的な方法はありますか? ここで hamdist は、ハミング距離を見つけるために私が書いた関数です。それは

ハミングウェイトに関するウィキペディアの記事を読んで、興味深いことに気づきました。

したがって、同じ長さのすべてゼロの文字列の from と同等Hamming distanceです。最も典型的なケースであるビットのストリングの場合、これはストリング内の 1 の数です。この2 進数の場合は、人口数、popcountまたは横方向の合計とも呼ばれます。

[鉱山を強調]

それで、何かが私に起こりました。XOR2 つの文字列をingし、結果の文字列のハミング ウェイト (POPCOUNT) を取得して、2 つの文字列間のハミング距離を計算できますか?

これに沿ったもの（gcc組み込み関数を使用）：

さて、なぜこれをしたいのかというと、一部のプラットフォームでは、そうです、これは単にgccを計算する関数への呼び出しを発行することに変換されますpopcount。たとえば、なしの x64popcntでは、gcc吐き出します ( Godbolt の GCC Online ):

OTOH、POPCOUNT をサポートするプラットフォームを使用している場合、x64 モデルnehalem以降 (を含むPOPCNT) のように、( Godbolt の GCC Online )が得られます。

特にインライン化すると、これは非常に高速になるはずです。

しかし、元の質問に戻ります。2 つの文字列の XOR のハミング重みをとって、それらのハミング距離を見つけることができますか? すなわち:

私は Go でアセンブリ言語を使用して遊んでおり、演習としてHamming Weight関数を作成しました。

この SO 回答に基づいてネイティブ Go バージョンを作成しました。アセンブリ バージョンはAMD (page 180) のこのドキュメントに基づいています。2 つの関数のベンチマークを行ったところ、ネイティブの Go バージョンはアセンブリ バージョンよりも約 1.5 倍から 2 倍高速であることがわかりました。ただし、手書きのアセンブリ バージョンは からの出力とほぼ同じですgo tool 6g -S popcount.go。

からの出力go test -bench=.

popcount.go

popcount_test.go

popcount_amd64.s

からの出力go tool 6g -S popcount.go

ここから、行にガベージ コレクターの情報が含まれていることがわかりますFUNCDATAが、それ以外に明らかな違いは見られません。

この 2 つの関数の速度の大きな違いの原因は何ですか?

1. バイナリ コードを効率的に格納するにはどうすればよいですか? 32 ビットなどの特定の固定サイズでは、使用できるプリミティブ型があります。しかし、私のバイナリコードがもっと長い場合はどうなるでしょうか?

2. 2 つのバイナリ コード間のハミング距離を計算する最速の方法は何ですか?

既に計算された 2 つの記述子間の距離 (ユークリッドまたはハミング) を計算しようとしています。問題は、マッチャーを使用したくないことです。2 つの記述子間の距離を計算したいだけです。私は OpenCV 2.4.9 を使用しており、私の記述子を Mat 型に格納しています。

そして今、記述子1の行1と記述子2の行1の間の距離（バイナリ記述子を使用しているため、ハミング距離が望ましい）を計算したいだけです（たとえば）。

bitwise_xor() 関数を使用しようとしましたが、ビットカウントを行う効果的な方法がありませんでした。2 つの配列間のハミング距離を計算する関数はありませんか?

私は OpenCV にかなり慣れていないことに気付きましたが、助けていただければ幸いです。ありがとうございました