Poszukuje wysokiej jakości funkcji szarpania łańcuchów w języku Java/Scala - coś, co jest szybsze niż funkcje z rodziny MurmurHash, nie musi być silne pod względem kryptograficznym, a jedynie dobrze dystrybuowane.Wysoka wydajność funkcji mieszania napisów w języku Java/Scala
Wszelkie sugestie?
Można znaleźć bardzo szybko implementacje funkcji skrótu dla Java, które BTW koncie realizację wewnętrzny String (char[] array), aby zmaksymalizować prędkość, tutaj: https://github.com/OpenHFT/Zero-Allocation-Hashing
Najszybszym algorytmem mieszania pasującym do rachunku wydaje się być obecnie xxHash. Projekt lz4-java zawiera implementation ported to Java. Nie wiem, czy implementacja Java została porównana z programem MurmurHash; Optymalizacje wydajności w C++ nie zawsze przesyłają się do/z Java. (W szczególności, xxHash zawiera więcej dostępu do tablicy, więc nie może być nieistotnego ograniczenia do sprawdzania ograniczeń).
Edycja: wygląda na to, że używa JNI do wywołania implementacji C++ xxHash, ale narzut JNI jest niezauważalne, więc problemy z wydajnością pozostają.
Jednak, biorąc pod uwagę, że Scala includes a MurmurHash function, i że Java zawiera szybszy domyślny skrót (około 2x), który jest sorto-rozsądnie dystrybuowany czasami, można się zastanawiać, czy to naprawdę konieczne. Na przykład: scala.util.hashing.MurmurHash3 jest mniej więcej tak szybkie, jak tworzenie ciągów z tablicy bajtów i jest dwa razy szybsze, jeśli dasz mu tablicę bajtów.
Sprawdzanie poprawności jest regularnie eliminowane przez kompilator JIT, jeśli po prostu starasz się go poinformować, że nie przekraczasz limitów. –
@MarkoTopolnik - Oczywiście, ale to, czy jest całkowicie (lub dostatecznie) wyeliminowane w jakiejkolwiek konkretnej implementacji algorytmu, nie jest pewne. (Na przykład, kroki o nieregularnych rozmiarach często go mylą.) Stąd potrzeba benchmarkingu, zwłaszcza, że MurmurHash jest już dość szybki. –
Zdecydowanie test porównawczy, tak. Ale zwykle można dodać trochę poprawek do pętli, co zapewni kompilator JIT, że nie przekroczycie limitu. Takich jak wstawienie pozornie redundantnej '&& index
Czego sprawdzonych do tej pory? Szybkie wyszukiwanie ujawnia to: https://github.com/jpountz/lz4-java –
Cóż ... Jeśli potrzebujesz czegoś podobnego do MurmerHash, ale szybciej, możesz spojrzeć na CityHash. CityHash jest około 2x szybszy, ale uważaj, że jest pod aktywną rafinacją i nie jest jeszcze zalecany do użytku produkcyjnego. Szmer jest wystarczająco szybki i ponieważ jest używany w wielu popularnych projektach, ma wydajne i dopracowane implementacje w różnych językach, więc co jest nie tak z pozostaniem w MurmurHash na teraz? –
@MarkoTopolnik Tak ... Pytanie OP nie oznacza dużego wysiłku, ale 'lz4-java' jest implementacją' lz4', która jest algorytmem "kompresji", a nie 'Hashingiem '. –