4 fach verkettete listen?
-
oder man speichert nicht nur das vorige und das nächste element sonder auch das vor-vorige und das 2t-nächste? wäre etwas seltsam, aber es gibt vieles auf dieser welt... kann mir nicht wirklich vorstellen wozu sowas gut sein sollte
geloescht
-
sexist schrieb:
gibts sowas??
im prinzip nicht. genau wie schon gesagt, sind listen eindimensional und mehr als vor und zurück ergibt keinen sinn.
aber für manche sachen mag man dann doch mehr. zum beispiel skip-lists.
-
vhlib::skiplist<T>
-
was haben denn skip lists gegeüber maps für vorteile?
-
schau dir obigen Link mal an, das gibt ne ziemlich gute Idee, was Skiplists können udn was nicht.
-
pumuckl schrieb:
schau dir obigen Link mal an, das gibt ne ziemlich gute Idee, was Skiplists können udn was nicht.
suchen nach schlüsseln in logarithmischer zeit(hab ich shcon vor meinem letzten beitrag gelesen).
und? das können maps auch. haben aber dafür keine so üblen probleme beim einfügen von neuen elementen
-
otze schrieb:
und? das können maps auch. haben aber dafür keine so üblen probleme beim einfügen von neuen elementen
sag nicht maps, wenn du avl-trees meinst.
maps können mit skip-lists implementiert sein.
weiter antworte ich nur, falls die frage klar ist, denn ich weiß, wo man skip-lists verwenden kann.
-
Man verwendet mehrfach verkette Listen z. B. um Relationen dazustellen. Ein Schulbuchbeipiel ist eine Liste, die die Bewohner eines Gebietes darstellt. Um weitere Realtionen wie "ist verwandt mit" oder "ist Nachbar" von oder "ist kunde von" darszustellen, kann man weitere Listen einbauen. Der Vorteil ist dann, dass man anhand solcher Listen mit Funktionen durch den Datensatz "wandern" kann und so weitere Informationen (z. B. "Durchschnittseinkommen von Kunden von" erstellen kann). Eine andere Anwendung sind z. B. sog. Bricking-Algorithmen. Man hat einen Satz von Punkten in einem Raum un muss sie zunaechst nach der Position sortieren, dass man nur die unmittelbare Nachbarschaft (geometrisch) sehen moechte. Dann ist eine Loesung ein mehrfach-verkette Liste, die die geometrischen Realtionen von sog. "Bricks" (Kuben) beschreibt. Eine Declaration sieht dann etwa so aus:
class SingleBrick { private: int iPos_x, iPos_y, iPos_z; Vector_3d clCorner_0, clCorner_1; SingleBrick *pNext_plus_x, *pNext_minus_x, *pNext_plus_y, *pNext_minus_y, *pNext_plus_z, *pNext_minus_z; [...]PS: Vector_3d ist eine kl. Klasse zur Administration x-y-z-Werten.
-
Aber wozu skiplisten? wenn ich einen avl-tree(danke volkard für begriffsverbesserung) benutze hab ich wesentlich bessere einfüge zeiten bei gleicher such geschwindigkeit.
-
otze schrieb:
Aber wozu skiplisten?
wenn ich einen avl-tree benutze hab ich wesentlich bessere einfüge zeiten bei gleicher such geschwindigkeit.wie finde ich beim avl-tree zum nächsten nachbarn? teuer, gell? bei skip-lists immer in O(1).
skip-lists sind nicht da, um oft einzufügen und zu löschen, sondern um wenig einzufügen und zu löschen und oft zu suchen. um genau zu sein, um viel drinherumzulaufen.
und skip-lists sind was für profis. wie hashtables. nur noch viel seltener nütztlich. bei fehlverwendung bremsen sie nur. ich gehe nicht von perfekten skip-lists aus, sondern von welchen, die gerademal das durchlaufen ein wenig beschleunigen, weil sie manchmal größere sprünge erlauben. sagen wir mal in meinem 3d-weltraum-shooter, wo die landschaftskachel-beschreibungs-knoten in ner skip-list hängen. ok, nach 2 dimensionen, aber das ist egal. nomalerweise, fast immer, ja sogar ganz richtig immer gehe ich immer von einer kachel auf die nachbarkachel. also doppelt verkettete liste. nur manchmal kann ich beamen, da will ich mir, weil die welt 2^20 kacheln breit und lang ist, manchmal einen größeren sprumg geben. ich füchte, da gewinnen skip-listen jeden vergleich (außer direkt gegen arrays). also ich sehe in den skip-listen nur leicht aufgepeppte verkettete listen. keinen baum-ersatz, nichmal konkurrenz.
-
skip-lists sind nicht da, um oft einzufügen und zu löschen, sondern um wenig einzufügen und zu löschen und oft zu suchen. um genau zu sein, um viel drinherumzulaufen.
ich frage mich grad nur, ob ein vector so eine skiplist nicht in fast jedem bereich schlagen würde(jetzt wo ich ihr anwendungsgebiet kenne):
Klar, sortieren tut der vector nicht automatisch, aber da wir nur Einfügen wollen, wenn es sich nicht vermeiden lässt, ist das eher nebensächlich. Sortiert man halt einmal nach dem Einfügen den kompletten vector. Naja, wenigstens sind die sortier algorithmen auf vectoren ordentlich schnell.
Iterieren kann der Vector von haus aus, dank random access kann man auch soviel drin rumspringen wie man will. Da hängt er jede Skiplist ab
Der einzige nachteil an dieser konstruktion ist, dass man sich nen such algorithmus basteln muss, aber auch da kriegt man schnell sehr schöne ergebnisse.
-
otze schrieb:
ich frage mich grad nur, ob ein vector so eine skiplist nicht in fast jedem bereich schlagen würde(jetzt wo ich ihr anwendungsgebiet kenne)
irgendwas wird's schon geben, wo skip-lists gewinnen. vielleicht, wenn die einfügungen ein wenig häufiger sind, so daß vector zu langsam wird, aber nicht häufig genug, daß der baum gewinnen würde?
vielleicht wollen wir hin und wieder zwei listen zusammenführen (wie bei listen üblich in O(1)).
-
volkard schrieb:
vielleicht wollen wir hin und wieder zwei listen zusammenführen (wie bei listen üblich in O(1)).
O(1) kriegste nicht hin. zwei sortierte listen zusammenzufügen sodass die neue liste wieder sortiert ist, verlangt doch ein bischen mehr arbeit.
-
skip-listen haben noch ne feine eigenschaft. nach einfügen und löschen von elementen sieht die liste genauso aus wie vorher. skiplisten können also nicht durch häufiges einfügen und löschen degenerieren.