Anwenden von logischen (bitweise) Operatoren -Jetzt aber Byte-weise

[Hagen Reddmann]

Ähm, du berechnest den Hash jedesmal neu ?
Normalerweise berechnet man den Hash nur einmalig pro Element bei dessen Einfügen. Man speichert dann diesen Hash separat oder zum Element ab. Somit würde nun ca. 600.000 Hashberechnungen anfallen.

Der Hash des Elementes dient in einer Hash-Liste als Index in die Elemente-Liste an der das Element eingefügt werden muß. Allerdings in unserem Beipiel bringt uns das in keinster Weise weiter, leider.

Gruß Hage

[Torsten Grundke]

Hallo Hagen,

für die einzelnen Elemente berechne ich den hash nur einmal. Zur Prüfung ob ein untergeordnetes Element vorhanden ist, wollte ich dann den Hash des möglichen untergeordneten Elements mit Bytewert=1 berechnen und diesen Hash in der HashTabelle suchen. Wenn ein Eintrag gefunden wird muß dann noch geprüft werden ob es tatsächlich das gesuchte Element ist. Wenn ja wird der Hash mit Bytewert 2 berechnet und ein Element mit diesem Hashwert gesucht, ansonsten wird das nächste NullByte des Elements der gleichen Prozedure unterzogen.

Die Hashwerte sollten so in einem Array gespeichert werden, das der Hashwert direkt zum indizieren des Array's verwendet werden kann. Somit ist ein schneller Zugriff möglich. Jetzt habe ich alle Elemente die dn gleichen Hashwert ergeben. Nun müssen diese Elemente geprüft werden ob tatsächlich das gesuchte untergeordnete Element vorhanden ist.

Tschau

Torste

[Hagen Reddmann]

Ah. Erstens sollte die Hashfunktion ja auf direktem Wege einen bestimmten Zahlenwert an definiertem Index herausrechnen können. Das habe ich ja schon oben angedeutet. Und zweitens ist dieser Hashwert der Index in die Tabelle der gespeicherten Elemente. D.h. am gleichen Index=Hash sind alle identischen Elemente verwaltet. Somit muss der Hashwert nicht mehr in der Tabelle/Array gesucht werden.
Ok das ist aber soweit klar.
Das Problem entsteht nun aber an anderer Stelle. Wenn zu einem aktuellen Hashwert an Index 5 zB. eine Null eingerechnet wird dann würde man damit nicht die Elemente finden die eben auch an Index 5 eine Null haben.
Letzendlich würde die Gesamtkomplexität der nötigen Vergleiche trotzdem enorm höher sein als ein Trie. Denn bei Elementen mit 18 Werten müsste ein Hashalgo. denoch pro Elemente 18 mal eine Null reinrechnen, diesen virtuellen Hash in der Elementeliste aufsuchen und alle gefundenen Elemente denoch vergleichen. Beim Trie ist das anderes. Angenommen beim Iterieren im Trie wird an Werteindex 5 im Baum festgestellt das es keinerlei Nodes gibt die passen, so würden ALLE Elemente die zwar in in den Werte[0..4] identisch sind ausgeklammert. Somit hat man schon sehr frühzeitig mit einer einzigsten Vergleichoperation auf Byteebene eine ganze Latte von Elementen abgearbeitet. Dies ist der eigentliche Grund warum main Trie eben so verdamt effizient ist.

Z.b. wir haben im Trie[0] ein Element[x][1,3,4] und fangen an im Trie[1] nach Wert 1 zu suchen. Schon nach 2 Byte Vergleichen wissen wir ob es überhaupt Elemente[] im Trie[1] gibt die mit 1 beginnen. Sollte dies der Fall sein wird nun Werteindex 2 = Wert 3 gesucht. Nach ca. 3 Vergleichen wissen wir ob es Elemente mit [1,3....] im Trie[1] gibt. Alle Elemente mit [1,<> 3] haben wir in diesem Moment schon inklusive abgearbeitet.
Wir müssen die virtuelle Nullstelle nur als Einmal-Joker verwenden. D.h. solange im Vergleich der Nodes noch kein Null-Joker eingesetzt wurde sind die Elemente noch identisch. So bald ein Joker eingesetzt wurde, in meinem Source Difference = True, darf es keine Werte-Unterschiede mehr geben. Falls doch welche vorkommen kann man die Überprüfung der untergeordneten Nodes überspringen.

Gruß Hage

[Constantinus van der Kruijs]

Hallo<br><br>
Scheinbar habt ihr wirklich nichts besseres zu tun . Also ich habe den geposteten code noch ein wenig umgestaltet, damit ich eine variable anzahl von byte-spalten verwenden kann. Der nachfolgende output enthält infos über den gesamten vorgang der test-applikation. Das öffnen des datenbestands und das speichern der ergebnisse fallen logischerweise weg, sobald das modul in der eigentlichen applikation integriert wurde.<br>
<pre>
Datenbank geöffnet in: 12985.85 ms
Datensätze : 656377
Aufteilungen : 18
</pre><pre>
Speicher reserviert in: 546.36 ms
Laden der Datensätze... 81820.03 ms
</pre><pre>
Inserting : 1009.20 ms
</pre><pre>
Tree # : Count : NodeCount : Size : Free
0 : 0 : 1 : 4 : 0
1 : 0 : 1 : 4 : 0
2 : 0 : 1 : 4 : 0
3 : 0 : 1 : 4 : 0
4 : 0 : 1 : 4 : 0
5 : 0 : 1 : 4 : 0
6 : 0 : 1 : 4 : 0
7 : 0 : 1 : 4 : 0
8 : 64113 : 139055 : 557056 : 12
9 : 116049 : 266977 : 1069056 : 12
10 : 168752 : 386925 : 1548288 : 12
11 : 132001 : 319901 : 1282048 : 21
12 : 106000 : 217811 : 872448 : 9
13 : 50483 : 101712 : 409600 : 10
14 : 15325 : 34366 : 139264 : 3
15 : 3049 : 7952 : 32768 : 3
16 : 552 : 1646 : 8192 : 0
17 : 46 : 168 : 4096 : 5
18 : 7 : 35 : 4096 : 9
</pre><pre>
Werte count : 656377
Trials : 0
Memory used : 5926948
Memory unused : 20720
</pre><pre>
Speedtest: 243.47 ms, Found: 2059659
compare Trie # 0 with # 1 0.00 ms
compare Trie # 1 with # 2 0.00 ms
compare Trie # 2 with # 3 0.00 ms
compare Trie # 3 with # 4 0.00 ms
compare Trie # 4 with # 5 0.00 ms
compare Trie # 5 with # 6 0.00 ms
compare Trie # 6 with # 7 0.00 ms
compare Trie # 7 with # 8 0.00 ms
compare Trie # 8 with # 9 207.97 ms
compare Trie # 9 with # 10 350.28 ms
compare Trie # 10 with # 11 407.99 ms
compare Trie # 11 with # 12 294.92 ms
compare Trie # 12 with # 13 232.46 ms
compare Trie # 13 with # 14 105.75 ms
compare Trie # 14 with # 15 27.99 ms
compare Trie # 15 with # 16 4.75 ms
compare Trie # 16 with # 17 0.61 ms
compare Trie # 17 with # 18 0.06 ms
</pre><pre>
Ermittle Atoms... 16113.53 ms
</pre><pre>
Speichere Children... 43683.20 ms
Speichere Parents... 26614.27 ms
Speichere Atoms... 30791.57 ms
</pre>
<br>
Ein weiteres beschleunigen des codes ist meiner ansicht nach nicht notwendig, da der vorgang lediglich beim öffnen und laden des datenbestands ausgeführt werden soll. Da ist es unkritisch, ob das ganze 3s oder 2,5s dauert ( @hagen: nichts für ungut - der code ist schon äusserst effizient ).<br>
<br>
Grüße