Soru Hash_map kullanırken bir stl dizesinde kullanılacak en iyi karma algoritması nedir?


Yüksek performans aramaları elde etmek için çalışırken VS2005 standart karma işlevinin ağrılı bir şekilde yavaş olduğunu buldum. Çarpışmaların çoğunu geçersiz kılan hızlı ve verimli karma algoritmaların iyi örnekleri nelerdir?


44
2017-09-18 23:58


Menşei


Aşağıdakiler iyi bir genel amaçlı karma işlevler kümesine sahiptir, bunları veri kümenize karşı denemeniz gerekir, bazıları da diğerlerine göre çarpışmalara dayanabilir: partow.net/programming/hashfunctions/index.html
Olası kopya Dizeler için İyi Hash Fonksiyonu - M.J. Rayburn


Cevaplar:


İle çalıştım Paul Larson bazı araştırmalar için Microsoft Araştırmaları. Çeşitli veri kümeleri üzerinde bir dizi dizgi toplama işlevini araştırdı ve basitçe 101 ve ekleme döngüsü ile çarpmanın şaşırtıcı derecede iyi çalıştığını gördü.

unsigned int
hash(
    const char* s,
    unsigned int seed = 0)
{
    unsigned int hash = seed;
    while (*s)
    {
        hash = hash * 101  +  *s++;
    }
    return hash;
}

63
2017-09-20 08:46



Selam George. Kodumu, cevabımda gönderdiğim karma ölçütte denedim. Güzel bul. Performans veya çarpışmalarda üstün değildir, ancak her zaman tutarlı sonuçlar verir. Genel amaçlı string-hashing için iyi ve ucuz bir aday gibi görünüyor. - Nils Pipenbrinck
Ancak bu sadece küçük uzunluktaki dizeler için çalışır. Büyük vakalar için, zamanın çoğunu taşar. - Soumajyoti
Soumajyoti, taşma önemli değil. En hash fonksiyonları taşar. Asıl amacı düşük sıralı 32 bitlik parçalarda iyi bir bit karışımı elde etmenizdir. - George V. Reilly
Bu Java uygulamasına benziyor, ancak 101 yerine 31 kullanıyor. - Jorge Galvão


Bazı eski kodlarımdan:

/* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */
static const size_t InitialFNV = 2166136261U;
static const size_t FNVMultiple = 16777619;

/* Fowler / Noll / Vo (FNV) Hash */
size_t myhash(const string &s)
{
    size_t hash = InitialFNV;
    for(size_t i = 0; i < s.length(); i++)
    {
        hash = hash ^ (s[i]);       /* xor  the low 8 bits */
        hash = hash * FNVMultiple;  /* multiply by the magic number */
    }
    return hash;
}

Hızlı. Gerçekten çıldırtıcı.


18
2017-09-19 00:01



hızlı olabilir, ama muhtemelen her zaman en büyük icat edilmiş birleşik icat fonksiyonlarından biri.
@Matthieu: Neden? Birçok kopya mı? Daha fazla okuyabileceğim herhangi bir referansın var mı? - Albert
@Albert: ^ geçişli, kötü olan. FNVMultiple Başbakan değil, hangi kötü. InitialFNV ya da kötü olmayabilir, ben belirsiz değilim, asal değil. - Mooing Duck
@MooingDuck FNVMultiple asal sayı gibi görünüyor. - bysreg
Eğer çok kötüyse, neden bu kadar yaygın kullanılıyor? isthe.com/chongo/tech/comp/fnv/#FNV-1a - Nick


Artırmak vardır bir artırmak :: karma En yaygın türler için bazı temel karma işlevleri sağlayan kütüphane.


8
2017-09-19 00:01





Bu her zaman veri setinize bağlıdır.

Birincisi için dizinin CRC32'sini kullanarak şaşırtıcı derecede iyi sonuçlar elde ettim. Çok çeşitli farklı giriş setleri ile çok iyi çalışır.

İyi CRC32 uygulamalarının birçoğu ağda bulmak kolaydır.

Düzenle: Neredeyse unutuldu: Bu sayfa, performans rakamları ve test verileriyle birlikte güzel bir karma işlev şovuna sahip:

http://smallcode.weblogs.us/ <- sayfanın ilerleyen kısımlarında.


7
2017-09-18 23:59





Ben bir Jenkins filtre kütüphanesi yazmak için Jenkins hash kullanıyorum, bu harika bir performansa sahip.

Ayrıntılar ve kod burada mevcuttur: http://burtleburtle.net/bob/c/lookup3.c

Perl'in karma operasyon için kullandığı şey bu, Fwiw.


6
2017-09-19 00:24



Ayrıca bak ürkütücü karma Jenkins'de bir gelişme - Soren


Sabit bir kelime kümesi varsa, en iyi karma işlevi genellikle bir mükemmel hash fonksiyonu. Ancak, genellikle, karma çalmaya çalıştığınız sözcük kümesinin derleme zamanında bilinmesini gerektirir. Anahtar kelimelerin bir lexer (ve anahtar kelimelerin tokenlere çevrilmesi) gibi araçlarla oluşturulan mükemmel karma işlevlerin yaygın kullanımıdır. gperf. Mükemmel bir karma ayrıca değiştirmenizi sağlar hash_map basit bir dizi veya vector.

Eğer sabit bir kelime kümesi yoksa, o zaman bu geçerli değildir.


6
2017-09-19 03:13





Bir dizi karma için bir klasik öneri, bir akümülatöre ascii / unicode değerlerini birer birer ekleyerek, her defasında akümülatörün bir asal sayı ile çarpılmasıdır. (karma değerde taşmaya izin vermek)

  template <> struct myhash{};

  template <> struct myhash<string>
    {
    size_t operator()(string &to_hash) const
      {
      const char * in = to_hash.c_str();
      size_t out=0;
      while(NULL != *in)
        {
        out*= 53; //just a prime number
        out+= *in;
        ++in;
        }
      return out;
      }
    };

  hash_map<string, int, myhash<string> > my_hash_map;

Verileri atmadan daha hızlı olmak zor. Dizelerinizin yalnızca birkaç karakterle değil tüm içeriğiyle ayırt edilebileceğini biliyorsanız, daha hızlı yapabilirsiniz.

Değerin çok sık hesaplanması durumunda, karma değerini hatırlayan yeni bir basic_string alt sınıfı oluşturarak karma değerini daha iyi önbelleğe almayı deneyebilirsiniz. hash_map bunu dahili olarak yapıyor olmalıydı.


2
2017-09-19 00:18



Yoda durum uyarısı! Bunun dışında bu Larson algoritmasına benzer (bunun daha önce yayınlandığını fark ettim!). - Helge Klein