quick sort beispiel in assembler?

was schaffe ich nicht den vergleich? oder auf blöde posts zu antworten

TriPhoenix

Versuch folgendes:

Generiere einen großen Haufen Daten (zufallszahlen z.B.), so 1 Million Stück oder so (das entspricht dann 4 MB Daten), davon machst du eine exakte Kopie.
Nun rufst du einmal das C-Quicksort zum sortieren auf und einmal das ASM-Quicksort (jeder natürlich mit einem unsortierten Datensatz, der ja gerade zweimal generiert wurde), jedesmal misst du die Zeit die gebruacht wurde und gibst beide Zeitwerte aus. Das ganze machst du am besten 100mal und vielleicht auch mal zuerst ASM und dann C aufrufen um allen Ungereimtheiten ausm Weg zu gehen. Während jedes Schleifeendurchlaufs addierst du am besten noch die Zeiten auf, so dass du am Ende einen gesamtwert C-QS und einen ASM-QS hast. Die Daten sollten aufschluss darüber geben, was schneller ist.

PS: Zeig doch mal das C-Quicksort was du verwendest, wenn möglich lasse ich gerne meine versuchten Optimierungen gegen das Original und gegen ASM antreten

[ Dieser Beitrag wurde am 20.11.2002 um 21:26 Uhr von TriPhoenix editiert. ]

hier meine routine, und GENAU dafür brauche ich eine in asm
und dies sollte auch noch schneller sein

ach ja, ich lasse ein feld sortieren und 2 weitere nach dieser sortierung ordnen. eigentlich wird hier nach a sortiert und b und c werden danach auch gleich angeordnet.

int vergleich(int x, int y)
{
if (x<=y)
return 1;
else
return 0;
}

void tausche(int* zx,int* zy)
{
int hilf;
hilf=*zx;
*zx=*zy;
*zy=hilf;
}

void quick_sort(const int anfang, const int ende, int feld[])
{
int links=anfang-1, rechts=ende-1,pivot=ende;
int vgllinks,vglrechts;

if (ende>anfang)
{
do
{
links++;
vgllinks=vergleich(feld[links],feld[pivot]);

while (!vgllinks && rechts>links)
{

vglrechts=vergleich(feld[rechts],feld[pivot]);

if (!vglrechts)
rechts--;
else
{
tausche(&feld[links],&feld[rechts]);

tausche(&xD[links] ,&xD[rechts]);
tausche(&AD[links] ,&AD[rechts]);
tausche(&OOD[links] ,&OOD[rechts]);
tausche(&BD[links] ,&BD[rechts]);
vgllinks=1;
}

}

}
while (links!=rechts);

if (feld[links]>feld[pivot])
{ tausche (&feld[links],&feld[pivot]);

tausche (&xD[links] ,&xD[pivot]);
tausche (&AD[links] ,&AD[pivot]);
tausche (&OOD[links] ,&OOD[pivot]);
tausche (&BD[links] ,&BD[pivot]);
}
quick_sort(anfang,links,feld);
quick_sort(links+1,ende,feld);
}

}

TriPhoenix

und wer ist xD, AB, BD, OOD ?

PS: Nimm doch nächstes mal das code-tag

felder vom typ int

int feld1[300] { 1, 5, 3, 8,5 ...};
int feld2[300] { 44, 56,767,212,3 ...};
int feld3[300] { 4, 3, 4, 23,1 ...};

diese werden "nur" in gleicher reihenfolhe sortiert wie feld, letztlich ist die sortierung aller felder abh. von dem zu sort. feld.

äh, war das halbwegs verständlich?

TriPhoenix

Ich denke schon, für den Vergleich habe ich die mal ausgeklammert so dass nur auf einem Feld sortiert wird.

Damit ergibt sich die erste Statistik:
Dein QuickSort vs. qsort() (eine Funktion aus der C-Library)
Gesamtzeit Userdef C: 38497ms
Gesamtzeit qsort() : 25578ms
Bei 100 Läufen.

Im Schnitt braucht deine Funktion rund 384ms, qsort() nur 255ms. qsort() ist zumindest im M$-Compiler auch nur als C-Funktion implementiert. Ergo kann man auch ganz ohne Assembler auf 2/3 der Laufzeit kommen.
Achja, schonmal dran gedacht qsort aus der C-Lib zu nehmen?

Ein asm-Einwurf kann natürlich gerne noch teilnehmen, der von da oben zählt nicht, der ist definitiv nicht für x86 oder maximal für einen absolut kranken Assembler.

[ Dieser Beitrag wurde am 20.11.2002 um 22:20 Uhr von TriPhoenix editiert. ]

Shade Of Mine

Die C++ Funktion std::sort() ist sogar noch besser als qsort(), da bei qsort() ja immer eine vergleichsfunktion aufgerufen werden muss

bei std::sort ist diese vergleichsfunktion inline

hmmm, bei mir ist qsort langsamer???

jetzt ergibt sich 1. die frage, warum und 2. wie gross war das array welches du sortieren lassen hast und 3. wie hast du qsort aufgerufen? ich habe es nur mit genau anderem ergebn. einbinden können

ich habe es gerade nochmal überprüft, stimmt, wenn ich NUR ein array sortieren lasse, ist qsort schneller, wenn ich aber in abhängigkeit von eben diesem sortierten array die 3 anderen mit sortiieren lasse, dann ist es andersherum

hat jemand einen einfall???

volkard

Original erstellt von <Gast>:
hat jemand einen einfall???

hieße die frage "suche schnelle sortierung" und wüßte ich, in welchem der beiden threads zu antworten ist, und wüßte ich, wozu die sortierung gesucht wird, dann wäre vielleicht was zu machen.

@volkard

ich habe bei einem freund ein snake game gesehen, welches nur mit directdraw programmiert wurde (also ohne Direct3D) diese snake ist in einem iso-3d gelände und ist selber incl. aller gegenstände auch in iso-3d persp. dargestellt.

ich habe nun (natürlich im moment noch sehr simpel) das ganze mal versucht nachzubauen und bin dabei auf folgende lösung gestossen:

1. um bei einfachen blits die blittreihenfolge der einzelteile richtig darstellen zu können, muss ich je nach position der teile die reihenfolge neu bestimmen (ist halt keine 3d engine)

2. um positionen sortieren zu können eignet sich ein int array für x, y, art, und ob das jeweilige teil zu sehen ist (snake wird länger oder kürzer)

3. ich muss das y array sortieren (richtige blitreihenfolge) und nun natürlich die zugehörigen werte in den anderen array auch.

ich hoffe es verständlich beschr. zu haben

volkard

Original erstellt von <Gast>:
2. um positionen sortieren zu können eignet sich ein int array für x, y, art, und ob das jeweilige teil zu sehen ist (snake wird länger oder kürzer)
3. ich muss das y array sortieren (richtige blitreihenfolge) und nun natürlich die zugehörigen werte in den anderen array auch.
ich hoffe es verständlich beschr. zu haben

jo, glaub schon.
allgemein ist zum sortieren quicksort am schnellsten.
hier wäre zu überlegen, ob nicht ein indexfeld sortiert werden sollte, um weniger kopieren zu müssen.
außerdem kackt quicksort fürchterlich ab, wenn das feld bereits vorsortiert ist. ist es vielleicht so, daß die daten von bild zu bild kaum geändert werden? also sagen wie mal nur 10 objekte ändern ihre position? dann wäre bubble evtl schneller. oder am besten werden die objekte, die ihre position ändern angeschubst, sich neu einzusortieren.
oder entstehen und verschwinden andauernd ein paar objekte? das sähe nach einem baum aus, den man dann in order durchgeht, um alle zu zeichnen.

wenn ich mal so drüber nachdenke...
ich denke, es gibt recht wenige mögliche y-positionen? dann wär da ein array voller doppelt verketterer listen ideal, würd ich sagen.
einfügen in O(1).
löschen in O(1).
kein Sortierbedarf.

oder brauchste auch suche nach x und y? jo, könnt ein array von bäumen werden, denke mal ein array von hashtables oder ein 2d-baum wär übertrieben.

oder gibts nur relativ wenige positionen, wo überhaupt objekte sein können und an jeder postion nur eins? das wäre dann ein dickes array of art.

verstehste jetzt, warum ich quicksort erstmal einfach angezweifelt hab? je mehr man über die genauen anforderungen weiß, desto genauer kann man ne gut angepaßte datenstruktor und gute algorithmen auswählen. und gut angepaßte dinge machen standard-dinge mit links platt. vergäude deine zeit also erstmal nicht damit, ein gutes allgemeines quicksort in c zu einem guten allgemeinen quicksort in asm zu machen, selbst wenn 20% mehr speed drinne ist. mach das erst, wenn du ganz sicher bist, daß dir kein besseres verfahren einfallen wird.

vielen dank für eure bemühungen, ich habe mittlerweile von herrn heinzig den quellcode welchen er verwendet hat bekommen, ist übrigens kompl. in assembler und verfolgt den gleichen grundgedanken welchen ich hatte.

Hey, magste den mal posten? Ich will sehen ob der schneller ist und wenn ja wieviel

volkard

da gibt man sich so ne mühe mit den jungen leuten...

und dann kommt einer und gibt mir den ganzen source und erklärt mir den auch noch und hilft mir diesen in mein programm einzubauen

nein, mal ganz ehrlich, ich danke dir, nur ist es so halt viel einfacher für mich und wann bekommt mann schon mal die möglichkeit mit so einem programmierer zusammenarbeiten zu können? nochmals vielen dank an alle und vor allem natürlich an maik!!!