マージ法(Merge algorithm)は、ソートされた二つの列を合体して一つのソートされた列を作るアルゴリズムです。
原理は非常に簡単です。例えば次のような列があったとして、
2 4 6 8 ...
3 6 9 12 ...
まず、両方の列の先頭を比較します。小さいほうの2を取り出して新たな列の先頭とします。
4 6 8 ...
3 6 9 12 ...
2
再び両方の列の先頭を比較します。3のほうが小さいので、取り出して新たな列に加えます。
4 6 8 ...
6 9 12 ...
2 3
同じことを繰り返して、
6 8 ...
6 9 12 ...
2 3 4
このとき両方の先頭が同じなので、両方取り出してここでは一つだけ新たな列に加えます。
8 ...
9 12 ...
2 3 4 6
これをPythonで書くと次のようになります。
from itertools import count, islice def gen_merge(g1, g2): n1 = next(g1) n2 = next(g2) while True: if n1 == n2: yield n1 n1 = next(g1) n2 = next(g2) elif n1 < n2: yield n1 n1 = next(g1) else: yield n2 n2 = next(g2) # generate multiple of n def gen_mul(n): return (m * n for m in count(1)) for n in islice(gen_merge(gen_mul(2), gen_mul(3)), 10): print n,
2 3 4 6 8 9 10 12 14 15
ちょっと長いですね。こう書けば短くなりますが、ちょっとわかりにくいですね。
def gen_merge(g1, g2): f = 0 while True: if f <= 0: n1 = next(g1) if f >= 0: n2 = next(g2) f = cmp(n1, n2) yield n1 if f <= 0 else n2
このコードの問題点は無限列にしか適用できないことです。有限列になるとより複雑なコードになってしまいます(こういうとき、Haskellなら簡単なんですが)。しょうがないので、適当に無限列にしてしまいましょう。
INF = 10 ** 9 def gen_inf(g): for n in g: yield n while True: yield INF
さて、今までは2つのジェネレータのマージを考えてきましたが、3つ以上の場合はどうしたらいいでしょう。最初、PriorityQueueを考えていましたが、どうもPythonのPriorityQueueは遅いようです。よく考えてみると、gen_mergeを再帰的によいですね。4つジェネレータがあったら、まず2つずつでマージしてそれぞれジェネレータを作り、それをまたマージすればよいです。
def gen_union(gen): l = len(gen) if l == 1: return gen[0] elif l == 2: return gen_merge(gen[0], gen[1]) else: return gen_merge(gen_union(gen[:l/2]), gen_union(gen[l/2:])) gen = map(gen_mul, (2, 3, 5, 7)) for n in islice(gen_union(gen), 15): print n,
2 3 4 5 6 7 8 9 10 12 14 15 16 18 20
こうすると簡潔でしかも非常に速く動作します。
マージ法とほとんど同じアルゴリズムで、2つのソートされた列から一致する値を取り出すという方法があります。実はProject Eulerではこちらのほうがよく使われます。
def gen_coincident(g1, g2): n1 = next(g1) n2 = next(g2) while True: if n1 == n2: yield n1 n1 = next(g1) n2 = next(g2) elif n1 < n2: n1 = next(g1) else: n2 = next(g2) for n in islice(gen_coincident(gen_mul(2), gen_mul(3)), 10): print n,
6 12 18 24 30 36 42 48 54 60
これを少し改変すると、2つの集合の中から1つずつ数を選んで和をある決められた数にできるか、という問題を解くことができます。これもよく使うアルゴリズムです。