Radix Heap

色々なダイクストラ高速化

• 最後にpopした値より小さな数値は入れられない
• push時に更新不要、pop時でも更新をある程度Lazyにすることが許されるので、データ量の多い優先キューとして高速

• C++での実装
  • GitHub - iwiwi/radix-heap: An implementation of radix heap

pythonでも楽に試してみたいなーと思ったけど、途中で「数値を2進数にした時の桁数」を頻繁に取得する必要がある。

C++など組み込みでサポートしてたらいいんだけど、pythonではいまいち適した方法がない。int.bit_length()はあるけど、遅い。

• 4. 組み込み型 — Python 3.5.2 ドキュメント
  • このページのint.bit_length()の項に、「次と等価です」として2進数文字列に変換して先頭の0を取るコードが出てくるけど、等価っていうのは内部で同じことをやっているのか、結果が同じになるというだけなのか、どっちだろう。

まぁ、pythonにははじめからheapqモジュールがあるし、使った方がいいよね。

やってることはそれなりに簡単そうなので、コードの流れだけでもメモ。

# python
class RadixHeapInt32:
    v = [[] for _ in range(33)]

    def __init__(self):
        self.last = 0

    def push(self, x):
        self.v[(x ^ self.last).bit_length()].append(x)

    def pop(self):
        if not self.v[0]:
            cv = next(x for x in self.v if x)
            self.last = min(cv)
            for x in cv:
                self.push(x)
            cv.clear()
        return self.v[0].pop()