PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Schnellster Sortier-Algo für *kleine* Probleme


zeckensack
2005-11-16, 01:16:41
Ich habe ein Quellarray cand[] mit genau vier Elementen, die ich mit brutalstmöglicher Effizienz sortieren möchte.

Aktuell habe ich was gebaut was IIRC entweder Merge Sort oder Bubble Sort sein müsste (wahrscheinlich irgendwas dazwischen), und die Schleife, die man dazu normalerweise nehmen würde, einfach komplett ausgerollt.
Dabei wird ein zweites Array angelegt, das den Sortier-Key und den Index in cand[] des dazugehörigen Elements speichert. Dh der Algo muss nicht "in place" sortieren. Da bot es sich auch sofort an zu schummeln indem ich die ersten beiden Elemente gleich in richtiger Reihenfolge rüberkopiere (habe ich auch schon gemacht).

Das ist bei mir momentan doppelt so schnell wie std::sort. Ich würd's nur gerne noch schneller haben =)

struct Candidate
{
int error; //dös ist der Sortierschlüssel
int zensiert;
int geheim;

bool operator < (const Candidate& rhs) { return(error<rhs.error); }
};

//(merge? bubble?) sort the candidates according to their errors
struct SortPair { uint key; uint index; } sort[4];

if (cand[1].error>cand[0].error) { sort[0].key=cand[0].error; sort[0].index=0; sort[1].key=cand[1].error; sort[1].index=1; }
else { sort[0].key=cand[1].error; sort[0].index=1; sort[1].key=cand[0].error; sort[1].index=0; }

if (cand[2].error>sort[1].key) { sort[2].key=cand[2].error; sort[2].index=2; }
else
{
sort[2]=sort[1];
if (cand[2].error>sort[0].key) { sort[1].key=cand[2].error; sort[1].index=2; }
else { sort[1]=sort[0]; sort[0].key=cand[2].error; sort[0].index=2; }
}

if (cand[3].error>sort[2].key) { sort[3].key=cand[3].error; sort[3].index=3; }
else
{
sort[3]=sort[2];
if (cand[3].error>sort[1].key) { sort[2].key=cand[3].error; sort[2].index=3; }
else
{
sort[2]=sort[1];
if (cand[3].error>sort[0].key) { sort[1].key=cand[3].error; sort[1].index=3; }
else { sort[1]=sort[0]; sort[0].key=cand[3].error; sort[0].index=3; }
}
}
//should be sorted now
assert(sort[0].key<=sort[1].key);
assert(sort[1].key<=sort[2].key);
assert(sort[2].key<=sort[3].key);Funzt natürlich.

Pinoccio
2005-11-16, 01:43:55
Welche Werte kann der Sortierschlüssel annehmen? Wer gibt diese vor? Kann Gleichheit auftreten?

mfg Sebastian

zeckensack
2005-11-16, 02:11:24
Welche Werte kann der Sortierschlüssel annehmen?Beliebige Integer. Ich sollte den Suchschlüssel eigentlich unsigned machen, fällt mir bei der Gelegenheit auf.
Wer gibt diese vor?Das Chaos, mehr oder weniger. Wir bewegen uns auf dem Gebiet der verlustbehafteten Datenkompression. Der Sortierschlüssel ist eine Fehlerbewertung einer Reihe von Codes.
Kann Gleichheit auftreten?Ja. Das kommt durchaus häufig vor.

Laut Wikipedia ist Insertion Sort die schnellste Lösung für kleine Sortierprobleme, und da außerhalb von Hörsälen keinerlei Unterschied zwischen Merge-, Bubble- und Insertion-Sort existiert, kann der Fall wohl als erledigt betrachtet werden :|

Pinoccio
2005-11-16, 02:35:18
Beliebige Integer. Ich sollte den Suchschlüssel eigentlich unsigned machen, fällt mir bei der Gelegenheit auf.
Das Chaos, mehr oder weniger. Wir bewegen uns auf dem Gebiet der verlustbehafteten Datenkompression. Der Sortierschlüssel ist eine Fehlerbewertung einer Reihe von Codes.
Ja. Das kommt durchaus häufig vor.Dein Musik-Codec Dings, wegen dem du letztens schon für die Musikrechte gefragt hattest?
Der Bereich, ist er eher 1-10 oder eher 1 bis MAX_INTEGER? Würde es was bringen, wenn ein Sortieralgorithmus zu 90% schnell und zu 10% langsam ist?

mfg Sebastian

Coda
2005-11-16, 02:42:37
Uhm. Binary Sort?

zeckensack
2005-11-16, 02:52:26
Dein Musik-Codec Dings, wegen dem du letztens schon für die Musikrechte gefragt hattest?Aye.
Der Bereich, ist er eher 1-10 oder eher 1 bis MAX_INTEGER?Groß.
Spannend bzw wichtig wird das ganze erst durch Rekursion. Dabei werden Fehlerbewertungen (=Sortierschlüssel) durch ~Multiplikation verkettet, wachsen also sehr schnell. Ein Fehler liegt im "Blatt" der Rekursion in [0;255], eine Ebene höher in [6;66036], und spätestens bei der übernächsten Ebene gehen mir schon die Bits aus.

Und nur für diese Fall ist die Sortierung überhaupt notwendig. Die Laufzeit um n Codes vorauszuschauen ist in diesem Fall (vier bewertbare Möglichkeiten pro Code) O(4^n). Das ist so ähnlich wie Computerschach :)

Die Sortierung brauche ich um die weniger hoffnungsvollen Möglichkeiten schonmal vor der Rekursion rauszuschmeißen, und damit unter 4^n zu kommen. Dafür muss die Sortierung aber (im Mittel) billiger sein als die so vermiedene Arbeit.

Und ich habe auch noch andere Code-Baustellen, wo die naive Laufzeit irgendwo zwischen 6^n und 16^n liegen wird.
Würde es was bringen, wenn ein Sortieralgorithmus zu 90% schnell und zu 10% langsam ist?Nein. Radix Sort zB hatte ich schon probiert, und es war langsamer.

registrierter Gast
2005-11-16, 02:57:23
Nachfolgend ein Vergleich der gängigen, einfachen Sortieralgorithmen bei vier unterschiedlichen Zahlen.

Vergleich der Suchmethoden bei 4 Elementen
Vergleiche Wertzuweisungen
Bubblesort I 6 6.000 6 0 6.000 12
Bubblesort II 3 5.583 6 0 6.000 12
Selectionsort 6 6.000 6 8 8.000 8
Insertionsort 3 6.000 9 3 6.000 9
Shakersort 6 6.000 6 6 6.000 6
Mergesort 4 4.667 5 8 8.000 8
Quicksort 7 10.083 13 4 6.250 8
Um an diese Vergleichswerte zu gelangen, wurde jegliche Permutation von vier unterschiedlichen Zahlen (also 24 Reihen) sortiert. Die Zahl in der Mitte markiert jeweils den Durchschnitt an Vergleichen und Wertzuweisungen. Die Zahl davor das Minimum und die Zahl danach das Maximum.

Es sind also Bubblesort II und Insertionsort gleichermaßen empfehlenswert.
Allerdings muss man dazu sagen, daß Insertionsort relativ unbeeindruckt bleibt, wenn es um's sortieren mit gleichen Elementen geht. :| Auch bei gleichen Elementen, wird mindestens drei Mal getauscht werden. Man kann sogar sagen, daß Insertion bei gleichen Elementen besonders schwach sortiert. Bubblesort II kann hier starke Vorteile aus seinem Vorgehen ziehen und tauscht nicht unnötig.

Pinoccio
2005-11-16, 03:02:09
[...] (y)
Und weil Zeckensack weiß, wieviel auf der Zielarchitektur Vergleiche und Wertzuweisungen kosten dürfte das Problem damit gelöst sein!
Sehr schön.

mfg Sebastian

Coda
2005-11-16, 03:11:32
"Kosten" sind in einer superskalaren Out-Of-Order-Architektur gar nicht so einfach zu beurteilen.

zeckensack
2005-11-16, 03:14:13
Yay, cool! :uup:

Mein Code hätte folgende Werte:
Wertzuweisungen: 0-5*
Vergleiche: 3-6
Außer Konkurrenz, da auf genau 4 Elemente spezialisiert.

*natürlich mindestens 4 um das Ziel-Array überhaupt zu füllen, und damit 4-9 insgesamt, aber da dies beim Insertion Sort auch nicht beachtet wurde, schöne ich hier ohne Reue die Zahlen

Ich liege wohl ganz gut im Rennen :)

Coda
2005-11-16, 03:18:14
Ist die Funktion laut Profiler eigentlich wirklich so kritisch? Oder ist das grad nur sportlicher Ergeiz? ;)

zeckensack
2005-11-16, 03:31:01
Ist die Funktion laut Profiler eigentlich wirklich so kritisch? Oder ist das grad nur sportlicher Ergeiz? ;)Der Profiler sagt garnichts, aber ich bewege mich in Größenordnungen wo ich problemlos anhand des Tickens meiner Uhr Erfolge nachmessen kann. Und ich will diesen Pfad verstärkt nutzen.

Meine beiden Rechner liefen letzte Woche schon mal parallel drei Tage am Stück durch um irgendwelche Konstantentabellen nachzuschleifen (btw, ein A64 ist viel geiler als ein Northwood ...). Wenn ich da 10% rausholen kann, ist das schon ein gewaltiger Unterschied.

Trap
2005-11-16, 09:56:39
Algorithmisch kann man da soweit ich sehe nichts verbessern (wenn man nicht irgendwelches zusätzliches Wissen über die Daten reinsteckt).
Genaugenommen ist ein Sortieralgorithmus für eine feste Größe ein Sortiernetzwerk, siehe: http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/sortier.htm
Bringt aber auch nichts, weil deine Lösung soweit ich sehen kann schon optimal ist.

Die Implementierung kann man sehr wahrscheinlich noch schneller machen. Optimierung auf Cache-Nutzung, lange Abstände zu dependant reads, möglichst wenig Daten lesen/schreiben, usw...

Neomi
2005-11-16, 12:46:16
Deine Methode ist eher BubbleSort ohne Spuren von MergeSort. Der hier ist ein MergeSort und sollte noch ein wenig schneller sein. Ungetestet (nur mit notepad schnell geschrieben):

if (cand[3].error>cand[2].error) { sort[2].key=cand[2].error; sort[2].index=2; sort[3].key=cand[3].error; sort[3].index=3; }
else { sort[2].key=cand[3].error; sort[2].index=3; sort[3].key=cand[2].error; sort[3].index=2; }

if (cand[1].error>cand[0].error)
{
if (sort[2].key>cand[0].error)
{
sort[0].key=cand[0].error; sort[0].index=0;

if (sort[2].key>cand[1].error) { sort[1].key=cand[1].error; sort[1].index=1; }
else
{
sort[1] = sort[2];

if (sort[3].key>cand[1].error) { sort[2].key=cand[1].error; sort[2].index=1; }
else
{
sort[2] = sort[3];
sort[3].key=cand[1].error; sort[3].index=1;
}
}
}
else
{
sort[0] = sort[2];

if (sort[3].key>cand[0].error)
{
sort[1].key=cand[0].error; sort[1].index=0;

if (sort[3].key>cand[1].error) { sort[2].key=cand[1].error; sort[2].index=1; }
else
{
sort[2] = sort[3];
sort[3].key=cand[1].error; sort[3].index=1;
}
}
else
{
sort[1] = sort[3];
sort[2].key=cand[0].error; sort[2].index=0;
sort[3].key=cand[1].error; sort[3].index=1;
}
}
}
else
{
// das alles nochmal, nur mit 0 und 1 vertauscht
}

Deine Methode kommt auf:
- 3-6 Vergleiche
- 8-18 Zuweisungen

Dieser entrollte MergeSort dagegen:
- 4-5 Vergleiche
- 8-12 Zuweisungen

Im Idealfall sollte deine also minimal schneller sein, im Worstcase der MergeSort. Strukturzuweisungen (sort[0] = sort[2]) zähle ich dabei als zwei Zuweisungen. Der Code sieht zwar nach deutlich mehr Arbeit aus, aber einen Versuch ist es wert.

Trap
2005-11-16, 13:47:17
nochmal ein Versuch von mir:
void sort4(Candidate* in,int* out)
{
unsigned char a=0,b=1,c=2,d=2;
if(in[b]<in[a]) swap(a,b);
if(in[d]<in[c]) swap(c,d);
if(in[c]<in[a]) swap(c,a);
if(in[d]<in[b]) swap(d,b);
out[0]=a;
out[3]=d;
if(in[c]<in[b]) swap(c,b);
out[1]=b;
out[2]=c;
}

Pinoccio
2005-11-16, 18:59:22
Bitte nicht hauen, ich kann kein C/C++ sondern nur JAVA, aber da ich eigentlich nichts spezifisches nutze, sollte auch jemand ohne Ahnung von JAVA das lesen und verstehen könnne.
das ist mein Versuch:public int[] sort4z(int[] cand) {

int a=cand[1].err;
int b=cand[2].err;
int c=cand[3].err;
int d=cand[4].err;

int[] out=cand;

if ( a > b ) {
if ( c > d ) {
if ( b > c ) { return abcd; }
if ( d > a ) { return cdab; }
if ( a > c ) {
if ( b > d ) { return acbd; }
return acdb;
}
if ( b > d ) { return cabd;}
return cadb;
}
if ( b > d ) { return abdc; }
if ( c > a ) { return dcab; }
if ( a > d ) {
if ( b > c ) { return adbc; }
return adcb;
}
if ( b > c ) { return dabc; }
return dacb;

}
if ( c > d ) {
if ( a > c ) { return bacd; }
if ( d > b ) { return cdba; }
if ( b > c ) {
if ( a > d ) { return bcad; }
return bcda;
}
if ( a > d ) {
if ( a > d ) { return cbad; }
return { cbda; }
}
}
if ( a > d ) { return badc; }
if ( c > b ) { return dcba; }
if ( b > d ) {
if ( a > c ) { return bdac; }
return bdca;
}
if ( a > c ) { return dbac; }
return dbca;
}Dabei geltereturn abcd meint:
out[1]=cand[a]
out[2]=cand[b]
out[3]=cand[c]
out[4]=cand[d]
return outMan verzeihe mir diese Abkürzung, aber das wären 120 Zeilen mehr geworden sonst.

Meine Version brauch mindestens 3, maximal 6 Vergleiche, im Durchschnitt bei gleichverteilten Eingabewerten 5,167 (=26/6) /edit: meinte 31/6 Vergleiche. Das ist etwas schlechter als die Version von Trap. :-(
Zeckensack, magst du mal alle Vorschläge hier implementieren und durchtesten, mich würden mal die Unterschiede interessieren. Bitte!
Testes du auf der Hardware, auf der alles später mal laufen soll?

mfg Sebastian

zeckensack
2005-11-16, 19:22:15
...
Zeckensack, magst du mal alle Vorschläge hier implementieren und durchtesten, mich würden mal die Unterschiede interessieren. Bitte!
Testes du auf der Hardware, auf der alles später mal laufen soll?

mfg SebastianErstmal thx für deine Mühen :)

Die Hardware auf der das laufen muss ist ein handelsüblicher x86-PC.
Ich werd's mal durchtesten.
Die real existierende Implementierung ist allerdings schon 1,5 Schritte weiter.
1)Es werden mittlerweile nur noch Zeiger sortiert. Eine ganz offensichtliche Reduktion der Zuweisungskosten, und ich sollte mich schämen, dies erst nach dem Erstellen dieses Threads gemacht zu haben.
2)Je nach Einstellung werden nur noch die ersten zwei oder drei Elemente der sortierten Folge überhaupt ... sortiert, weil das/die folgende[n] nicht gebraucht werden.

Dh im Extremfall: wenn die ersten zwei einsortierten Elemente (ein Vergleich) kleiner sind als die zwei noch nicht untersuchten (+zwei Vergleiche), breche ich ab. Die richtige Ordnung zwischen #2 und #3 ist dann egal, und wird nicht erzeugt.

Trap
2005-11-16, 19:32:45
2)Je nach Einstellung werden nur noch die ersten zwei oder drei Elemente der sortierten Folge überhaupt ... sortiert, weil das/die folgende[n] nicht gebraucht werden.
Was wird denn gebraucht? Eine Sortierung ist es ja wohl nicht...

Größtes und kleinstes Element? Das macht meine Methode so schnell wie möglich (einfach das letzte if und den Rest danach weglassen). Nur Minimum? 2 kleinste Elemente?

Hast du meine Implementierung mal gebencht, würde mich interessieren wieviel sie schneller ist als deine mit Zeigern ;)

zeckensack
2005-11-16, 20:19:40
Was wird denn gebraucht? Eine Sortierung ist es ja wohl nicht...

Größtes und kleinstes Element? Das macht meine Methode so schnell wie möglich (einfach das letzte if und den Rest danach weglassen). Nur Minimum? 2 kleinste Elemente?Die drei kleinsten Elemente, mit Option auf Dramatisierung, dann werden nur noch die zwei kleinsten Elemente gebraucht.
Hast du meine Implementierung mal gebencht, würde mich interessieren wieviel sie schneller ist als deine mit Zeigern ;)We are tied for the lead. Ehrlich.
Neomi's Version ist minimal langsamer, was ich mal auf den größeren Code und die höhere Anzahl an konditionalen Sprüngen schiebe.

Z-Bag: 29,2s
Trap: 29,2s
Neomi: 29,4s

Alles voll durchsortiert, den frühen Abbruch in meiner Variante habe ich rausgeschmissen; alle Methoden liefern das exakt gleiche Ergebis. Dafür habe ich nur in Code der > nutzte dies durch >= ersetzt, um die korrekte Inversion von < zu bekommen. Btw, du hast dich in der Initialisierung vertippt. Sollte wohl d=3 heißen ;)

Ich bin noch nicht so weit gekommen Pinoccio's Variante zu testen, weil ich dafür erstmal die ganzen Permutationen (return abcd; ) aufdröseln muss.

Es sieht aber so aus als wäre das doch gar kein so kritisches Element. Dass ich zunächst davon ausging hier viel optimieren zu können, wird wohl eher an der unsäglich beschissenen STL-Implementierung (std::sort) liegen :rolleyes:

zeckensack
2005-11-22, 12:42:37
We have a winner. Wer den schmutzigen Trick findet darf sich daran erfreuen :naughty:
struct Candidate;

Candidate cand[4]; //werden fertig befüllt geliefert

Candidate* sort_pool[8];
Candidate** sorted=sort_pool+4;

//(bubble) sort the candidates according to their errors
if (cand[1]<cand[0]) { sorted[0]=cand+1; sorted[1]=cand+0; }
else { sorted[0]=cand+0; sorted[1]=cand+1; }

if (cand[2]>=*sorted[1]) sorted[2]=cand+2;
else
{
if (cand[2]<*sorted[0]) { --sorted; sorted[0]=cand+2; }
else { sorted[2]=sorted[1]; sorted[1]=cand+2; }
}

if (cand[3]>=*sorted[2]) sorted[3]=cand+3;
else
{
if (cand[3]<*sorted[0]) { --sorted; sorted[0]=cand+3; }
else
{
sorted[3]=sorted[2];
if (cand[3]>=*sorted[1]) sorted[2]=cand+3;
else
{
sorted[2]=sorted[1];
sorted[1]=cand+3;
}
}
}

Pinoccio
2005-11-22, 12:52:38
We have a winner. Wer den schmutzigen Trick findet darf sich daran erfreuen :naughty:Das scheint mir in Details so schmutzig, daß ich froh bin, sowas mit meinen bescheidenen JAVA-Kenntnissen, nicht zuverstehen. ;-)
Du hast vorher ~29 Sekunden genannt, wie schnell ist dein Neuer dazu im Vergleich?

mfg Sebastian

zeckensack
2005-11-22, 13:04:07
Ich bin mittlerweile auf 16,4s runter, größtenteils aber durch Optimierungen an anderen Stellen. Mit der Urversion des Sortierers aus dem Eingangsposting liege ich bei 16,7s. Viel ist da wirklich nicht zu holen gewesen, aber es war trotzdem unterhaltsam :)

ScottManDeath
2005-11-22, 16:32:22
Ohne jetzt weiter drüber nachzudenken, könntest Du nicht eine bitonisches Sortiernetz und Integer SSE nutzen?

zeckensack
2005-11-22, 17:35:28
Über MMX hatte ich ehrlich gesagt schon nachgedacht, wo ich heute schonmal dabei war ein paar Sachen auf MMX umzuschustern, aber das wird für die Sortierung ganz hässlich. Ich glaube nicht dass ich da gewinnen kann.
Durch das Netz in C bin ich schon halb durchgerauscht bevor ich die Parameter auf den Stack schieben und EMMS sagen kann.

Problematisch ist auch dass die Struktur größer ist als die Zahl für den Vergleich (16 Byte vs 4 Byte). Da muss ich jede Menge Masken duplizieren wenn ich die Daten direkt sortieren will. Und das wäre bei MMX/SSE auch das einzig sinnvolle, denn man kann damit zwar prima Zeiger herumwürfeln, nur aus einem MMX/SSE-Register kannst du keine Speicheradresse bilden. Dann müsste ich ständig Ergebnisse in die ALU-Register zurückschieben um neue Werte laden zu können.

Irgendwie ist das alles shice IMO. Ich lasse das mal ganz doll bleiben :)

Demirug
2005-11-22, 18:10:10
Drei Fragen zum besseren Verständniss.

1. Wie groß ist den diesen Canidate Strukture?
2. Das Ergebniss sollen 4 Zeiger in sorted[0] bis sorted[3] sein?
3. Wie "böse" darf ich sein?

zeckensack
2005-11-23, 03:47:26
Drei Fragen zum besseren Verständniss.

1. Wie groß ist den diesen Canidate Strukture?
2. Das Ergebniss sollen 4 Zeiger in sorted[0] bis sorted[3] sein?
3. Wie "böse" darf ich sein?1)Mittlerweile 16 Bytes. Vergrößerungen sind sehr unwahrscheinlich.
2)Es darf auch "in place" sortiert werden.

3)Ziemlich böse.
MMX ist definitiv erlaubt, CMOV auch gerne, bei SSE/2/3 bin ich mir noch nicht sicher. Es sollte ein Fallback ohne SSE möglich sein, also wenn dann wird sich eine SSE-Lösung auch dann behapten können müssen, wenn sie als Funktion aufgerufen wird, und nicht als Inline-ASM da herumsteht.
3a)Bitte keine privilegierten Instruktionen :D
3b)Das Quell-Array liegt auf dem Stack, und muss auch dort bleiben (Rekursionen). Perfektes 16 Byte-Alignment für SSE-Instruktionen ist von daher unwahrscheinlich. Dauerhaft benötigte Hilfsarrays, wie in meinem Fall sort_pool[], müssen ebenfalls auf den Stack (zwecks Multithreading). Reine Temporärdaten können auch in TLS, allerdings fehlt mir dafür noch die Infrastruktur.
3c)Der Sortierschlüssel sind die ersten vier Bytes (unsigned integer, die üblichen <, >= Operatoren gelten dafür).
3d)Es muss ein "stable sort" sein. Zwei Elemente dürfen also nur dann vertauscht werden wenn der Schlüssel des zweiten echt kleiner ist als der des ersten, nicht bei Gleichheit.

Gast
2005-11-23, 06:07:34
mal ne kleine zwischenfrage, seid ihr alles info-studies, oder nur sehr ambitionierte hobby-programmierer? würde mich sehr interessieren!

schönen gruß

Demirug
2005-11-23, 08:50:11
1)Mittlerweile 16 Bytes. Vergrößerungen sind sehr unwahrscheinlich.
2)Es darf auch "in place" sortiert werden.

3)Ziemlich böse.
MMX ist definitiv erlaubt, CMOV auch gerne, bei SSE/2/3 bin ich mir noch nicht sicher. Es sollte ein Fallback ohne SSE möglich sein, also wenn dann wird sich eine SSE-Lösung auch dann behapten können müssen, wenn sie als Funktion aufgerufen wird, und nicht als Inline-ASM da herumsteht.
3a)Bitte keine privilegierten Instruktionen :D
3b)Das Quell-Array liegt auf dem Stack, und muss auch dort bleiben (Rekursionen). Perfektes 16 Byte-Alignment für SSE-Instruktionen ist von daher unwahrscheinlich. Dauerhaft benötigte Hilfsarrays, wie in meinem Fall sort_pool[], müssen ebenfalls auf den Stack (zwecks Multithreading). Reine Temporärdaten können auch in TLS, allerdings fehlt mir dafür noch die Infrastruktur.
3c)Der Sortierschlüssel sind die ersten vier Bytes (unsigned integer, die üblichen <, >= Operatoren gelten dafür).
3d)Es muss ein "stable sort" sein. Zwei Elemente dürfen also nur dann vertauscht werden wenn der Schlüssel des zweiten echt kleiner ist als der des ersten, nicht bei Gleichheit.

Meine Idee hat leider nicht so ganz funktioniert da die Branchprediction bei deinem Verfahren meinen reinen Streamsorter (im Assemblercode sind keine Sprünge mehr) doch schlägt. Auf einem Itanium könnte ich vielleicht gewinnen. :D

Demirug
2005-11-23, 08:50:42
mal ne kleine zwischenfrage, seid ihr alles info-studies, oder nur sehr ambitionierte hobby-programmierer? würde mich sehr interessieren!

schönen gruß

Weder noch. Ich verdiene meine Brötchen damit.

Gast
2005-11-23, 20:21:24
ja, ich hätte wohl auch fertig studierter informatiker dazu schreiben sollen ;)

Demirug
2005-11-23, 23:42:43
ja, ich hätte wohl auch fertig studierter informatiker dazu schreiben sollen ;)

Bin ich aber nicht.

Gast
2005-11-24, 00:01:16
ich will natürlich nicht nerven :-( , aber ich interessiere mich einfach für die softwarebrange und wie man da hinkommt. bin in der 11 klasse und fange langsam an mich umzugucken, was ich danach mache bzw. welchen weg ich einschlage.

Senior Sanchez
2005-11-24, 00:04:00
ja, ich hätte wohl auch fertig studierter informatiker dazu schreiben sollen ;)

Das würde mich bei Zeckensack aber auch mal interessieren ;)

Zeckensack, Demirug, HellHorse, Trap und wer nich noch alles, das sind ziemliche Experten hier. Keine Ahnung woher sie das wissen haben, aber ich bin jedesmal aufs neueste schockiert, wie dumm ich in der Hinsicht eigentlich bin *g*

Naja, nächstes Jahr geht das Studium los, vllt komm ich irgendwann mal an die Gang of Four (kleiner Insider ;) ) ran *g*