Radix Heap

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

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

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

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

    • このページの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()

programming_algorithm/data_structure/radix_heap.txt · 最終更新: 2017/10/08 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0