環境: Python 2.7
はじめに
ソートしたいものを渡すと、トーナメント式に要素が組み合わせられて、2個の要素の比較を人力で行う。最終的に得られる結果は、順位に重複のない完全なランキングとなる。（全順序関係）
多分もっとうまい実装はあるだろうけど、思いついたことが正しいか試したかったので作ってみました。
追記(2014/12/04)
あまりにも自然な実装→Re:人力ソート【Python】
アルゴリズムの概要
アルゴリズムの骨子を図にすると、次のようになります。
まず、全ての要素を、トーナメント形式に配置し、競わせます（上の図）。このとき、勝者をインデックスの先頭に持つようなタプルを保持しておきます。最終的に勝ち残ったものはこの要素の中で最も強いものです。したがってこれはランク1です（緑の矢印）。
次に、ランク2は2番目に強いわけなので、当然のことながら今回のチャンピオンにどこかで負けているはずです。これは先ほど保持しておいたタプルから検索できます（赤で囲まれた部分と赤い矢印）。したがってこれらの要素を再びトーナメント形式に配置して競わせると（下の図）、ランク2が必ず優勝します。
以後、ランク3はそれまでの戦いの中で必ずランク2に敗れているはずなので（青で囲まれた部分と青の矢印）・・・と繰り返していきます。このようにしていくとランクの高い順から配列rankに格納され、最終的に要素がなくなるまで続ければ良いことが分かります。
コード解説
解説？
上のアルゴリズムを実現するものをPythonで書きました。
descriptionに書いているように、これは自己分析用に書いたものです(笑)同じジャンルのものを羅列して、どっちが好きかを答えていくと最終的にランキングになるものが欲しかったのです。
- argparseで引数管理してます。
- 最後の7行で分かるとおり、関数を再帰的に実行します。
気をつけるべき点としては、要素数が1でトーナメントができない時や、最後の終了のタイミングがどこになるかという点です。
クラスRankの中でコメントアウトしてある関数compareは、テストの段階でいちいち入力するのが面倒くさい時に使ったもので、また後に示す計算量の計測に用いたものです。それ以外のprint のコメントアウトもテスト用です。 これを表示させると、どのように動いているか理解しやすいと思います。
(追記)printのコメントアウトは、オプションに"-v"を付けることで、self.verboseの真偽によって表示を分けるようにしました。もっとうまいやり方がありそう。compareもdefault_compareとauto_compareを、オプションの"-t"で切り替えるように。
ranking.py
#!/usr/bin/env python
# -*- coding:utf-8 -*-
#
# written by ssh0, September 2014.
description = """
自己分析用ランク付けインターフェース。
このアプリケーションでは
与えたリストをもとに比較質問を作成し、
ユーザーがそれに答えていくとランキングが完成する。
"""
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): # 計測用
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)
実行例1
実行例は以下のようになります。
➤ 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
実行例2
上の例だけではちゃんとソートできているかわかりにくいので、デバッグ表示をして、0〜9までの数字を大きい順にソートした場合を載せておきます。pairsが図で言うところのタプルのリストで、unsorted_tableが図で矢印で指定された、次のトーナメントの要素たちです。後半になるとunsorted_tableの要素数が1になる時があるので、処理を分ける必要があります。unsorted_tableが空になったとき、過程を終了します。
➤ 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
計算量の計測
さて、このプログラム自体が人間の入力を前提としたものである以上、比較の回数が最も小さくあってほしいですね。ということで、N個の要素に対して何回の比較演算がなされているかを測定してみました。
下のようにテスト用のスクリプトを用意しまして、
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()
実行した結果得られたグラフは下図のとおりです。横軸は要素数N（10刻み）を表しており、縦軸は比較演算の回数を表しています。
比較ソートの理論限界(Wikipedia)は$O(n\log n)$で、$100\log 100 \simeq 460.5$に対して、$N=100$で比較操作の量が626でしたから、オーダーとしてはこれ以上小さくすることはできなさそうです。逆に言うと、今回作成したアルゴリズムは、いい比較ソートアルゴリズムだったと言えると思います。
まとめ
トーナメントソート自体はどこかで実装されているはずなので、その比較演算子の定義を自分で定義していく形にすれば、同じようなことができたかもしれませんね。でも、自分で考えてここまでできたので、個人的には満足です。車輪の再発明と言われようと気にしません。（メソッドなど詳しい方はそっと教えてくださいませ）
あれ？自己分析ってなんだっけ？