読者です 読者をやめる 読者になる 読者になる

マージソート(SQLite)

アルゴリズムの名前が分からないのですが、途中でマージは使われているのでマージソートの一種でしょうか。ぼくが見ているSQLiteのままのコード(pcache.cの457行目-のpcacheMergeDirtyListがmergeに、pcacheSortDirtyListがsortに対応します)だと一緒にすると失敗するので調節しました。SQLiteの中では2^(N_SORT_BUCKET-1)(N_SORT_BUCKET=32)までの数のページを扱えることになっているのですが、そんな状況考えられないのでSQLITEの方にバグがあるとしても、バグに出会うことは無いでしょう。
インプットのリストの長さが2^(N_SORT_BUCKET-1)になるまではsort(inp)関数の中のa[N_SORT_BUCKET]はs(n)をn要素をソートしたリストを表すことにすると、a[0]=s(1), a[1]=s(2), a[2]=s(4),..a[i]=s(2^i)になっていることがわかります。試しにa[k+1]に値が入る瞬間をかんがえてみると、a[0]-a[k]が埋まった状態で再びwhileステートメントの一番上に来ます。a[0]はNoneではないのでp=sort(2)が入ります、次にp=s(s(2),s(2))=s(4), p = s(s(4), s(4)) = s(8)...と変化していきます。要するにi=kのときpにはa[0]-a[i]までが含む、全ての要素をソートしたものが入り、i=k+1のときにa[k+1]=pになってbreakします。このときpのsortした要素の数は1+sum_{i=0}^{k}2^{i}=2^{k+1}です。だからa[k+1]=s(2^{k+1})というわけです。

#!/usr/bin/env python2.6
import unittest
import random
import heapq
def merge_sort(a, b):
    if a is None:
        return b
    elif b is None:
        return a
    return [i for i in heapq.merge(a, b)]
N_SORT_BUCKET = 6
def sort(inp):
    a = [None] * N_SORT_BUCKET
    is_reached = False
    while len(inp):
        p = [inp.pop()]
        for i in range(N_SORT_BUCKET):
            if a[i] is None:
                a[i] = p
                break
            else:
                p = merge_sort(a[i], p)
                a[i] = None
        if i == N_SORT_BUCKET-1:
            """
              To get here, there need to be 2^(N_SORT_BUCKET-1) elements
              in the input list.
            """
            a[i] = p
            is_reached = True
    p = a[0]
    for i in range(1, N_SORT_BUCKET):
        p = merge_sort(p, a[i])
    return p, is_reached

    return range(20)
class SortTests(unittest.TestCase):
    def test_merge_sort(self):
        ia = [i*2 for i in range(5)]
        ib = [i*2+1 for i in range(5)]
        self.assertEqual(range(10), merge_sort(ia, ib))
    def test_sort(self):
        for i in range(1, N_SORT_BUCKET-1):
            inp = range(1<<i)
            random.shuffle(inp)
            self.assertEqual((range(1<<i), False), sort(inp))
        inp = range(1<<(N_SORT_BUCKET-1))
        random.shuffle(inp)
        self.assertEqual((range(1<<(N_SORT_BUCKET-1)), True), sort(inp))
if __name__ == '__main__':
    unittest.main()