Das soll jetzt eine schematische Darstellung einer selectionsort Routine sein. Nun wollte ich mal fragen wie relevant die verzweigung in Zeile 8 is. Es ist ja bekannt dass ein Tauschvorgang länger dauert als ein Vergleich aber um wieviel ist das wirklich länger?



Dann hab ich nochwas. Es heißt dass der Compiler auf Integer und Cardinalwerte optimiert sei und nicht bspw. auf Byte. Wenn ich nun aber nur Werte bis 255 abspeichern will wären diese Typen ziemliche Platzverschwendung, sollte man dann trotzdem Integer benutzen?

Moderiert von Christian S.: Delphi-Tags hinzugefügt.

minnime hat folgendes geschrieben:

Dann hab ich nochwas. Es heißt dass der Compiler auf Integer und Cardinalwerte optimiert sei und nicht bspw. auf Byte. Wenn ich nun aber nur Werte bis 255 abspeichern will wären diese Typen ziemliche Platzverschwendung, sollte man dann trotzdem Integer benutzen?

Das lässt sich allgemein schwer beantworten, weil das ziemlich von Prozessor und Speicherausbau abhängig ist. Zugirffe auf Integers und Cardinals sind schneller als auf einzelne Bytes, weil sie der natürlichen Wortlänge des Prozessors entsprechen (32 Bits). Andererseits ist ein Byte-Array kleiner, womit es wahrscheinlicher ist, dass es in den Prozessor-Cache passt. Das macht die Sache natürlich viel schneller, weil der Prozessor Speicherzugriffe spart. Das gleiche gilt auch, wenn das Array so gross wird, dass es nicht mehr in den Arbeitsspeicher passt und die Maschine anfängt, zu swappen.
Ich würde daher vermuten, dass sich die Sache so verhält:

1. Sowohl Byte-Array auch Integer-Array passen in den Cache -> Integer ist schneller
2. Byte-Array passt in den Cache, Integer-Array aber nicht -> Byte ist schneller
3. Beide passen nicht in den Cache -> Integer ist schneller
4. Byte-Array passt noch ins RAM, Integer-Array aber nicht (natürlich zusammen mit so unwesentlichen Dingen wie dem Betriebssystem und dem Programm selbst ) -> Byte ist viel schneller
5. Beide passen nicht ins RAM -> beides ist furchtbar langsam

Das ist jetzt natürlich von mir so in den Raum spekuliert, nicht gemessen. Kann sein, dass der Vorteil der Grösse eines Byte-Arrays so viel ausmacht (das Integer-Array ist immerhin 4-mal grösser), dass das immer schneller ist.

Grundsätzlich muss man noch dazu sagen, dass es eigentlich nicht viel Sinn macht, einen Selection-Sort zu optimieren. Wenn man ein Programm optimieren will, schaut man sich zuerst die Algorithmen selbst an, und dann ist der logische Schluss, dass man Selection Sort überhaupt nicht verwendet. Ist das Array gross genug, ist die ineffizienteste Quicksort-Implementierung schneller als ein in Assembler handoptimiertes Selection-Sort.

Stefan

Das mit dem Speicherplatz war eigentlich mehr auf den Platzbedarf in Dateien bezogen (ist normalerweise gegenstandslos) macht bei Datenbanken aber Sinn. Bei der Geschwindigkeit geht es halt nur darum ob es wesentlich schneller ist. Ist es x mal schneller oder nur 1,x mal? Ich kann mir das eben nicht vorstellen dass das soviel ausmacht, wenn vier Byte in ein register passen dann passt eins erst recht rein, oder?
Zu Selectionsort, für eine kleine Liste in einem Programm, die nur ab und zu mal sortiert werden muss, reicht das allemal, zudem ist der Algorithmus sehr einfach. Sortieralgorithmen sind für mich eben eine ziemlich komplizierte Angelegenheit, das ist jetzt geredemal der zweite (nach Bubblesort) den ich soweit verstanden habe dass ich ihn selbst implementieren kann. Eigentlich geht es mir gar nicht um Selectionsort sondern eher um die besagte zusätzliche Zeile.