In dieser Optimierungsaufforderung schreiben Sie ein Programm, das ein einzelnes Array sortiert, indem Sie nur Elemente vergleichen, indem Sie den Benutzer auf stdout auffordern, Vergleichsergebnisse auf stdin einzugeben.
Das folgende Protokoll ist zeilenbasiert. Jedes Mal, wenn Sie in stdout drucken oder aus stdin lesen, wird davon ausgegangen, dass eine neue Zeile folgt. In der folgenden Frage wird davon ausgegangen, dass der Benutzer (gelesen: das Bewertungsprogramm) ein Array hat, das in einem 0-basierten indizierten Array mit dem Namen sortiert werden soll array
. Aus technischen Gründen empfehle ich, nach jedem Druck zu spülen, um kräftig zu werden.
- Als ersten Schritt muss Ihr Programm die Arraygröße
n
von stdin lesen . - Dann können Sie so oft Sie möchten
a < b
mit zwei ganzen Zahlen auf stdout drucken0 <= a, b < n
. Dann gibt der Benutzer1
in stdin ifarray[a] < array[b]
und0
andernfalls ein. Sobald Ihr Programm überzeugt ist, dass es die Reihenfolge des Arrays korrekt abgeleitet hat, muss es
a ...
in stdout drucken , wobei...
eine durch Leerzeichen getrennte Liste von Ganzzahlen die Reihenfolge angibt. Wenn Ihr Programm ausgegeben wirda 3 0 1 4 2
, bedeutet dies, dass Ihr Programm abgeleitet hatarray[3] <= array[0] <= array[1] <= array[4] <= array[2]
Beachten Sie, dass Ihr Programm den Inhalt von nie kannte
array
und dies niemals tun wird.
Sie können nur <
nach stdin fragen , um das Array zu sortieren. Sie können andere Vergleichsoperationen durch diese Äquivalenzen erhalten:
a > b b < a
a <= b !(b < a)
a >= b !(a < b)
a != b (a < b) || (b < a)
a == b !(a < b) && !(b < a)
Da Ihr Programm mit dem Scoring-Programm auf stdout interagiert, drucken Sie die Debug-Informationen an stderr.
Ihr Programm wird mit dem folgenden Python-Programm bewertet:
from __future__ import print_function
from subprocess import Popen, PIPE
import sys, random
def sort_test(size):
array = [random.randrange(0, size) for _ in range(size)]
pipe = Popen(sys.argv[1:], stdin=PIPE, stdout=PIPE, bufsize=0, universal_newlines=True)
print(str(size), file=pipe.stdin); pipe.stdin.flush()
num_comparisons = 0
while True:
args = pipe.stdout.readline().strip().split()
if args and args[0] == "a":
answer_array = [array[int(n)] for n in args[1:]]
if list(sorted(array)) != answer_array:
raise RuntimeError("incorrect sort for size {}, array was {}".format(size, array))
return num_comparisons
elif len(args) == 3 and args[1] == "<":
a, b = int(args[0]), int(args[2])
print(int(array[a] < array[b]), file=pipe.stdin); pipe.stdin.flush()
num_comparisons += 1
else:
raise RuntimeError("unknown command")
random.seed(0)
total = 0
for i in range(101):
num_comparisons = sort_test(i)
print(i, num_comparisons)
total += num_comparisons
print("total", total)
Sie bewerten Ihr Programm durch Eingabe python score.py yourprogram
. Die Bewertung erfolgt, indem Ihr Programm ein zufälliges Array jeder Größe von 0 bis 100 sortiert und die Anzahl der von Ihrem Programm angeforderten Vergleiche zählt. Diese zufälligen Arrays können Duplikate haben. Ihr Algorithmus muss in der Lage sein, gleiche Elemente zu verarbeiten. Falls es Duplikate gibt, gibt es keine Anforderungen an die Reihenfolge der gleichen Elemente. Wenn [0, 0]
es sich also um ein Array handelt, spielt es keine Rolle, ob Sie a 0 1
oder ausgeben a 1 0
.
Möglicherweise optimieren Sie nicht speziell für die bestimmten Arrays, die das Scoring-Programm generiert. Ich kann den RNG-Samen jederzeit ändern. Antworten, die integrierte Sortieralgorithmen verwenden, dürfen aus Gründen des Interesses veröffentlicht werden, sind jedoch nicht konkurrierend.
Programm mit der niedrigsten Punktzahl gewinnt.
Antworten:
Python, Punktzahl 23069
Dies verwendet den Ford-Johnson-Algorithmus zum Sortieren von Zusammenführungseinfügungen.
quelle
Python 3, 28462 Punkte
Schnelle Sorte. Der Drehpunkt befindet sich ganz links.
Die Punktzahl wird erwartet, weil:
Bewertungen für jede getestete Größe:
quelle
Python 2 (nicht konkurrierend), 23471 Punkte
Bewertungen für jede getestete Größe:
quelle
Python, 333300 Punkte
Dies ist ein Beispielprogramm, das die einfachste Form von Bubblesort implementiert und immer
n*(n-1)
Vergleiche pro Array durchführt.Ich habe dieses Programm durch Speichern
sort.py
und Tippen bewertetpython score.py python sort.py
.quelle
print
wie eine Funktion aussehe.