Strings vergleichen im QuickSort Algorithmus, Performance?
Hallo,
ich implementiere z.Z. einen External Multiway Merge Sort Algorithmus, mit dem Ziel, enorm große datenmengen (ab 100 000 datensätze) in relativ schneller zeit sortieren zu können. der algorithmus teilt die daten in blöcke von 1mb, welche dann jeweils einzeln im speicher mittels QuickSort sortiert werden.
leider dauert dies pro block momentan ca. 18 sekunden, was mir ehrlich gesagt viel zu langsam ist.
jetzt meine fragen:
weiss jemand wie die c# interne String.CompareTo() Methode arbeitet? wird hier mit hashing gearbeitet? kann ich mittels hashing die anzahl der vergleiche evtl. verringern um so zeit einzusparen? ich suche halt nach einem effizienterem weg, strings zu vergleichen, was ja der kern eines jeden sortier-algorithmus ist.
wenn jemand also ne idee hat, wie ich meinen quicksort algorithmus optmieren kann, wäre ich sehr dankbar wenn er/sie mir diese kundtun würde.
beste grüße,
f.
Hallo feadur,
soweit ich weiß vergleicht String.Compare einfach zeichenweise von links nach rechts. Wenn die String sich früh unterscheiden, sollte hier eigentlich nicht das Problem liegen.
18s erscheint mir für 1mb (auf einem aktuellen Rechner) extem lange. Das wird aber nicht an Quicksort liegen.
Sind die zu sortierenden Einträge structs oder echte Objekte?
Ach ich sehe gerade, du meinst CompareTo. Das sollte aber kein großer Unterschied sein, es sei denn deine Objekte werden irgendwann in Strings umgewandelt und du hast in der Klasse eine aufwändige ToString-Methode.
HTH
herbivore
hi,
es werden nur strings verglichen, die quicksort methode sieht so aus:
array beinhaltet jeweils einen ca. 1 MB großen block daten. (also jeweils eine zeile aus einer sequenziellen datei)
EDIT
hat sich erledigt, mein quicksort hatte nen lustigen kleinen bug.
jetzt geht es rasend schnell.
😉
schonmal vorweg:
ich bitte um eine kräftige genickwatschn falls ich hier mist rede.
prinzipiell müsste hashing doch funktionieren. nur wie siehts dann mit doppelten datensätzen aus? wird sowas übergangen, weil ich ja den selben inhalt habe oder hashed er da andere infos mit rein?
bei simplen vergleichen hat sich bei meinen projekten (okok größere datenmengen warens nie) der bitweise vergleich etabliert. (zeitlich wird das aber im vergleich zu selbstgeschreibenen und optimierten algorithmen eher ein mäuseschiss sein) wie machts dann das .net framework? ich glaub auch so.
auf jeden fall glaub ich, dass in den sort methoden von .net objekten usw schon optimierte algorithmen stattfinden oder nicht? ich hab noch nicht viel mit datenbanksachen gearbeitet aber in .net gibts doch viele solche klassen....datagrid zB.
muss man da seinen sortieralgorithmus extra implementieren oder gibts da schon vorgefertigtes? ich würd meine daten mal in son ding einlesen und sortieren. vielleicht is das schneller? wer weiss.
mfg
tom