[ Letztes Update: Benchmark-Programm und vorläufige Ergebnisse verfügbar, siehe unten]
Daher möchte ich den Kompromiss zwischen Geschwindigkeit und Komplexität mit einer klassischen Anwendung testen: dem Sortieren.
Schreiben Sie eine ANSI C-Funktion, die ein Array von Gleitkommazahlen in aufsteigender Reihenfolge sortiert.
Sie können keine Bibliotheken, Systemaufrufe, Multithreading oder Inline-ASM verwenden.
Einträge werden anhand von zwei Komponenten beurteilt: Codelänge und Leistung. Bewertung wie folgt: Einträge werden nach Länge (Protokoll von #Zeichen ohne Leerzeichen, damit Sie die Formatierung beibehalten können) und nach Leistung (Protokoll von #Sekunden über einem Benchmark) sortiert und jedes Intervall [am besten, am schlechtesten] linear auf [normalisiert] 0,1]. Die Gesamtpunktzahl eines Programms ist der Durchschnitt der beiden normalisierten Punktzahlen. Die niedrigste Punktzahl gewinnt. Ein Eintrag pro Benutzer.
Die Sortierung muss (eventuell) vorhanden sein (dh das Eingabearray muss bei der Rückgabe sortierte Werte enthalten), und Sie müssen die folgende Signatur einschließlich der Namen verwenden:
void sort(float* v, int n) {
}
Zu zählende Zeichen: diejenigen in der sort
Funktion, einschließlich Signatur, plus zusätzliche Funktionen, die von ihr aufgerufen werden (jedoch ohne Testcode).
Das Programm muss alle numerischen Werte float
und Arrays mit einer Länge von> = 0 bis zu 2 ^ 20 verarbeiten.
Ich werde sort
und seine Abhängigkeiten in ein Testprogramm einbinden und auf GCC kompilieren (keine ausgefallenen Optionen). Ich werde eine Reihe von Arrays einspeisen, die Richtigkeit der Ergebnisse und die Gesamtlaufzeit überprüfen. Die Tests werden auf einem Intel Core i7 740QM (Clarksfield) unter Ubuntu 13 ausgeführt. Die
Array-Längen erstrecken sich über den gesamten zulässigen Bereich mit einer höheren Dichte an kurzen Arrays. Die Werte sind zufällig mit einer Fettschwanzverteilung (sowohl im positiven als auch im negativen Bereich). Doppelte Elemente werden in einigen Tests enthalten sein.
Das Testprogramm ist hier verfügbar: https://gist.github.com/anonymous/82386fa028f6534af263
Es importiert die Einreichung als user.c
. Die Anzahl der Testfälle ( TEST_COUNT
) im aktuellen Benchmark beträgt 3000. Bitte geben Sie in den Fragenkommentaren Feedback.
Frist: 3 Wochen (7. April 2014, 16:00 GMT). Ich werde den Benchmark in 2 Wochen veröffentlichen.
Es kann ratsam sein, kurz vor Ablauf der Frist zu posten, um zu vermeiden, dass Ihr Code an Mitbewerber weitergegeben wird.
Vorläufige Ergebnisse zum Zeitpunkt der Veröffentlichung der Benchmark:
Hier einige Ergebnisse. In der letzten Spalte wird die Punktzahl als Prozentsatz angezeigt. Je höher desto besser, wobei Johnny Cage an erster Stelle steht. Algorithmen, die um Größenordnungen langsamer waren als die anderen, wurden in einer Teilmenge von Tests ausgeführt und die Zeit extrapoliert. Cs eigene qsort
ist zum Vergleich enthalten (Johnny's ist schneller!). Ich werde zum Abschluss einen abschließenden Vergleich durchführen.
quelle
Antworten:
150 Zeichen
Schnelle Sorte.
Komprimiert.
quelle
150 Zeichen (ohne Leerzeichen)
quelle
if(*w<*v) { t=v[++l]; v[l]=*w; *w=t; }
kann seinif(*w<*v) t=v[++l], v[l]=*w, *w=t;
67 7069 ZeichenÜberhaupt nicht schnell, aber unglaublich klein. Es ist eine Mischung aus einer Auswahlsortierung und einem Blasensortierungsalgorithmus, denke ich. Wenn Sie tatsächlich versuchen, dies zu lesen, sollten Sie wissen, dass dies
++i-v-n
dasselbe ist wie++i != v+n
.quelle
if(a)b
->a?b:0
speichert ein Zeichen.++i-v-n
ist++i != v+n
natürlich das Gleiche wie nur in einer Bedingung.if(*i>v[n])...
->*i>v[n]?...:0
123 Zeichen (+3 Zeilenumbrüche)
Eine Standard-Shell-Sortierung, komprimiert.
PS: entdeckt, dass es immer noch 10x langsamer als Quicksort ist. Sie können diesen Eintrag auch ignorieren.
quelle
395 Zeichen
Zusammenführen, sortieren.
Formatiert.
quelle
331326327312 ZeichenSortiert Radix 8 Bits gleichzeitig. Verwendet einen ausgefallenen Bithack, um negative Floats korrekt zu sortieren (gestohlen von http://stereopsis.com/radix.html ). Es ist nicht so kompakt, aber es ist sehr schnell (~ 8x schneller als der schnellste vorläufige Eintrag). Ich hoffe auf eine Geschwindigkeit, die den Code übertrifft ...
quelle
511424 ZeichenRadixsort einbauen
Update: Wechselt bei kleineren Array-Größen zur Einfügesortierung (erhöht die Benchmark-Leistung um den Faktor 4,0).
Formatiert.
quelle
void*
inqsort
(Zeile 88) wirft die Zeigerarithmetik ab.121114111 ZeichenNur eine schnelle und schmutzige Blasensortierung mit Rekursion. Wahrscheinlich nicht sehr effizient.
Oder die lange Version
quelle
221193172 ZeichenHeapsort - Nicht das kleinste, aber vorhanden und garantiert O (n * log (n)) Verhalten.
Komprimiert.
quelle
TEST_COUNT
= 3000 ausführen , scheint mindestens ein Test fehlgeschlagen zu sein.154166 ZeichenOK, hier ist eine längere, aber schnellere Quicksortierung.
Hier ist eine Korrektur, um sortierte Eingaben zu überleben. Und formatiert, da Leerzeichen nicht zählen.
quelle
150 Zeichen
Shellsort (mit Knuth-Lücke).
Formatiert.
quelle
C 270 (Golf)
Erläuterung: In einem leeren Array wird jede aufeinanderfolgende Mindestanzahl gespeichert. Ein int-Array ist eine Maske mit 0, die angibt, dass die Nummer noch nicht kopiert wurde. Nach Erhalt des Mindestwerts überspringt eine Maske = 1 bereits verwendete Zahlen. Anschließend wird das Array wieder in das Original kopiert.
Ich habe den Code geändert, um die Verwendung von Bibliotheksfunktionen zu vermeiden.
quelle
144
Ich nahm schamlos Johnnys Code, fügte eine winzige Optimierung hinzu und komprimierte den Code auf sehr schmutzige Weise. Es sollte kürzer und schneller sein.
Beachten Sie, dass je nach Compiler die Sortierung (q, v + n- ++ q) durch die Sortierung (++ q, v + nq) ersetzt werden muss.
Eigentlich habe ich angefangen, meinen Code zu formen und ihn zu optimieren, aber anscheinend hat Johnny bereits die richtigen Entscheidungen getroffen. Also habe ich quasi seinen Code erhalten. Ich habe nicht an den Goto-Trick gedacht, aber ich konnte darauf verzichten.
quelle
228 Zeichen
Radixsort.
quelle