4. quick sort beispiel in assembler?

quick sort beispiel in assembler?

  • ?

    in asm wird's auch nicht viel schneller!

    0
  • ?
     

    ;***********************************************************
;   Coded by Kty    June 2000
;***********************************************************
QuickSort:          ;d0= begining, d1 = End 
    subq.l  #4,a7
    move.w  8(a7),d1
    move.w  10(a7),d0
    move.w  d0,d3       ;d3=i=beg
    move.w  d1,d4       ;d4=j=end
    move.w  d1,d2
    add.w   d0,d2       ;deb+fin
    lsr.w   #1,d2       ;(deb+fin)/2
    lsl.w   #1,d2
    move.w  0(a0,d2.w),d2   ;d2=HandleSortedPtr[(begining+End)/2)]
    lsl.w   #4,d2       ;Face caracteristic is 16Bytes
    move.w  6(a1,d2.w),d2   ;Z of the middle facette
While:
    cmp.w   d3,d4       ;
    blt EndWhile    ;d3>d4       
                ; here d3<=d4
While1:
    move.w  d3,d5
    lsl.w   #1,d5
    move.w  0(a0,d5),d5
    lsl.w   #4,d5       ;3
    move.w  6(a1,d5),d5 ;d5=Z of considered facette
    cmp.w   d2,d5
    ble EndWhile1   
    addq.w  #1,d3
    bra While1
EndWhile1:
While2:
    move.w  d4,d5
    lsl.w   #1,d5
    move.w  0(a0,d5),d5
    lsl.w   #4,d5       ;3
    move.w  6(a1,d5),d5
    cmp.w   d5,d2
    ble EndWhile2   
    subq.w  #1,d4
    bra While2

EndWhile2:
    cmp.w   d4,d3
;   bgt EndIf
    bgt While

    move.w  d3,d5
    lsl.w   #1,d5
    move.w  0(a0,d5),d6 ;d6=HandleSortedPtr[i]

    move.w  d4,d5
    lsl.w   #1,d5
    move.w  0(a0,d5),d7 ;d7=HandleSortedPtr[j]

    move.w  d3,d5
    lsl.w   #1,d5
    move.w  d7,0(a0,d5) ;HandleSortedPtr[i]=d7

    move.w  d4,d5
    lsl.w   #1,d5
    move.w  d6,0(a0,d5) ;HandleSortedPtr[j]=d6

    addq.w  #1,d3
    subq.w  #1,d4
;EndIf:
    bra While

EndWhile:
    cmp.w   d1,d3
    bge EndIf1      ;if d1 <= d3
    move.w  d3,d0
    move.w  d3,0(a7)    
    move.w  d4,2(a7)
    move.w  d0,-(a7)
    move.w  d1,-(a7)
    bsr QuickSort
    addq.l  #4,a7
    move.w  2(a7),d4
    move.w  0(a7),d3
EndIf1:
    move.w  10(a7),d0
    cmp.w   d4,d0       
    bge Endif2      ;if d4 <= d0
    move.w  d4,d1
    move.w  d3,0(a7)    
    move.w  d4,2(a7)
    move.w  d0,-(a7)
    move.w  d1,-(a7)
    bsr QuickSort
    addq.l  #4,a7
Endif2:
    addq.l  #4,a7
    rts

;***********************************************************
;***********************************************************
    0
  • ?

    verschoben ins ASM Forum

    0
  • ?

    äh 🙄
    ich bin c programmierer, wie kann ich denn diesem asm code in mein c programm einbinden? 😕
    und wie übergebe ich dann das array?

    Danke schonmal!

    0
  • T

    Original erstellt von <Gast>:
    kann mir einer helfen, ich habe eine quick sort routine in c, leider ist die noch ein bischen langsam. ich such nun eine verwendbare routine in assembler, welche ich möglichst als unterprogramm einbinden kann und an die ich nur die daten übergeben muss

    Ich glaube nicht dass es dir was bringen wird, das Quicksort nicht mehr in C sondern in ASM zu schreiben. Compilier optimieren jetzt schon viel raus, vielelicht ist die Variante in C die du hast nur einfach nicht günstig geschrieben 🙂

    0
  • ?

    um herauszufinden, wie gut meine variante ist, möchte ich ja eine in asm einbinden um das ergebn. vergleichen zu können.

    😉

    0
  • ?

    schaffst du sowieso nicht in asm. bleib bei c

    0
  • ?

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

    0
  • T

    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. ]

    0
  • ?

    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);
    }

    }

    0
  • T

    und wer ist xD, AB, BD, OOD ?

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

    0
  • ?

    🙂

    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? 🙄

    0
  • T

    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. ]

    0
  • S

    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 🙂

    0
  • ?

    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 😕

    0
  • ?

    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???

    0
  • V

    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.

    0
  • ?

    @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 😉

    0
  • V

    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.

    0
  • ?

    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. 😃

    0
Anmelden zum Antworten