Radix Heap

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 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()