✔ Verkettete Listen - Element schneller finden

[thekiller]

Moin,

verkettete Listen sind ja, wenn man bei einem Durchgang auf alle Elemente in folge zugreifen möchte ähnlich schnell als wenn man mit Arrays arbeitet.
Nur wenn man auf einzelne Elemente der Liste zugreifen möchte wirds lahm, weil man ja bekanntlich erst alle Elemente durchgehen muss, bis man das gewünschte gefunden hat.

Gibt es da Tricks wir man dass ganze beschleunigen kann?
Ich habe gedacht ein Array mit den Pointern zu jedem Element anzulegen. Wenn man dann z.B. genau weiß, dass das 5. Element das gewünschte ist dann einfach auf z.B. Liste[4] zugreifen. Wenn die Liste sich aber ständig ändert ist es auch wieder schlecht, da man dann ja jedesmal das Array reorganisieren müsste.

MfG Manuel

 

[sheel]

Hi
Lassen sich die Objekte anhand ihrer Werte irgendwie in bestimmte Gruppen aufteilen?
Am Besten so, dass jede Gruppe im Durchschnitt ungefähr gleich viel Elemente bekommt?

Man könnte dann zB so eine Art Hashliste machen.
Also einfach in zwei Ebenen aufteilen, eine Liste aus Listen.

Am Beispiel Menschennamen: macht man eine Liste aus 26 "Unter"-Listen.
Wenn man einen Mensch namens Andreas adden will, steckt man ihn anhand seines Anfangsbuchstaben in die erste Liste. Ein Christian kommt durch C in die Dritte usw...
Wenn man jetzt einen bestimmten Namen sucht, muss man nur noch eine der 26 Listen durchsuchen.
(Wenn man sowieso immer 26 Buchstaben hat, kann man als Überstruktur auch gleich ein Array nehmen, aber eine Liste macht je nach gespeicherten Daten auch Sinn.)

Soviel zum Prinzip.
Wie gut das die Performance steigert, hängt davon ab, ob du eine gute Verteilungsmethode für deine Daten findest. Sollte eben möglichst gleichmäßig aufteilen.
Wenn man will, kann man das Ganze noch um eine/mehrere Stufen erweitert (Hashlist aus Hashlisten aus Daten...)

Geht alles eben nur bei Daten, die man anhand ihrer Werte irgendwie gruppieren kann.

Nachteil am System: Die Reihenfolge, in der Elemente eingefügt werden, bleibt nicht erhalten.
Wenn das wichtig ist, gäbe es schon auch passende Ansätze aus diesem System, die aber im Performancegewinn nicht mit der "zerrüttelten" Hashlist mithalten können.

Gruß

 

[deepthroat]

Hi.

Man könnte natürlich einfach eine andere Datenstruktur verwenden wie sheel im Grund vorgeschlagen hat. Bäume gibt es z.B. in vielen Varianten mit ähnlichen Eigenschaften wie Listen.

Ganz einfach wäre die Verwendung eines Cursors.

Gruß

 

[thekiller]

Hi danke euch beiden für die Antworten. Klingen ganz gut. Mal schauen ob ich davon was implementieren kann =)

MfG Manuel