Sorun:

Belirli bir büyük (~100 milyon) listesi işaretsiz 32-bit tamsayı, işaretsiz bir 32-bit tamsayı giriş değeri ve maksimum Hamming Distance dönüş tüm liste üyeleri içinde belirtilen Hamming Mesafe girdi değeri.

Liste veri yapısı oluşturmak için açık, performans gereksinimleri, bellek içi bir çözüm dikte, maliyeti tutmak için gerçek veri yapısı veri yapısı önemlidir sorgulamak için ikincil, düşük maliyetli.

Örnek:

For a maximum Hamming Distance of 1 (values typically will be quite small)

And input: 
00001000100000000000000001111101

The values:
01001000100000000000000001111101 
00001000100000000010000001111101 

should match because there is only 1 position in which the bits are different.

11001000100000000010000001111101

should not match because 3 bit positions are different.

Düşüncelerimi şimdiye kadar:

0, sadece Hamming Mesafesi durumunda dejenere için sıralı bir listesini kullanmak ve belirli giriş değeri için bir ikili arama yapın.

Hamming Uzaklığı sadece 1, Orijinal giriş her bit flip ve üzeri 32 kere tekrar edebilirim olurdu.

Nasıl verimli (listenin tamamını taramadan) Hamming Mesafe ^ ile liste üyeleri bulabilir miyim . 1.

Soru:Biz Hamming uzaklığı d(x,y) hakkında ne biliyorsun?

Cevap:

1. Negatif: 0 ≥ d(x,y)
2. Aynı girişler için sadece sıfır: d(x,y) = 0 ⇔ x = y
3. Simetrik: d(x,y) = d(y,x)
4. Üçgen eşitsizliği, (x,z) d(n d(x,y) d (y,z) dir

Soru:Neden önemsiyoruz?

Cevap:Hamming mesafe anlamına gelir çünkümetrikbir içinmetrik uzay. Metrik uzaylar indeksleme algoritmaları vardır.

• Metric tree (Wikipedia)
• BK-tree (Wikipedia)
• M-tree (Wikipedia)
• VP-tree (Wikipedia)
• Cover tree (Wikipedia)

Ayrıca "mekansal dizin" genel olarak, uzay ama . Öklid olmayan bilgi ile donanmış algoritmaları arayabilirsiniz ^em>bir metrik uzay. Bu konuda birçok kitap dize dizin oluşturma Hamming uzaklığı gibi bir metrik kullanarak koruyun.

Dipnot:Eğer sabit genişlikli dizeleri Hamming uzaklığı karşılaştırma, montaj veya işlemci ön tanımlı kullanarak önemli bir performans artışı elde etmek mümkün olabilir. GCC ile örneğin, (manual) bunu yapmak için:

static inline int distance(unsigned x, unsigned y)
{
    return __builtin_popcount(x^y);
}

Eğer SSE4a, sonra bir bilgisayar için derleme sonra bilgilendirmek GCC eğer bu sadece bir kaç işlem kodları azaltılması gerektiğine inanıyorum.

Düzenleme:Kaynaklarına göre, bu kodu ekleyin/her zamanki maskesi/vardiyasında daha sık bazen daha yavaş. Kıyaslama sistemi, C versiyonu daha iyi performans GCC __builtin_popcount 160% ile gösteriyor.

Ek:Üç uygulamaları tekrar söyler o yüzden sorunu kendim merak ettim,: doğrusal arama, BK ağaç, ağaç ve Başkan YARDIMCISI. VP ve BK ağaçları çok benzer olduğunu unutmayın. BK ağacındaki bir düğümü çocukları "" ağaçlar içeren işaret eden ağacın merkezine sabit bir mesafe vardır. kabukları vardır VP ağacındaki bir düğümü iki çocuk, bir küre düğümün merkezi merkezli içindeki tüm noktaları içeren ve diğer çocuk dışında tüm noktaları içeren vardır. Çok kalın çok ince olanların yerine. iki kabukları ile BK bir düğüm olarak VP bir düğüm düşünebilirsiniz yani

Sonuçları 3.2 GHz benim PC de ele geçirildi algoritmaları çoklu çekirdek kolay olması () kullanmaya çalışmayın. 100M rastgele tamsayılar veritabanı boyutu seçtim. Sonuçlar mesafe 1..5 ve 6..10 ve doğrusal arama için 100 sorguları için 1000 sorgular, ortalama.

• Veritabanı: 100M rastgele tamsayılar
• Test sayısı: 1000 mesafe için 1..5, 100 mesafe için 6..10 ve doğrusal
• Bulgular: Ortalama # sorgu vurur çok yakındır
• Hız: sorgu Sayısı saniyede
• Kapsam: başına sorgu veritabanı muayene yüzdesi Ortalama

                -- BK Tree --   -- VP Tree --   -- Linear --
Dist    Results Speed   Cov     Speed   Cov     Speed   Cov
1          0.90 3800     0.048% 4200     0.048%
2         11     300     0.68%   330     0.65%
3        130      56     3.8%     63     3.4%
4        970      18    12%       22    10%
5       5700       8.5  26%       10    22%
6       2.6e4      5.2  42%        6.0  37%
7       1.1e5      3.7  60%        4.1  54%
8       3.5e5      3.0  74%        3.2  70%
9       1.0e6      2.6  85%        2.7  82%
10      2.5e6      2.3  91%        2.4  90%
any                                             2.2     100%

Yorum, söz:

BK-ağaçlar farklı bir kök düğüm ile BK-ağaçlara üreten ve bunları yayarak daha iyi olabileceğini düşünüyorum.

Bu tam olarak VP ağacı (biraz) BK ağacı daha iyi yapar nedeni de budur bence. ""Yerine"", daha fazla puan yerine daha az puan karşı daha hassas karşılaştırmalar kullanarak. karşı karşılaştırır sığ daha derin olmak Farklar Yüksek boyutlu uzaylarda daha aşırı olduğunu düşünüyorum.

Son bir ipucu: ağacın yaprak düğümleri sadece bir doğrusal tarama için tamsayılar düz diziler olmalıdır. Küçük ayarlar (ya da daha az 1000 puan) için bu daha hızlı ve daha hızlı olacak.