Array sortieren - Performance Problem

[Aron]

Ich habe mich gewundert, warum mein Game "stottert" mit zunehmender Spieldauer. Jetzt habe ich festgestellt, dass die Array-Sortiererei einfach zu langsam ist. Erschwerend kommt hinzu, dass ich FlashMX benutze und ein zweiter Array mitsortiert werden muss. Einen für die Punkte, einen für die Spielernamen ( hierzu habe ich die Funktion aus diesem Thread benutzt ). Der pointArray kann bis 150 Einträge haben.

Hat jemand eine Idee, wie ich die Sortierfunktion beschleunigen kann? Oder nutzt Ihr vielleicht einen anderen Ansatz (evtl. mit Objekten)?

Bin für jede Hilfe dankbar
Aron

[kenichi]

hi,

ich glaube die sortierfunktion die die dort benutzen nennt sich bubble-sort.
ist nicht grad die schnellste. ausserdem glaub ich (habs mir jetzt nicht genau angeschaut), dass man die funktion noch verkuerzen koennte.

ansonsten such doch hier oder bei google einfach mal nach sortier algorithmen und versuch die nach AS zu portieren. ein stichwort dafuer ist z.b. "merge-sort", aber es gibt auch noch mehr.

und ich bin mir sicher, dass es alle algorithmen schon fuer AS gibt. musst sie nur finden .

ansonsten hast du dir schon mal die actionscript eigenen sortierfunktionen angeschaut?
die duerften ansich auch recht schnell sein.
die heissen glaub ich "Array.sort()" und "Array.sortOn()".
frag mich aber nicht, wie und was die genau machen.

ich hoffe, das hilft etwas.

gruss,
kenichi

[kenichi]

den kannste ja mal versuchen...
http://proto.layer51.com/d.aspx?f=301

[Aron]

Die Flash-Interne Sortfunktion ist auch megalahm. Ist aber auch keine Wunder, die Schleifen müssen ja schließlich array.length² durchlaufen. Da hilft keine Optimierung, das dauert einfach. Der "Misch"-ansatz von dir ist nicht schlecht. So hab ich's gemacht.

Da nur ein Element hinzugefügt wird, ist es ja eigentlich garnich nötig, den ganzen Array neu zu sortieren. Es wird also nur überprüft, wann ein kleinerer Eintrag als der Neue in dem Array kommt. Hier wird dann der neue Eintrag eingefügt. Das selbe wird mit dem zweiten Array auch gemacht.

Array.prototype.addArrayElementInOrder = function(newElement,secondArray,secondValue){
    var a = this;
    var spliced = 0;
    for(var i=0; i<a.length ; i++){
        if(a[i] <= newElement){
            a.splice(i, 0, newElement);
            secondArray.splice(i, 0, secondValue);
            spliced=1;
            break;
        }
    }
    if(spliced == 0){
        a.push(newElement);
        secondArray.push(secondValue);
    }
}
 
// Anwendung
a = [15,10,10];
b = ["Aron", "Bron", "Cron"];
 
a.addArrayElementInOrder(25,b,"Dron");
trace(a);
trace(b);
 
a.addArrayElementInOrder(10,b,"Eron");
trace(a);
trace(b); 

Danke
Aron