Mükemmel bir karma için bir işlev tasarlamaya nasıl giderdin?

Question

İlgi alanı dize eşleşmesidir. Böyle bir yapıya sahip olduğumu varsayın.

typedef struct 
{ 
    char *name, 
    int (*function)(); 

} StringArray 

StringArray s[] = 
{ 
    {"George", func1}, 
    {"Paul", func2}, 
    {"Ringo", func3}, 
    {"John", func4}, 
    {"",  NULL} /* End of list */ 
} 

Dizide sabit sayıda dizgi var. Örnekte olduğu gibi kodlanmışlardır. Tablo değişirse, hash işlevinin kalitesini yeniden değerlendirmek gerekir.

Bir dizeye bir karma işlevi uygulamak istiyorum ve dize dizideki bir ile eşleşiyorsa, işlevini çağırın. Bunun için mükemmel bir karma işlevi gereklidir. Çarpışmalara izin verilmez. Yemin etmenin amacı, aramada O (1) performansının elde edilmesidir.

Bunu yapmak için bir işlev tasarlama konusunda hangi fikirlere sahipsiniz?

Answer 1

kullanabilirsiniz.

Answer 2

Sen gperf giriş sayfasına bakın haritayı

std::string foo() { return "Foo"; } 
std::string bar() { return "Bar"; } 

int main() 
{ 
    std::map<std::string, std::string (*)()> m; 
    m["foo"] = &foo; 
    m["bar"] = &bar; 
} 

Answer 3

bakınız:

What is a good Hash Function?

Best hashing algorithm in terms of hash collisions and performance

What is a performant string hashing function that results in a 32 bit integer with low collision rates?

Choosing a multiplier for a (string) hash function

Very low cost hash function

What’s the best hashing algorithm to use on a stl string when using hash_map?

Answer 4

çarpışmalar kesinlikle izin verilmez değilseniz, tek seçenek muhtemelen bir en iyi yol değildir veritabanında her dize, takip etmektir gitmek.

Yapacağım şey, MD5 veya SHA gibi mevcut ortak güçlü karma algoritmalardan birini uygulamaktır. Etrafta örneklerin mimiad'leri var, örneğin bir tane: İşte bir örnek: http://www.codeproject.com/KB/security/cryptest.aspx

Answer 5

Mükemmel bir hash fonksiyonu yok.

Çarpışmaları en aza indirecek çok şeyiniz var, ancak hiçbiri bunları yok etmiyor.

olsa birini tavsiye edebilir: P

DÜZENLEME: Çözüm mükemmel karma işlevi bulma olamaz . Çözüm, çarpışmaların farkında olmaktır. Genelde karma işlevinin çarpışmaları vardır. Bu açıkça, veri kümesine ve sonuçta oluşan karma kodun boyutuna bağlıdır.

Answer 6

Dengeli bir ikili ağaç kullanın. Sonra, KNOW davranışı, ALWAYS O (logn) olur.

Keskiler sevmiyorum. İnsanlar algoritmaları ile ne kadar risk aldıklarını fark etmiyorlar. Bazı test verilerini çalıştırıyorlar ve alana yerleştiriyorlar. Kullanılmamış bir karma algoritmanın ASLA alanında davranış kontrolü olup olmadığını gördüm. O (1) yerine hemen hemen her zaman kabul edilebilir olan

.

Answer 7

Özet, hem C hem de C++'yi listeler. Hangisini arıyorsun? C ve C++ iki ayrı dildir ve string işleme ve veri yapılarında büyük ölçüde farklılık gösterir (ve C'nin C++ içinde çalışması gerçeği değişmez).

Neden, özellikle, mükemmel bir karma işlev istiyor musunuz? Bir dizeyi bir işlevle ilişkilendirmek istiyor ve bunu yapmak için iyi bir yol olacağını düşündünüz mü? Bu bir çeşit ödev görevi mi? <> C++ haritasından kaçınmak için bir nedeniniz var mı? (Ya da unordered_map <> eğer mevcutsa?)

Mükemmel bir kareye ihtiyacınız varsa, dizelerdeki kısıtlamalar nelerdir? Göndermek istediğiniz belirli bir sabit set olacak mı? Setlerden biri ile uyuşmayan dizeler ne olacak? Rastgele dizelerden isabet almayı kabul ediyor musunuz, yoksa gelen dizelerin sayısı sınırlı mı?

Sorunuzu bu gibi bilgileri içerecek şekilde düzenleyebilirseniz, çok daha yararlı olabiliriz. (Ilk iki yorumlara yanıt olarak)

DÜZENLEME: Eğer tahminen sizin C ve C++ çalışmaları hem bunu istiyor çünkü

Tamam, C çözümleri bakmak gerekir. Muhtemelen performansı istiyorsun, ama test ettin mi? G/Ç sisteminde gelen dizelerle uğraşıyorsak, gönderim zamanının cüce olması muhtemeldir.

Rasgele dizeler bekliyorsunuz. Tüm çarpışmaları rastgele verilerden uzaklaştıracak mükemmel bir karma işlev beklemek biraz fazladır, bu yüzden bunu dikkate almanız gerekir.

trie'u düşündünüz mü? Mükemmel bir karma fonksiyonundan (veya olmamasından) daha verimli olabilir, C içinde uygulanması oldukça kolay olmalı ve sevk dizileri veya olası çarpışmalar listenizi yeniden tasarlamada sorunlardan kaçınacaktır.

Answer 8

Bu egzersizin nihai sonuç net kapalı dize odaklı hash fonksiyonları bir dizi çalmak

etmekti.
• Her bir işlevi, veri kümesiyle bir dizi mod operatör değeriyle test eden ve bu işlevle çalışan en küçük mükemmel hashı arayan bir tür fabrika sınıfı oluşturun.
• Bu fabrika sınıfı varsayılan yapıcısı, doğru karma işlevini çektiğinde ve en az miktarda bellek gerektiren mükemmel karma değeri vermek için mod boyutunu belirleyen bir dizi argümanı temsil eden bir dize döndürür.
• normal kullanımda, yalnızca döndürülen argümanlarla sınıfı başlatırsınız ve sınıf kendini istenen işlevlere sahip bir çalışma durumuna sokar.
• Bu kurucu, herhangi bir çarpışma olmadığını ve varsa iptal edildiğini doğrular.
• Kusursuz karmanın bulunmadığı durumlarda, giriş tablonun sıralı bir sürümünde ikili bir aramaya dönüşür.

Etki alanımdaki diziler için bu çok iyi çalışıyor gibi görünüyor. Gelecekteki olası bir optimizasyon, girişin alt dizileri üzerinde aynı tür testleri yapmaktır. Örnek olayda, her müzisyen isminin ilk harfi, birbirinden ayırmak için yeterlidir. Daha sonra, gerçek hash fonksiyonunun maliyetini, kullanılan hafızaya karşı dengelemek gerekir.

Fikir veren herkese teşekkür ederim. Evil