Jak zaprojektowałbyś funkcję idealnego skrótu?

Question

Domeną zainteresowania jest dopasowywanie ciągów znaków. Załóżmy, że mam taką strukturę.

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

} StringArray 

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

W tablicy znajduje się stała liczba ciągów. Są one zakodowane jak na przykładzie. Jeśli tabela ulegnie zmianie, konieczna będzie ponowna ocena jakości funkcji skrótu.

Chcę zastosować funkcję skrótu do napisu, a jeśli ciąg pasuje do jednej w tablicy, , a następnie wywołaj funkcję. Do tego potrzebna jest idealna funkcja skrótu. Żadne kolizje nie są dozwolone. Celem wymagającego skrótu jest uzyskanie O (1) wydajności podczas wyszukiwania.

Jakie masz pomysły dotyczące projektowania funkcji?

Answer 1

Zobacz stronę gperf domu.

Answer 2

Można używać map

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

Patrz:

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

Jeśli kolizje są absolutnie niedozwolone, jedyną opcją jest, aby śledzić każdy ciąg w bazie danych, co nie jest chyba najlepszym sposobem udać się.

Co mogę zrobić, to zastosować jeden z istniejących wspólnych silnych algorytmów mieszających, takich jak: MD5 lub SHA. Wokół są miriadki próbek, na przykład jeden: http://www.codeproject.com/KB/security/cryptest.aspx

Answer 5

Cóż, nie ma idealnej funkcji skrótu.

Masz kilka, które minimalizują kolizje, ale żadne ich nie eliminuje.

nie może doradzić jedno ale: P

EDIT: Rozwiązanie nie może być znalezienie idealnego funkcji skrótu. Rozwiązaniem jest świadomość kolizji. Zwykle funkcja mieszająca ma kolizje. To oczywiście zależy od zbioru danych i rozmiaru wynikowego kodu skrótu.

Answer 6

Użyj zbalansowanego drzewa binarnego. To zachowanie WIEM jest ZAWSZE O (logn).

Bardzo nie lubię haszysz. Ludzie nie zdają sobie sprawy z tego, ile ryzyka podejmują z ich algorytmem. Przeprowadzają niektóre dane testowe, a następnie wdrażają je w terenie. NIGDY nie widziałem wdrożonego algorytmu mieszania, który jest sprawdzany pod kątem zachowania w terenie.

O (log n) jest prawie zawsze akceptowalny zamiast O (1).

Answer 7

Podsumowanie zawiera zarówno C, jak i C++. Którego szukasz? C i C++ są dwoma odrębnymi językami i różnią się znacznie pod względem obsługi łańcuchów i struktur danych (a fakt, że te C działają w C++, nie zmienia tego).

Dlaczego, konkretnie, chcesz uzyskać idealną funkcję skrótu? Czy chcesz powiązać ciąg z funkcją i pomyśleć, że byłby to dobry sposób na zrobienie tego? Czy to jest zadanie domowe? Czy masz powód, aby nie używać mapy <> w C++? (Lub unordered_map <> jeśli jest dostępny?)

Jeśli potrzebujesz idealnego skrótu, jakie są ograniczenia na strunach? Czy będzie jakiś ustalony zestaw, który chcesz wysłać? A co z ciągami, które nie pasują do jednego z zestawów? Czy chcesz zaakceptować trafienia z losowych ciągów lub czy liczba przychodzących łańcuchów jest ograniczona?

Jeśli możesz edytować swoje pytanie, aby dołączyć takie informacje, możemy być bardziej przydatni.

EDIT (w odpowiedzi na dwa pierwsze komentarze):

OK, powinniśmy spojrzeć na rozwiązania C, ponieważ przypuszczalnie chcesz to zarówno dla dysku C i C++ pracy. Prawdopodobnie chcesz występu, ale czy przetestowałeś? Jeśli mamy do czynienia z ciągami wchodzącymi do systemu I/O, czas prawdopodobnie skróci czas wysyłki.

Spodziewasz się arbitralnych ciągów znaków. Oczekiwanie na doskonałą funkcję skrótu, która pozwoli uniknąć kolizji z losowych danych, jest nieco spora, więc musisz to rozważyć.

Czy brałeś pod uwagę trie? Może być bardziej wydajna niż idealna funkcja skrótu (lub nie musi być), powinna być dość łatwa do implementacji w C, i pozwoli uniknąć problemów z ponawieniem listy wysyłanych łańcuchów lub możliwych kolizji.

Answer 8

Końcowym rezultatem tego ćwiczenia było

• Steal szereg zorientowanych ciągów funkcji mieszających się siatki.
• Zbuduj rodzaj klasy fabrycznej, która przetestowała każdą z funkcji w zestawie danych z zakresem wartości operatorów mod, szukając najmniejszego idealnego skrótu, który działa z tą funkcją.
• Ten konstruktor domyślny klasy fabrycznej zwraca ciąg znaków, który reprezentuje zbiór argumentów, które po użyciu wybiera poprawną funkcję haszowania, oraz rozmiar modu, aby uzyskać idealny skrót, który wymaga najmniejszej ilości pamięci.
• pod normalnym użyciem, po prostu tworzysz instancję klasy za pomocą zwróconych argumentów, a klasa umieszcza się w stanie roboczym z pożądanymi funkcjami.
• Ten konstruktor sprawdza, czy nie ma kolizji i przerwie, jeśli są.
• W przypadku, gdy nie znaleziono idealnego skrótu, ulega on degradacji do wyszukiwania binarnego w posortowanej wersji tabeli wejściowej.

Dla zestawu tablic, które mam w mojej domenie, wydaje się, że działa bardzo dobrze. Ewentualną przyszłą optymalizacją byłoby wykonanie tego samego rodzaju testów na podciągach danych wejściowych. W przykładowym przypadku pierwsza litera każdego imienia muzyczki wystarczy, aby je odróżnić. Wówczas trzeba będzie zrównoważyć koszt rzeczywistej funkcji hashującej z użytą pamięcią.

Dziękuję wszystkim, którzy wnieśli swoje pomysły.

Zło