sortieren und suchen in array mit records

[ThorsteinB]

Hallo,

mit meinem Programm stoße ich solangsam an meine Grenzen, da ich Arrays mit Records bilden muß und diese sollten sortiert sein, um Duplikate zu finden bzw. um Elemente nach ihrer Priorität zu selektieren.

Leider ist in meinem Buch "Learning Pascal in 3 days" ausgerechnet das Kapitel zu verketteten Listen besonders fehlerhaft. Und die Beispiele dich ich bisher im Netz finde sind für einen Anfänger wie mich nicht wirklich lesbar. Manche raten sogar zu einer doppelt verketteten Liste.

Könnte sich bitte jemand von Euch die Mühe machen, um in einem verständlichen Beispiel zu zeigen, wie sowas funktioniert?


Freundliche Grüße,
Thorstein

[Socke]

Hallo,

willst du Records in einen Array packen oder (einfach/doppelt) verkettete Listen erstellen? Das sind an sich zwei grundsätzlich unterschiedliche Strukturen.

[ThorsteinB]

Ich bin mir selbst nicht ganz sicher was ich will, da mir schlichtweg der Überblick fehlt.

Als Ausgangsbasis habe ich Records (Wort, Wortart: String; Frequenz, Klasse: Integer) die (bisher) in einem Array abgelegt sind. Am Ende stehen ca. 10000 Datensätze zur Verfügung und der Zugriff darauf sollte möglichst schnell sein. Jemand meinte deshalb, dass es sinnvoller wäre, die Records in einer doppelt verketteten Liste zu speichern.

Nur habe ich in beiden Fällen keine Ahnung, wie ich das sortieren und suchen implementieren könnte.


Thorstein

[Scotty]

Es gibt sehr viele Möglichkeiten, dein Problem zu lösen.

1. TList (die hat dann eine Sort-Funktion; -> New(Zeiger auf Record), Add())
2. TStringList (die Zusatzinformationen als Objects[] speichern)
3. Eigenen Bubblesort-Algorithmus programmieren

Man speichert Daten eher nicht in dynamischen array of <records>. Das ist nicht sonderlich flexibel, fehleranfällig und Standardfunktionalität fehlt.

[Keifor]

Hallo,

Wichtiger wäre es dann doch erstmal festzulegen, wie der Zugriff geschieht und welche Daten eindeutig sind. (Anwendungsfälle)
Bspw. soll für ein Wort die Klasse/Frequenz/Wortart gesucht werden?
Sind Wörter eindeutig, oder gibt es Klassen/Wortarten mit gleichen Wörtern (bzw. welche Felder ergeben zusammengesetzt ein eindeutiges Datum welches nicht doppelt vorkommen darf.)?
Kurz, auf was soll zugegriffen werden, was soll zurückgeliefert werden, gibt es noch spezielle Anwendungen (durchlaufen, alles Datensätze [sortiert] ausgeben)? Danach sollten die Datenstrukturen gewählt werden.

Für einfaches Ablegen der Datensätze und einfachen Durchlauf sowie Zugriff über einen Index bieten sich Arrays an.
Für Einfügen/Löschen/Durchlauf oder auch Umsortieren etc. kann man gut Listen verwenden. Doppelt verkettete sind dabei einfacher in der Nutzung aber komplexer in der Implementation und verbrauchen mehr Speicher. Erlauben aber Löschen und einfachen Rückwärts-Durchlauf.
Sortieren z.B. nach einem Integer Schlüssel ist i.d.R. einfacher auf Arrays, sofern das Sortieren in einem Schwung (nach dem einfügen aller Datensätze gemacht wird), bei Sortierung während des Einfügens sind Listen wiederum besser.
Für Zugriffe über Zeichenketten gibt es z.B. auch effizientere Datenstrukturen wie Hashtabellen.
Bei Sortierung nach Frequenzen z.B. wäre eine Prioritätsliste/ein Baum/ein Heap angebracht.

Fpc/Lazarus haben nebenbei noch ein paar Datenstrukturen die sich für große Anzahl an Datensätzen und Zugriffe über Zeichenketten/Zahlenschlüssel eignen (10000 ist eher mittlerer bis unterer Bereich ) wie AVL Baum oder Hashtabellen Implementation.

Oder anders ausgedrückt, es gibt keine "Alles könnende Datenstruktur". Es gibt verschiedene einfach bis sehr komplexe Datenstrukturen die sich für Einfügen/Löschen/Suchen/Durchlaufen/Sortieren eignen. In der Regel gehen aber nur ein paar der Operationen effizient, andere dagegen mit hohem Rechenaufwand oder sind nicht möglich. Erst festlegen was benötigt wird, dann Datenstrukturen auswählen.

-- Nachtrag
@Scotty: von Bubblesort würd ich abraten. Bubblesort läuft im schlechtesten Falle in Quadratischer Laufzeit und ist eher ein netter Algorithmus für die Lehre. Nichts für praktische Anwendung außer man wartet gerne auf Resultate
TList/TFPList sollte auch eine effizientere Sortierung erlauben.

[MAC]

was willst du genau damit machen.
Das muss man sich immer als erstes fragen.
Danach - wird 1 mal geschrieben und danach immer abgefragt oder wie ist das verhältnis von lesen schreiben. z.b. wenn man nur alle 5 minuten einen eintrag hinzufügt und alle 3 millisekunden einen sucht kann das sortieren ruhig langsam sein wenn das suchen danach schneller geht.

Wenn du das mit arrays machst ist die einfachste methode

Code: Alles auswählen

for i := 0 to high(myarray) do
begin
if myarray[i].wort = gesucht then 
begin
result := i;
exit;
end;
end;

gib dir dann zurück an welcher position das gesuchter wort ist. nachteil: das exit hört auf sobald etwas gefunden ist, hast du also ein wort zweimal drinn findet es nur das erste.

Code: Alles auswählen

result.x := nil;
for i := 0 to high(myarray) do
begin
if myarray[i].wort = gesucht then 
begin
setlength(result.x,length(result.x)+1);
result.x[high(result.x)] := i;
end;
end;

währe dort angebracht. Result ist hier nicht vom typ integer sondern ein record, weil als result kein array rauskommen darf. heißt

Code: Alles auswählen

result = record
x:array of integer;
end;

wenn du das jetzt sortieren willst empfehle ich erstmal einzubauen:

Code: Alles auswählen

for i := 0 to high(myarray)-1 do
begin
if myarray[i].wort = '' then continue;
if byte(myarray[i].wort[1]) > byte(myarray[i+1].wort[1])  then
   begin // vertauschen
   puffer := myarray[i+1];
   myarray[i+1] := myarray[i];
   myarray[i] := puffer;
   end; 
end;

mit dem [1] nehme ich das erste Zeichen des wortes, deshalb wird vorher auch geprüft ob das wort überhaupt zeichen hat. sonst wird der teil übersprungen
byte wandelt ein buchstabe in seinen ASCII wert um. Alle Buchstaben sind ja nichts anderes als Zahlen. und zahlen lassen sich besser vergleichen
puffer ist vom gleichen record wie dein array. dort wird nur kurz etwas zwischengespeichert.
Dieser Algorythmus ist nur sehr bedingt zu gebrauchen und sollte mehrmals durchgeführt werden, weil er sonst kein erfolg bringt. außerdem sollte er oft vom 1 bis high durchgelaufen werden und es wird i und i-1 geprüft werden ...
Er ist also nicht effizient, aber besser als nichts. Verbessern darfst du ihn natürlich.

es bietet sich jetzt an, bei großen mengen erstmal zu schauen, wenn ich das wort "Welt" suche mit welchem buchstabe es beginnt. und mir einen 2ten array erstelle der sagt: ab wo a beginnt, wo b beginnt,... ! dann muss ich nicht mehr von 0 bis 10000 suchen, sondern mit glück nurnoch von 8000 - 9000.

[ThorsteinB]

Super, vielen Dank an MAC und Keifor, aber natürlich auch an Scotty und Socke.

Das Hauptproblem liegt vielleicht darin, nichts falsch bzw. alles richtig machen zu wollen. Denn voll automatisiert läuft meine Anwendung ca. 12-14 Stunden um die Wort-Datenbank anzulegen. Und dabei stimmt leider die Qualität nicht. Deshalb muß ich nun alle 10000 Wörter von Hand prüfen, was vermutlich eher Wochen statt Tage dauern wird. Wie die Daten gespeichert werden ist also schon von großer Bedeutung.

Aber durch Eure Vorschläge ist mir aufgefallen, dass ich doch einen einfacheren Weg nehmen kann, als den über doppelt verkettete Listen

Nochmals Dankeschön!


Freundliche Grüße,
Thorstein

[Teekeks]

weil als result kein array rauskommen darf.

Wie kommst du darauf?

Code: Alles auswählen

type TIntArray=array of Integer;
//...
function Foo():TIntArray;
//...

[MAC]

Ich habe nur bemerkt das

Code: Alles auswählen

function test:array of Integer;

nicht geht.
Auf die idee mit type kam ich nicht.
jetzt weis ich es...

[Teekeks]

Wenn man TBoundArray aus der objpas.pas nimmt, brauch man nicht einmal ein type.
ein function foo:array of integer; kann ja nicht gehen weil du ja einen Typen angeben musst und nicht Definieren
Aber ich weiß was du meinst.

Gruß Teekeks

[carli]

Super, vielen Dank an MAC und Keifor, aber natürlich auch an Scotty und Socke.

Das Hauptproblem liegt vielleicht darin, nichts falsch bzw. alles richtig machen zu wollen. Denn voll automatisiert läuft meine Anwendung ca. 12-14 Stunden um die Wort-Datenbank anzulegen. Und dabei stimmt leider die Qualität nicht. Deshalb muß ich nun alle 10000 Wörter von Hand prüfen, was vermutlich eher Wochen statt Tage dauern wird. Wie die Daten gespeichert werden ist also schon von großer Bedeutung.

Das macht Sortieren macht aber die Datenbankschicht für dich.
Du indizierst die Felder, nach denen sortiert werden soll und demnach können auch die Daten sortiert abgefragt werden.