[GO] [Neuerfindung der Räder] Von Menschen betriebene Turniersorte [Python]
Umgebung: Python 2.7
Einführung
Wenn Sie das übergeben, was Sie sortieren möchten, werden die Elemente in einer Turnierformel kombiniert und die beiden Elemente manuell verglichen. Das Endergebnis ist ein vollständiges Ranking ohne Überlappung im Ranking. (Alle Ordnungsbeziehungen)
Vielleicht gibt es eine bessere Implementierung, aber ich wollte sehen, ob das, was ich mir ausgedacht habe, richtig ist, also habe ich eine gemacht.
__ Nachtrag (04.12.2014) __ Zu natürliche Implementierung → Re: Human Power Sorting [Python]
Überblick über den Algorithmus
Der Umriss des Algorithmus ist wie folgt.
Platzieren Sie zunächst alle Elemente in einem Turnierformat und lassen Sie sie gegeneinander antreten (siehe Abbildung oben). Behalten Sie zu diesem Zeitpunkt einen Taple, der den Gewinner am Anfang des Index hat. Der endgültige Gewinner ist der stärkste dieser Faktoren. Das ist also Rang 1 (grüner Pfeil).
Zweitens ist Rang 2 der zweitstärkste, also hättest du natürlich irgendwo gegen diesen Champion verlieren sollen. Sie können dies anhand des zuvor gespeicherten Taples suchen (der Teil, der von Rot und dem roten Pfeil umgeben ist). Wenn Sie diese Elemente in einem Turnierformat neu positionieren und gegeneinander antreten (siehe Abbildung unten), gewinnt Rang 2 definitiv.
Danach muss Rang 3 in den vorherigen Schlachten durch Rang 2 besiegt worden sein (der Teil, der von Blau und dem blauen Pfeil umgeben ist), also werde ich dies wiederholen. Auf diese Weise können Sie sehen, dass die Elemente im Array-Rang in absteigender Reihenfolge des Ranges gespeichert sind, und Sie können fortfahren, bis keine Elemente mehr vorhanden sind.
Codekommentar
Kommentar?
Ich habe in Python geschrieben, was den obigen Algorithmus implementiert.
Wie ich in der Beschreibung schrieb, wurde dies zur Selbstanalyse geschrieben (lacht). Ich wollte etwas, das irgendwann zu einem Ranking werden würde, wenn ich die gleichen Genres auflistete und antwortete, welches mir gefiel. ist.
- Das Argument wird von argparse verwaltet.
- Wie Sie in den letzten 7 Zeilen sehen können, wird die Funktion rekursiv ausgeführt.
Eine Sache, die Sie beachten sollten, ist, wenn die Anzahl der Elemente 1 beträgt und das Turnier nicht stattfinden kann oder wenn das endgültige Ende erreicht ist.
~~ Der in der Klasse Rank auskommentierte Funktionsvergleich wurde verwendet, wenn die Eingabe jedes Mal in der Testphase schwierig war, und wurde auch verwendet, um den später angezeigten Berechnungsbetrag zu messen. Andere Druckkommentare dienen ebenfalls zum Testen. Wenn Sie dies anzeigen, ist es einfacher zu verstehen, wie es funktioniert. ~~
(Ergänzung) In dem vergriffenen Kommentar wird die Anzeige durch Hinzufügen von "-v" zur Option nach der Wahrheit von self.verbose unterteilt. Es scheint einen besseren Weg zu geben. Compare wechselt auch zwischen default_compare und auto_compare mit der Option "-t".
ranking.py
#!/usr/bin/env python
# -*- coding:utf-8 -*-
#
# written by ssh0, September 2014.
description = """
Ranking-Schnittstelle zur Selbstanalyse.
In dieser Anwendung
Erstellen Sie eine Vergleichsfrage basierend auf der angegebenen Liste
Das Ranking ist abgeschlossen, wenn der Benutzer darauf antwortet.
"""
import argparse
import sys
class Rank:
def __init__(self, args):
self.pair = [] # match pairs
self.rank = [] # sorted list
self.args = args
self.verbose = self.args.verbose
if self.args.test:
self.compare = self.auto_compare
else:
self.compare = self.default_compare
self.N = 0
def default_compare(self, a, b):
self.N += 1
print '\nQ[%d] which ones do you like?' % self.N
print ' [j]: %s, [k]: %s' % (a, b)
key_input = raw_input(">>> ")
if key_input == 'j':
ans = (a, b)
elif key_input == 'k':
ans = (b, a)
else:
raise ValueError('please select by "j" or "k".')
return ans
def auto_compare(self, a, b): #Zur Messung
self.N += 1
ans = (max(a, b), min(b, a))
return ans
def first_matching(self, data):
n = len(data)
N = 1
if n == 0:
self.func_finally()
elif n == 1:
self.rank.append(data[0])
if self.verbose:
print "n = 1 ::",
print self.rank
return self.first_matching(self.narrowing(data[0]))
else:
while n >= N:
N = N*2
unseed = 2*n - N
first_winner = []
for i in range(unseed/2):
a, b = data.pop(0), data.pop(0)
ans = self.compare(a, b)
g, l = ans[0], ans[1]
first_winner.append(g)
self.pair.append((g, l))
data += first_winner
member = [(data[2*i], data[2*i+1]) for i in range(len(data)/2)]
return member
def tournament(self, data):
member = self.first_matching(data)
if self.verbose:
print "next tournament",
print member
while len(member) > 1:
winner = []
for p in member:
ans = self.compare(p[0], p[1])
g, l = ans[0], ans[1]
self.pair.append((g, l))
winner.append(g)
member = [(winner[2*i], winner[2*i+1]) for i
in range(len(member)/2)]
ans = self.compare(member[0][0], member[0][1])
top, l = ans[0], ans[1]
self.pair.append((top, l))
self.rank.append(top)
if self.verbose:
print "pairs",
print self.pair
print "champion",
print top
print "current rank",
print self.rank
return top
def narrowing(self, x):
unsort_table = []
for_delete = []
for i, pair in enumerate(self.pair):
if x == pair[0]:
unsort_table.append(pair[1])
for_delete.append(i)
for j in for_delete:
self.pair[j] = None
self.pair = [k for k in self.pair if k is not None]
if self.verbose:
print "unsort_table",
print unsort_table
return unsort_table
def func_finally(self):
result = ''
for i, x in enumerate(self.rank):
result += ' %d: %s\n' % (i+1, x)
if self.args.outfile:
outfile = self.args.outfile
with open(outfile, 'a') as out:
out.write(result)
if not self.args.test:
print result
print "these result is saved in '%s'." % outfile
else:
print self.N
elif self.args.test:
print self.N
else:
print result
sys.exit()
if __name__ == '__main__':
parse = argparse.ArgumentParser(description=description)
parse.add_argument('-l', '--list',
dest='obj',
nargs='*',
type=str,
help='list of some objects',
default=argparse.SUPPRESS
)
parse.add_argument('-o', '--output',
dest='outfile',
type=str,
help='OPTIONAL: file to save output',
default=None
)
parse.add_argument("-v", "--verbose",
help="increase output verbosity",
action="store_true"
)
parse.add_argument("-t", "--test",
help="auto comparing mode (int, descending) for test",
action="store_true"
)
args = parse.parse_args()
data = args.obj
rank = Rank(args)
def ranking(pair_lists):
result = rank.narrowing(rank.tournament(pair_lists))
return result
a = ranking(data)
while True:
a = ranking(a)
Ausführungsbeispiel 1
Das Ausführungsbeispiel lautet wie folgt.
➤ python ranking.py -l apple orange banana melon berry
Q[1] which ones do you like?
[j]: apple, [k]: orange
>>> j
Q[2] which ones do you like?
[j]: banana, [k]: melon
>>> j
Q[3] which ones do you like?
[j]: berry, [k]: apple
>>> j
Q[4] which ones do you like?
[j]: banana, [k]: berry
>>> k
Q[5] which ones do you like?
[j]: apple, [k]: banana
>>> j
Q[6] which ones do you like?
[j]: orange, [k]: banana
>>> j
1: berry
2: apple
3: orange
4: banana
5: melon
Ausführungsbeispiel 2
Da es schwierig ist zu sagen, ob die Sortierung nur mit dem obigen Beispiel richtig durchgeführt wird, werde ich den Fall zeigen, in dem die Zahlen von 0 bis 9 in absteigender Reihenfolge sortiert werden, indem das Debug angezeigt wird. Pairs ist die Liste der Tupel in der Abbildung, und unsorted_table sind die Elemente des nächsten Turniers, die durch die Pfeile in der Abbildung angegeben werden. In der zweiten Hälfte kann die Anzahl der Elemente von unsorted_table 1 werden, daher ist es notwendig, die Verarbeitung zu trennen. Der Prozess endet, wenn unsorted_table leer ist.
➤ python ranking.py -l 1 0 6 3 4 9 5 7 8 2 -v
Q[1] which ones do you like?
[j]: 1, [k]: 0
>>> j
Q[2] which ones do you like?
[j]: 6, [k]: 3
>>> j
next tournament [('4', '9'), ('5', '7'), ('8', '2'), ('1', '6')]
Q[3] which ones do you like?
[j]: 4, [k]: 9
>>> k
Q[4] which ones do you like?
[j]: 5, [k]: 7
>>> k
Q[5] which ones do you like?
[j]: 8, [k]: 2
>>> j
Q[6] which ones do you like?
[j]: 1, [k]: 6
>>> k
Q[7] which ones do you like?
[j]: 9, [k]: 7
>>> j
Q[8] which ones do you like?
[j]: 8, [k]: 6
>>> j
Q[9] which ones do you like?
[j]: 9, [k]: 8
>>> j
pairs [('1', '0'), ('6', '3'), ('9', '4'), ('7', '5'), ('8', '2'), ('6', '1'), ('9', '7'), ('8', '6'), ('9', '8')]
champion 9
current rank ['9']
unsort_table ['4', '7', '8']
Q[10] which ones do you like?
[j]: 4, [k]: 7
>>> k
next tournament [('8', '7')]
Q[11] which ones do you like?
[j]: 8, [k]: 7
>>> j
pairs [('1', '0'), ('6', '3'), ('7', '5'), ('8', '2'), ('6', '1'), ('8', '6'), ('7', '4'), ('8', '7')]
champion 8
current rank ['9', '8']
unsort_table ['2', '6', '7']
Q[12] which ones do you like?
[j]: 2, [k]: 6
>>> k
next tournament [('7', '6')]
Q[13] which ones do you like?
[j]: 7, [k]: 6
>>> j
pairs [('1', '0'), ('6', '3'), ('7', '5'), ('6', '1'), ('7', '4'), ('6', '2'), ('7', '6')]
champion 7
current rank ['9', '8', '7']
unsort_table ['5', '4', '6']
Q[14] which ones do you like?
[j]: 5, [k]: 4
>>> j
next tournament [('6', '5')]
Q[15] which ones do you like?
[j]: 6, [k]: 5
>>> j
pairs [('1', '0'), ('6', '3'), ('6', '1'), ('6', '2'), ('5', '4'), ('6', '5')]
champion 6
current rank ['9', '8', '7', '6']
unsort_table ['3', '1', '2', '5']
next tournament [('3', '1'), ('2', '5')]
Q[16] which ones do you like?
[j]: 3, [k]: 1
>>> j
Q[17] which ones do you like?
[j]: 2, [k]: 5
>>> k
Q[18] which ones do you like?
[j]: 3, [k]: 5
>>> k
pairs [('1', '0'), ('5', '4'), ('3', '1'), ('5', '2'), ('5', '3')]
champion 5
current rank ['9', '8', '7', '6', '5']
unsort_table ['4', '2', '3']
Q[19] which ones do you like?
[j]: 4, [k]: 2
>>> j
next tournament [('3', '4')]
Q[20] which ones do you like?
[j]: 3, [k]: 4
>>> k
pairs [('1', '0'), ('3', '1'), ('4', '2'), ('4', '3')]
champion 4
current rank ['9', '8', '7', '6', '5', '4']
unsort_table ['2', '3']
next tournament [('2', '3')]
Q[21] which ones do you like?
[j]: 2, [k]: 3
>>> k
pairs [('1', '0'), ('3', '1'), ('3', '2')]
champion 3
current rank ['9', '8', '7', '6', '5', '4', '3']
unsort_table ['1', '2']
next tournament [('1', '2')]
Q[22] which ones do you like?
[j]: 1, [k]: 2
>>> k
pairs [('1', '0'), ('2', '1')]
champion 2
current rank ['9', '8', '7', '6', '5', '4', '3', '2']
unsort_table ['1']
n = 1 :: ['9', '8', '7', '6', '5', '4', '3', '2', '1']
unsort_table ['0']
n = 1 :: ['9', '8', '7', '6', '5', '4', '3', '2', '1', '0']
unsort_table []
1: 9
2: 8
3: 7
4: 6
5: 5
6: 4
7: 3
8: 2
9: 1
10: 0
Messung des Berechnungsbetrags
Übrigens, da dieses Programm selbst auf menschlichen Eingaben basiert, möchte ich, dass die Anzahl der Vergleiche am geringsten ist. Also habe ich gemessen, wie viele Vergleichsoperationen an N Elementen durchgeführt wurden.
Bereiten Sie ein Testskript wie unten gezeigt vor.
test_ranking.py
#!/usr/bin/env python
# -*- coding:utf-8 -*-
import numpy as np
import matplotlib.pyplot as plt
import commands
Ns = [10*i for i in range(1, 11)]
cal = []
for N in Ns:
raw = [i for i in range(N)]
x = np.random.choice(raw, N, replace=False)
lists = ''
for _x in x:
lists += str(int(_x)) + ' '
command = "python ranking.py -l %s -t" % lists
result = commands.getoutput(command)
cal.append(result)
f = plt.figure()
ax = f.add_subplot(111)
ax.plot(Ns, cal)
ax.set_xlabel(r"$N$")
ax.set_ylabel("calculate times")
plt.show()
Das als Ergebnis der Ausführung erhaltene Diagramm ist in der folgenden Abbildung dargestellt. Die horizontale Achse repräsentiert die Anzahl der Elemente N (in 10 Schritten) und die vertikale Achse repräsentiert die Anzahl der Vergleichsoperationen.
[Theoretische Grenzen der vergleichenden Sortierung (Wikipedia)](http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88#.E6.AF.94.E8 .BC.83.E3.82.BD.E3.83.BC.E3.83.88.E3.81.AE.E7.90.86.E8.AB.96.E9.99.90.E7.95.8C) ist $ O. Für n \ log n) $, $ 100 \ log 100 \ simeq 460.5 $ und $ N = 100 $ betrug der Umfang der Vergleichsoperation 626, sodass die Reihenfolge anscheinend nicht kleiner gemacht werden kann. Umgekehrt denke ich, dass der diesmal erstellte Algorithmus ein guter Vergleichssortierungsalgorithmus war.
Zusammenfassung
Die Turniersortierung selbst hätte irgendwo implementiert werden müssen, also hätte ich das Gleiche tun können, wenn ich den Vergleichsoperator selbst definieren müsste. Ich bin jedoch persönlich zufrieden, weil ich selbst darüber nachdenken konnte. Es ist mir egal, ob es eine Rad-Neuerfindung heißt. (Wenn Sie mit Methoden vertraut sind, lassen Sie es mich bitte wissen.)
Das? Was ist Selbstanalyse?
Recommended Posts