Przechowywanie string'ów w drzewie binarnym

Odpowiedz Nowy wątek
2011-09-22 14:43
Okkd
0

Witam

Przechowuję kilka tysięcy string'ów do których co chwilę są dodawane nowe, ale każdy musi być unikalny, dlatego przed każdym dodaniem zbiór musi zostać przeszukany pod kątem istnienia takiego samego napisu. Napisy mniej więcej mają długość kilka do około 30 znaków. Zależy mi na bardzo szybkim działaniu.

Nigdy nie miałem takiego problemu, ale domyślam się, że najlepszym rozwiązaniem będzie użycie drzewa binarnego. Jednak nie daje mi to spokoju, że zeżre to o wiele za dużo pamięci.

Skoro bajt może mieć wartość 0 - 255, to w każdym węzłu drzewa będzie trzeba przechować 256 wskaźników (pustych lub nie).

Jeżeli pierwsza część napisu nie będzie taka sama, to praktycznie przy każdym znaku trzeba będzie tworzyć nowy liść z węzłami zajmującymi 1 kb pamięci (256 * 4), więc zamiast tych kilkunastu bajtów każdy napis będzie zajmował 1 kb + kilkanaście b.

Może się myle.

Pozdrawiam.

To co opisałeś nazywa się TRIE i jest całkiem fajne, ale pytanie czy faktycznie aż tak zalezy ci na niskiej pamięci. Jeśli chodzi o szybkość to jakiś HashSet się tu lepiej sprawdzi pewnie. - Shalom 2011-09-22 21:29

Pozostało 580 znaków

2011-09-22 15:04
0

Drzewo binarne zawsze ma dwoje potomków - stąd właśnie nazwa. Mówisz o drzewach k-narnych.
a) nie musisz zakładać, że każda wartość z przedziału 0-255 jest prawidłowa (no chyba, że musisz?).
b) Możesz użyć drzewa binarnego

Jakie operacje chcesz wykonywać na tym zbiorze?

Pozostało 580 znaków

2011-09-22 15:27
0

IMHO drzewo binarne do tego celu jest złym wyborem. Do problemu słownikowego (bo na taki twój problem wygląda) najlepsza jest hash-table.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
Trie zwykle ma porównywalną wydajność z hash-table i nie ma ryzyka kolizji. - Zjarek 2011-09-22 16:10

Pozostało 580 znaków

2011-09-22 20:24
0

Spróbuj ze strukturą:

set<string> zbior;

Jeśli coś nie będzie działać, próbuj dalej (map, multimap, unordered_set, boost::bimap).


Szacuje się, że w Polsce brakuje 50 tys. programistów
edytowany 1x, ostatnio: vpiotr, 2011-09-22 20:26

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0