Il est probablement naturel d'entendre que mes amis étudient de temps en temps l'implémentation d'algorithmes et travaillent sur l'implémentation de sortes de fusion. Un jeu mystérieux a eu lieu dans lequel il était préférable de le mettre en œuvre avec le moins de lignes possible car c'était un gros problème. J'ai entendu dire que mon ami voulait le faire en Python, alors j'ai décidé de le faire en Python. Je ne perdrai pas
--Utilisez un tableau de données dans lequel les nombres de 1 à 10 sont disposés de manière aléatoire.
Le code de la partie commune est le suivant
from data import generate_data
data = generate_data() #Les nombres de 1 à 10 sont alignés en morceaux
print(data)
#Mis en œuvre ci-dessous
Il y a data.py dans un autre fichier, et la fonction generate_data là générera les données.
Les données seront quelque chose comme [5, 1, 3, 9, 2, 8, 7, 4, 10, 6] ''. Je viens de créer correctement le contenu de data.py``, je vais donc l'omettre ici.
Quand je l'ai écrit selon les règles ci-dessus, c'est devenu comme ça.
from data import generate_data
data = generate_data() #Les nombres de 1 à 10 sont alignés en morceaux
print(data)
#Mis en œuvre ci-dessous
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]))
production
[5, 1, 3, 9, 2, 8, 7, 4, 10, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Ce n'était pas un problème même si on me disait "Long. En trois lignes". Je vais l'expliquer pour le moment.
Le tri de fusion semble être basé sur la "méthode de règle de division", et il semble que le tableau de données est une fois divisé à l'unité minimale, et les données sont correctement sélectionnées à partir de chaque donnée divisée, combinées, puis réorganisées. La personne qui a pensé Étant donné que de nombreux ancêtres ont expliqué divers détails de l'algorithme, je vais l'omettre ici.
Ainsi, le résultat de la mise en œuvre des trois lignes ci-dessus est Ligne 1: Split Ligne 2: Rejoindre Ligne 3: sortie Les rôles sont divisés comme ça.
Commençons par le «fractionnement».
C'est le code en question.
Code "Split"
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))])]
Si la séquence de données est «[7, 6, 3, 2, 4, 5, 1, 8]», le but du «fractionnement» provient de cette séquence.
[
[
[6, 7],
[2, 3]
],
[
[4, 5],
[1, 8]
],
]
Cela signifie qu'un tableau multiple avec une structure hiérarchique comme celle-ci sera généré. Divisez l'unité minimale en deux pour que le nombre d'éléments soit de 2 ou moins, et si le nombre d'éléments dans l'unité minimale est de 2 ou moins, classez-les par ordre croissant. Je fais quelque chose comme ça. Celles qui sont ordonnées par ordre croissant sont à l'origine le rôle de "couplage", mais il est pratique de le faire ici, donc je le ferai à ce stade.
La fonction "split" est à l'origine comme ça.
Forme originale
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)]
Lorsque le nombre d'éléments est égal ou inférieur à 2, le tableau est renvoyé dans l'ordre croissant, et dans d'autres cas, la structure hiérarchique ci-dessus peut être réalisée en divisant en deux en gauche '' et droite '' et en reculant. Je vais.
Après ʻelse``, si vous utilisez la variable de half_count`` directement en la remplaçant par `len (data) // 2, vous pouvez éviter d'utiliser la variable. Oh, j'ai utilisé gauche '' et `` droite '' une seule fois! Si vous le faites tel quel dans le prix de retour
La valeur de retour est folle ~
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))])]
Sera. Ah, «if» et «else» n'ont qu'une seule phrase «return». C ’est un opérateur ternaire et ce n’ est qu ’une ligne.
C'est une ligne avec un opérateur ternaire
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))])]
Cela se calme jusqu'à la sensation. S'il n'y a qu'un seul `` retour '' dans la fonction, utilisez une expression lambda
Faites-en un style lambda
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))])]
Il s'intègre parfaitement dans une seule ligne. C'est bien de pouvoir utiliser la récurrence même dans les expressions lambda.
C'est le code en question.
Code "Rejoindre"
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 ... Le but de «rejoindre» est
Données après division
[
[
[6, 7],
[2, 3]
],
[
[4, 5],
[1, 8]
],
]
Il s'agit de combiner les données divisées dans l'ordre à partir de la couche inférieure, et enfin de les combiner toutes pour revenir à la forme originale d'une couche. Comme un flux
Flux 1
[
[2, 3, 6, 7],
[1, 4, 5, 8]
]
Flux 2
[1, 2, 3, 4, 5, 6, 7, 8]
Etc. Pour réaliser ce flux, la fonction `` fusion ''
--Les éléments gauche et droit de l'argument sont combinés lorsque leurs éléments enfants sont numériques
Je vais faire quelque chose comme ça. C'est difficile à comprendre même si vous l'expliquez avec des mots, alors regardons le code.
La fonction "combiner" ressemble à l'origine à ceci.
Forme originale
def merge(left, right):
if type(left[0]) is int and type(right[0]) is int: #Les deux lorsque l'élément enfant est un nombre
result = [] #Préparez une nouvelle baie
for i in range(len(left) + len(right)):
# left,Lorsque le bon élément disparaît, faites apparaître celui qui existe encore
if len(left) == 0:
result.append(right.pop(0))
elif len(right) == 0:
result.append(left.pop(0))
#S'il en reste les deux, éclatez le plus petit
elif left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
return result
else:
"""
Selon la hiérarchie, les éléments enfants peuvent être des nombres ou des tableaux, même au même niveau.
Retraite avec l'élément enfant tel quel
"""
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]))
Voir les commentaires pour les détails de mise en œuvre. Je l'ai fait intentionnellement avec «if-elif-else». Cela signifie que vous pouvez utiliser l'opérateur ternaire pour créer la valeur de retour sur une ligne, et vous pouvez également écrire la fonction sur une ligne avec une expression lambda, comme dans le cas de "split"!
Quand j'ai essayé d'exprimer le résultat '' en notation d'inclusion de liste, je craignais que pop '' réduise correctement les éléments, mais quand je l'ai essayé, il a diminué correctement. J'ai pu représenter la partie `` pour '' sur une ligne en utilisant la notation d'inclusion de liste et l'opérateur ternaire.
Code "Sortie"
print(merge(divide(data)[0], divide(data)[1]))
À l'origine ici
data = divide(data)
print(merge(data[0], data[1]))
Et `` divide '' ne doit être exécuté qu'une seule fois, mais comme vous pouvez le voir, c'est une perte du nombre de lignes à exercer 1 pour sécuriser la variable, donc je l'exécute de force deux fois. Eh bien, si le nombre d'éléments est d'environ 10, c'est une erreur.
Je suis sûr que ce sera le code gagnant pour le Fucking Code of the Year Awards en moi. Merci beaucoup.
Recommended Posts