Liste mit wahlfreiem Zugriff möglich?

timbo

Hi,

ich bin gerade dabei eine Aufgabe zu lösen, bei der ich einen Index aus einem Text erstellen soll. Habe soweit jetzt alles realisiert bekommen aber nun will ich das Ding noch etwas optimieren.

Wenn ich ein Wort finde, muss ich es sortiert in eine Liste einfügen. Bisher gehe ich die liste linear durch und schaue, wo ich das Element einfügen muss bzw. ob es schon vorhanden ist. Dazu vergleiche ich in jedem Schritt den aktuellen Knoten der Liste mit dem einzufügenden.

Mein Ansatz wäre nun, dass ich ähnlich wie bei der Binärsuche (devide and conquer) durch den Baum gehe und so sehr schnell ( ~O(log(n) ) die Stelle finde, an der ich einfügen muss.

Dazu muss ich aber einen wahlfreien Zugriff (über einen Index, ähnlich einem Array) auf die Liste haben. Da ich die Listenfunktionen selbst implementieren muss und kein STL verwenden darf, bekomme ich leider keinen wahlfreien Zugriff auf einen Knoten.

Ich habe jetzt versucht bei jedem Einfügevorgang ein temporäres Array anzulegen welches alle bisherigen Pointer auf die Listenknoten enthält. Allerdings bringt das keine wirklichen Vorteile, da ich das Array ja bei jedem Vorgang neu anlegen muss. Ein vector wie in der STL wäre hier genau das richtige denke ich. Lässt sich sowas irgendwie "nachbauen".

Vielleicht gibt es ja auch noch bessere Methoden den Index abzulegen. Bin für jeden Tipp dankbar.

Gruß, Tim

viande

Bei Listen lässt sich auch nur die lineare Zugriffszeit vermeiden, wenn man Arrays verwendet und das führt dazu, dass man eine maximale Größe hat. Außerdem musst du dich sozusagen selbst um die Speicherwverwaltung kümmern, weil im Array dann durch Löschen Lücken entstehen können. Ver Vorteil ist aber gegenüber dem Array, dass du nicht das ganze immer hin und herschieben musst.
Du könntest das dann so machen:

class List
{
   Elem elems[1024]; //"Arrayliste"
   Elem * first;  //erstes Element
   Elem * last;  //letztes Elemént
};
class Elem
{
   T value; //Wert (bei komplexeren Datenstrukturen als Basisdatentypen ->
            //Pointer)
   Elem * pred; //vorheriges ELement
   Elem * succ; //nächstes Element
};

So, damit kannst du vielleicht was anfangen
Wenn dann dein Array überläuft, kannst du ja dynamisch neuen Speicher allokieren und dann die Liste dort hinein kopieren (dabei aber immer mehr allokieren, als nur ein neues Element ;))

Shade Of Mine

Warum nimmst du eine Liste wenn du wahlfreifen zugriff brauchst? Das ist irgendwie die falsche Datenstruktur für das Problem

timbo

Hi,

danke für eure Hinweise. Das ich die "falsche" Datenstruktur habe ist mir auch schon aufgefallen ;-). Ich wollte es aber erstmal so probieren, damit ich erstmal eine funktionsfähige Lösung habe. Es hätte ja auch sein können, dass es irgendeinen kleinen Trick gibt, mit dem sich das hätte lösen können. Beim genauerem Nachdenken ist es aber auch logisch, dass es mit einer "normalen" Liste nicht geht.

Ich habe mir gerade einen interessanten Artikel über Bäume durchgelesen (Binärbäume, AVL Bäume, etc.). Für einen Index solch eine Struktur sicherlich am sinnvollsten.

Wen es Interessiert:
http://www.cs.fhm.edu/~schieder/programmieren-2-ss97/tree.html#section_19

Die Idee mit dem "dynamischen" Array ist natürlich auch was aber so optimal nun auch wieder nicht, da ich keine Speicher verschenken will/darf. Trotzdem danke für den Vorschlag.

Die Geschichte mit dem wahlfreiem Zugriff kam mir auch nur spontan in den Sinn, weil mein erster Gedanke Binärsuche in einer sortierten "Liste" war.

Ein Binärbaum ist aber auch eher nur für den Zugriff schneller als beim einfügen. Ich werde einfach mal ein wenig rumprobieren.

Vielen Dank für eure Hilfe!

Gruß, Tim

timbo

Hi,

falls es vielleicht irgendjemand interessiert. Ich habe mich nun mal durch die verschiedenen "Baumarten" durchgeforstet und habe rausgefunden, dass der B-Tree für meinen Einsatz am besten geeignet ist. Gerade für die Indizierung ist er gut geeignet und wir deshalb von vielen Datenbanksystemen und Dateisystemen zur Indexierung verwendet.

Für weitere Informationen empfielt sich:
- http://de.wikipedia.org/wiki/B-Baum (Erklärung des B-Baum)
- http://cis.stvincent.edu/swd/btree/btree.html (Erklärung des B-Baum und Implementierung)

Mit freundlichem Gruß,

Tim

viande

Wenn du dich für weitere Datenstrukturen interessierst und wie man diese Umsetztr, deren Einsatzmöglichkeiten etc., empfehle ich dir das Buch "Datenstrukturen und Algorithmen" von Ralf Hartmut Güting und Stefan Dieker aus dem Teubner Verlag. Das hat seit der 2. Auflage alle Beispiele in Java enthalten und ist somit für C++ Programmierer sehr gt geeignet. Außerdem ist es von Deutschen geschrieben und somit keine! (schlechte) Übersetzung
Ist alles recht anschaulich erklärt, wenn man allerdings auch die Mathematik darin (komplett)verstehen will, sollte man min. Abi haben. Ist für mich als 12 Klässler schon ziemlcih hart, geht aber grad noch so (Google und Wikipedia hilft :p). Ist aber nicht unbedingt nötig, da auch das Ergebnis am Schluss genannt wird und das ist das wirklich interessante für den Durchschnittsinformatiker.

Shade Of Mine

timbo schrieb:

Die Idee mit dem "dynamischen" Array ist natürlich auch was aber so optimal nun auch wieder nicht, da ich keine Speicher verschenken will/darf.

Sagt jemand mit 2*sizeof(void*) Bytes overhead pro element

timbo

Da hast du natürlich auch Recht aber nun hab ich ja die, für mein Problem, beste Lösung gefunden, bei der das Suchen schnell geht (O(log n)) und das einfügen auch (O(log(n)). Was will man mehr. Ist auch so ziemlich das erste mal, dass ich mit solchen Listen arbeite bzw. spezielle Funktionen (suchen, etc.) darauf anwenden will.

Danke nochmal für all eure Hilfe.