Skip Liste



  • Ich habe gerade - als ich was über hash maps nachlesen wollte auch von Skip Listen gelesen...
    Sind diese wirklich verbreitet oder eher theoretischer Natur?
    Wie geht man in der Praxis mit der Höhe um? 2x heap-allokation(einmal für das objekt und einmal für die zeiger-liste) oder nimmt man für die zeiger ein array mit einer bestimmten - konstanten - Größe?

    bb



  • Habe in freier Wildbahn noch keine Skiplist gesehen. Aber ich habe mal eine gebaut, bevor ich wußte, daß es sowas gibt. Und zwar kann die was bringen, wenn man sie eben nicht bis oben hin verwirklicht, dann könnte man ja gleich einen Baum nehmen, schätze ich. Die Liste wurde fast ausschließlich als queue verwendet, aber manchmal wollte ich auch ein weinig reinsuchen, und mit den schnellen Zeigern auf Ebene zwei und drei konnte ich 10-mal und 100-mal so schnell wie normal durchrennen.
    Die Variable Größe des Verknüpfungszeigerfeldes macht man im Falle einer randomisierten oder unausgeglichenen Skiplist wohl am besten mit sowas: http://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html
    Im Falle einer ausgeglichenen Skiplist sollte man wohl in jedem Knoten für die maximale Höhe vorallokieren.



  • Danke : >


Log in to reply