Es ist wahrscheinlich natürlich zu hören, dass meine Freunde von Zeit zu Zeit die Implementierung von Algorithmen studieren und an der Implementierung von Zusammenführungssorten arbeiten. Es wurde ein mysteriöses Spiel abgehalten, in dem es besser war, es mit so wenig Zeilen wie möglich zu implementieren, weil es eine große Sache war. Ich habe gehört, dass mein Freund es in Python machen wollte, also habe ich beschlossen, es in Python zu machen. Ich werde nicht verlieren
--Verwenden Sie ein Datenarray, in dem Zahlen von 1 bis 10 zufällig angeordnet sind.
Der Code des gemeinsamen Teils lautet wie folgt
from data import generate_data
data = generate_data() #Zahlen von 1 bis 10 sind in Stücken aufgereiht
print(data)
#Darunter implementiert
In einer anderen Datei befindet sich data.py, und die Funktion generate_data generiert dort die Daten.
Die Daten sind so etwas wie "[5, 1, 3, 9, 2, 8, 7, 4, 10, 6]".
Ich habe gerade den Inhalt von data.py richtig gemacht, also werde ich ihn hier weglassen.
Als ich es nach den oben genannten Regeln schrieb, wurde es so.
from data import generate_data
data = generate_data() #Zahlen von 1 bis 10 sind in Stücken aufgereiht
print(data)
#Darunter implementiert
divide = lambda data: data if len(data) == 1 else [min(data), max(data)] if len(data) <= 2 else [divide([data[i] for i in range(len(data) // 2)]), divide([data[i] for i in range(len(data) // 2, len(data))])]
merge = lambda left, right: [right.pop(0) if len(left) == 0 else left.pop(0) if len(right) == 0 else left.pop(0) if left[0] < right[0] else right.pop(0) for i in range(len(left) + len(right))] if type(left[0]) is int and type(right[0]) is int else merge(left, merge(right[0], right[1])) if type(left[0]) is int else (merge(merge(left[0], left[1]), right) if type(right[0]) is int else merge(merge(left[0], left[1]), merge(right[0], right[1])))
print(merge(divide(data)[0], divide(data)[1]))
Ausgabe
[5, 1, 3, 9, 2, 8, 7, 4, 10, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Es war kein Problem, auch wenn mir "Lang. In drei Zeilen" gesagt wurde. Ich werde es vorerst erklären.
Die Zusammenführungssortierung scheint auf der "Teilungsregelmethode" zu basieren, und es scheint, dass das Datenarray einmal auf die minimale Einheit aufgeteilt ist und die Daten aus den jeweils geteilten Daten entsprechend ausgewählt, kombiniert und dann neu angeordnet werden. Die Person, die dachte Die Details des Algorithmus werden hier weggelassen, da viele Vorfahren verschiedene Dinge erklärt haben.
Das Implementierungsergebnis der obigen drei Zeilen ist also Zeile 1: Teilen Zeile 2: Beitreten Zeile 3: Ausgabe Die Rollen sind so aufgeteilt.
Beginnen wir mit "Teilen".
Dies ist der betreffende Code.
"Split" -Code
divide = lambda data: data if len(data) == 1 else [min(data), max(data)] if len(data) <= 2 else [divide([data[i] for i in range(len(data) // 2)]), divide([data[i] for i in range(len(data) // 2, len(data))])]
Wenn das Datenarray "[7, 6, 3, 2, 4, 5, 1, 8]" ist, ist der Zweck des "Aufteilens" von diesem Array.
[
[
[6, 7],
[2, 3]
],
[
[4, 5],
[1, 8]
],
]
Dies bedeutet, dass ein Mehrfacharray mit einer solchen hierarchischen Struktur generiert wird. Teilen Sie die Mindesteinheit in zwei Hälften, sodass die Anzahl der Elemente 2 oder weniger beträgt. Wenn die Anzahl der Elemente in der Mindesteinheit 2 oder weniger beträgt, ordnen Sie sie in aufsteigender Reihenfolge an. Ich mache so etwas. Diejenigen, die in aufsteigender Reihenfolge angeordnet sind, sind ursprünglich die Rolle der "Kopplung", aber es ist zweckmäßig, dies hier zu tun, also werde ich es an dieser Stelle tun.
Die "Split" -Funktion ist ursprünglich so.
Ursprüngliche Form
def divide(data):
if (len(data) <= 2):
return data if len(data) == 1 else [min(data), max[data]]
else:
half_count = len(data) // 2
left = [data[i] for i in range(half_count)]
right = [data[i] for i in range(half_count, len(data))]
return [divide(left), divide(right)]
Wenn die Anzahl der Elemente 2 oder weniger beträgt, wird das Array in aufsteigender Reihenfolge zurückgegeben, und in anderen Fällen kann die obige hierarchische Struktur realisiert werden, indem in "links" und "rechts" in zwei Hälften geteilt und zurückgezogen wird. Ich werde.
Wenn Sie nach "else" die Variable "half_count" direkt mit "len (data) // 2" verwenden, können Sie die Verwendung der Variablen vermeiden. Oh, ich habe left und right nur einmal benutzt! Wenn Sie es so machen, wie es innerhalb des Rückgabepreises liegt
Der Rückgabewert ist verrückt ~
def divide(data):
if (len(data) <= 2):
return data if len(data) == 1 else [min(data), max[data]]
else:
return [divide([data[i] for i in range(len(data) // 2)]), divide([data[i] for i in range(len(data) // 2, len(data))])]
Wird sein.
Ah, sowohl if als auch else haben nur einen return Satz. Es ist ein ternärer Operator und nur eine Zeile.
Es ist eine Zeile mit einem ternären Operator
def divide(data):
return data if len(data) == 1 else [min(data), max(data)] if len(data) <= 2 else [divide([data[i] for i in range(len(data) // 2)]), divide([data[i] for i in range(len(data) // 2, len(data))])]
Es beruhigt sich auf das Gefühl. Wenn die Funktion nur eine "Rückgabe" enthält, verwenden Sie einen Lambda-Ausdruck
Machen Sie es zu einem Lambda-Stil
divide = lambda data: data if len(data) == 1 else [min(data), max(data)] if len(data) <= 2 else [divide([data[i] for i in range(len(data) // 2)]), divide([data[i] for i in range(len(data) // 2, len(data))])]
Es passt perfekt in eine Linie. Es ist schön, Wiederholungen auch in Lambda-Ausdrücken verwenden zu können.
Dies ist der betreffende Code.
"Join" -Code
merge = lambda left, right: [right.pop(0) if len(left) == 0 else left.pop(0) if len(right) == 0 else left.pop(0) if left[0] < right[0] else right.pop(0) for i in range(len(left) + len(right))] if type(left[0]) is int and type(right[0]) is int else merge(left, merge(right[0], right[1])) if type(left[0]) is int else (merge(merge(left[0], left[1]), right) if type(right[0]) is int else merge(merge(left[0], left[1]), merge(right[0], right[1])))
Guhe, Nageyo ... Der Zweck des "Beitritts" ist
Daten nach der Teilung
[
[
[6, 7],
[2, 3]
],
[
[4, 5],
[1, 8]
],
]
Es besteht darin, die geteilten Daten in der Reihenfolge der unteren Ebene zu kombinieren und schließlich alle zu kombinieren, um zur ursprünglichen Form einer Ebene zurückzukehren. Als Fluss
Fluss 1
[
[2, 3, 6, 7],
[1, 4, 5, 8]
]
Fluss 2
[1, 2, 3, 4, 5, 6, 7, 8]
Und so weiter. Um diesen Fluss zu erreichen, wird die Funktion "Zusammenführen" verwendet
pop das kleinere der ersten linken und rechten Elemente und fügt sie als untergeordnete Elemente des neuen Arrays hinzu.Ich werde so etwas tun. Es ist schwer zu verstehen, selbst wenn Sie es in Worten erklären. Schauen wir uns also den Code an.
Die "Join" -Funktion ist ursprünglich so.
Ursprüngliche Form
def merge(left, right):
if type(left[0]) is int and type(right[0]) is int: #Beides, wenn das untergeordnete Element eine Zahl ist
result = [] #Bereiten Sie ein neues Array vor
for i in range(len(left) + len(right)):
# left,Wenn das richtige Element verschwindet, platzieren Sie das noch vorhandene
if len(left) == 0:
result.append(right.pop(0))
elif len(right) == 0:
result.append(left.pop(0))
#Wenn beide noch übrig sind, platzen Sie den kleineren
elif left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
return result
else:
"""
Abhängig von der Hierarchie können die untergeordneten Elemente auch auf derselben Ebene Zahlen oder Arrays sein.
Ziehen Sie sich mit dem untergeordneten Element so zurück, wie es ist
"""
if type(left[0]) is int:
return merge(left, merge(right[0], right[1]))
elif type(right[0]) is int:
return merge(merge(left[0], left[1]), right)
else:
return merge(merge(left[0], left[1]), merge(right[0], right[1]))
Einzelheiten zur Implementierung finden Sie in den Kommentaren. Ich habe es absichtlich mit "if-elif-else" vervollständigt. Dies bedeutet, dass Sie den ternären Operator verwenden können, um den Rückgabewert in eine Zeile zu setzen, und Sie können die Funktion auch in eine Zeile mit einem Lambda-Ausdruck schreiben, genau wie im Fall von "split"!
Als ich versuchte, "Ergebnis" in der Listeneinschlussnotation auszudrücken, war ich besorgt, dass "Pop" die Elemente richtig reduzieren würde, aber als ich es tatsächlich versuchte, nahm es richtig ab. Ich konnte den for Teil in einer Zeile mit der Listeneinschlussnotation und dem ternären Operator darstellen.
Code "Ausgabe"
print(merge(divide(data)[0], divide(data)[1]))
Ursprünglich hier
data = divide(data)
print(merge(data[0], data[1]))
Und dividieren sollte nur einmal ausgeführt werden, aber wie Sie sehen können, ist es eine Verschwendung der Anzahl von Zeilen, 1 zu üben, um die Variable zu sichern, also führe ich sie zwangsweise zweimal aus. Wenn die Anzahl der Elemente ungefähr 10 beträgt, ist dies ein Fehler.
Ich bin mir sicher, dass es der Gewinncode für die Fucking Code of the Year Awards in mir sein wird. Vielen Dank.
Recommended Posts