Schnelle HashTable

[Didelphodon]

's wär mal Zeit für 'ne "native" Purebasic Hashtable Library.

[Froggerprogger]

Hashtables werden ja meist in zeitkritischen Anwendungen verwendet. Leider sind gerade Hashtables besonders dann langsam, wenn sie allgemein gehalten sind. So lohnen sie sich oft erst ab vielen hundert, oder tausenden Elementen. Es macht z.B. einen Geschwindigkeitsunterschied, ob die Maximalanzahl im Vorfeld bekannt ist, oder ob der Table ggf. mitwachsen soll, oder ob man bereits diverse Eigenschaften der zu verwendenden Keys kennt (z.B. fortlaufende IDs), etc. und so die Hashfunktion vereinfachen und festcoden kann.

Wenn, dann würde PB (wie auch andere Sprachen) nur einen sehr allgemein gehaltenen Hashtable bieten, der sich eben erst ab einer gewissen Anzahl Elemente lohnt. Aber trotzdem wär das super!

Dabei kann Hashing in konkreten Szenarien sogar bei sehr wenigen Elementen schneller sein, als bspw. lineare Suche im Array. Siehe hier:

http://www.purebasic.fr/english/viewtopic.php?t=34284

Dort findet sich ein Hasharray (bestehend aus ein paar Variablen und Makros), das maximal #N (mit #N Zweierpotenz) Elemente halten kann, die Keys ein Integerwert sind, deren Differenzen zueinenander möglichst oft teilerfremd zu #N sind (z.B. wenn man wie dort fortlaufende IDs als keys nimmt, oder allgemein zufällige keys nimmt). Es wird Hinzufügen, Suchen und Löschen unterstützt. Das ganze ist sogar bei 16 oder 32 Elementen in Zugriffen anhand ID deutlich schneller, als die Elemente in einem Array zu halten und dieses linear zu durchsuchen. Aber es lässt sich so bspw. nicht auf Strings übertragen, das Array wächst nicht mit und die Größe wird zur Kompilezeit festgelegt, und man kann relativ leicht böse key-Kombinationen erstellen (z.B. nur Vielfache von #N), die den Hashtable dann ausbremsen und langsamer als Alternativen machen würden.

Ergo: Gerade bei Hashtables zeigt sich wie oft der gegenläufige Zusammenhang von Speed zu Anwendungsbreite. Eine konkrete optimale Lösung ist dann handgemacht.

[Little John]

Eine konkrete optimale Lösung ist dann handgemacht.

Ja, aber das ist nur was für mindestens schon fortgeschrittenerere Programmierer.
Für alle anderen wären eingebaute Hashtables schon schön (wie Du ja auch schreibst). In der Dokumentation könnte ja darauf hingewiesen weren, dass im Einzelfall spezielle Hashtables evtl. schneller sind.

Gruß, Little John

[inc.]

Hier eine Hashtabelle mit quadratischer Sondierung!
Zudem wird sie autom. Erweitert, wenn sie über die Hälfte gefüllt ist, etc.
Es gibt zudem wahlweise diverse Hashalgorhythmen, welche zur Auswahl stehen.

http://www.purebasic-lounge.com/viewtop ... 5177#55177

Da diese Tabelle noch getestet werden muss, wäre das hier doch die Gelegenheit.

Grüße - momentan aus Caracas / Venezuela
Inc.

[DrShrek]

Hier eine Hashtabelle mit quadratischer Sondierung!
Zudem wird sie autom. Erweitert, wenn sie über die Hälfte gefüllt ist, etc.
Es gibt zudem wahlweise diverse Hashalgorhythmen, welche zur Auswahl stehen.

http://www.purebasic-lounge.com/viewtop ... 5177#55177

Da diese Tabelle noch getestet werden muss, wäre das hier doch die Gelegenheit.

Grüße - momentan aus Caracas / Venezuela
Inc.

@inc,

Getestet werden ist ein 'grosser' Begriff...um was geht es Dir: Geschwindigkeit, Stabilität, oder 'Benutzbarkeit'?
Am besten einen eigenen Tread deswegen aufmachen...sonst findet das bald keiner mehr...