|
Registriert seit: 11. Mär 2003
1 Beiträge
|
11. Mär 2003, 08:11
Ich muß sagen, daß die Beiträge sehr hilfreich sind. Gerade, wenn man einen Sortieralgorithmus für einen bestimmten Zweck sucht, sind die Vergleiche und Optimierungsvorschläge sehr nützlich.
Nun habe ich aber ein spezielles Problem. Ich möchte gerne eine Liste sortieren, die aber nicht ganz in den vom Programm nutzbaren Speicher passt. Das heißt, daß nach wenigen bis einigen hundert Einträgen ein Speicherseitenwechsel notwendig wird. Die einzelnen Listeneinträge können zudem bis zu 3KB groß sein. Welchen Algorithmus nehme ich am besten? Ich denke der Quicksort mit Optimierung, wie er hier dargestellt wird, ist noch am besten geeignet, weil er auch für große Datenmengen am schnellsten ist. Allerdings nur dann, wenn man auf verkettete Listen zurückgreift. Bei verketteten Listen ergibt sich aber das Problem, aus einem Bereich jeweils den mittleren Eintrag zu finden, weil ja die Position eines Eintrags in der Liste nicht der tatsächlichen Position in der Liste entspricht. Das ist nur ganz zu Anfang so, wenn die Liste neu erstellt wird. Man müßte also eigentlich, jedesmal, wenn man den mittleren Eintrag sucht, die verkettete Liste sequentiell so lange durchlaufen, bis man beim mittleren Eintrag angekommen ist. Aber gerade bei großen Datenmengen (100.000 Einträge zu je 508 Byte Größe z.B.) wo dann auch immer noch ein Speicherseitenwechsel zwischendurch notwendig wird, bei dem die Daten eventuell auch noch von Festplatte eingelagert werden müssen, bremst das doch den ganzen Algorithmus aus. Oder sehe ich das falsch? Wie kann man denn, vielleicht mit einem Trick, den mittleren Eintrag einer verketteten Liste schnell finden, also ohne das sequenzielle Suchen?
Oder gibt es vielleicht noch andre effektivere Ansätze zur Sortierung solcher von mir beschriebener Datenmengen?
Torsten
|