前に書いたものを少し書き直します。
マージ法（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
これをScalaでStreamを使って書くと非常に素直に書けます。
def merge(s1 :Stream[Int], s2 :Stream[Int]) :Stream[Int] = (s1, s2) match { case (s1, Stream()) => s1 case (Stream(), s2) => s2 case (h1 #:: t1, h2 #:: t2) if h1 < h2 => h1 #:: merge(t1, s2) case (h1 #:: t1, h2 #:: t2) if h1 > h2 => h2 #:: merge(s1, t2) case (h1 #:: t1, h2 #:: t2) => h1 #:: merge(t1, t2) } def stream_mul(n :Int) = Stream.from(1).map(n *) val m2 = stream_mul(2) val m3 = Stream.from(1).map(3 *) println (merge(m2, m3).take(10).toList)
List(2, 3, 4, 6, 8, 9, 10, 12, 14, 15)
このコードは見ての通り有限列にも無限列にも対応しています。
さて、今までは2つのジェネレータのマージを考えてきましたが、3つ以上の場合はどうしたらいいでしょう。この場合、再帰的にマージをすればよいです。4つジェネレータがあったら、まず2つずつでマージしてそれぞれジェネレータを作り、それをまたマージします。
def union(ss :List[Stream[Int]]) :Stream[Int] = ss.size match { case 1 => ss(0) case 2 => merge(ss(0), ss(1)) case n => merge(union(ss.slice(0, n / 2)), union(ss.slice(n / 2, n))) } val ms = List.range(2, 6).map(stream_mul) println (union(ms).take(15).toList)
こうすると簡潔でしかも非常に速く動作します。
マージ法とほとんど同じアルゴリズムで、2つのソートされた列から一致する値を取り出すという方法があります。実はProject Eulerではこちらのほうがよく使われます。
def merge(s1 :Stream[Int], s2 :Stream[Int]) :Stream[Int] = (s1, s2) match { case (s1, Stream()) => s1 case (Stream(), s2) => s2 case (h1 #:: t1, h2 #:: t2) if h1 < h2 => merge(t1, s2) case (h1 #:: t1, h2 #:: t2) if h1 > h2 => merge(s1, t2) case (h1 #:: t1, h2 #:: t2) => h1 #:: merge(t1, t2) } def stream_mul(n :Int) = Stream.from(1).map(n *) val m2 = stream_mul(2) val m3 = Stream.from(1).map(3 *) println (merge(m2, m3).take(10).toList)
これを少し改変すると、2つの集合の中から1つずつ数を選んで和をある決められた数にできるか、という問題を解くことができます。これもよく使うアルゴリズムです。「蟻本」の最初の問題もこれであっさり解けます。
