マージ法

マージ法(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つずつ数を選んで和をある決められた数にできるか、という問題を解くことができます。これもよく使うアルゴリズムです。