Treap

概要

平衡二分探索木の一種
乱数を使って木の平衡を保つ
- メチャクチャ運が悪いと遅くなるけど、普通は大丈夫
平衡二分探索木の中では比較的実装が簡単

Pythonのようにリストアクセスが遅い言語では、AVL木・赤黒木などでは平衡を保つための木の回転が頻繁に生じ、多数のリスト参照が積もり積もって遅くなる。

Treapは比較的、参照すべきノードが少ないので、その意味では若干有利となる可能性がある。

ただし、木の平衡がきちんとは保たれず効率性は落ちるので、トレードオフ。

仕組み

プログラミングコンテストでのデータ構造 2　～平衡二分探索木編～
- 基本的にこれ見ればわかる

Pythonでの高速化

なんかいろんな要因が絡みそうで、個別の検証は行っていない。

ランダム値生成

競技プログラミングの範疇では、平衡二分探索木を使う問題はせいぜい $N=10^6$ くらいの挿入・削除操作を想定すればいい。

よってpriorityに使う乱数も、それなりにばらけた値を返す、高速な、周期が $10^6$ くらいの疑似乱数生成アルゴリズムがあればいい。

それには、Xorshiftがよく使われている。 $x,y,z,w$ の初期値はランダムでいいが、128bitでは下記の値が比較的周期が長いらしい。実際は64bitもあればいい。

        
              def xor128(self):
    x = 123456789
    y = 362436069
    z = 521288629
    w = 88675123
 
    while True:
        t, x, y, z = x ^ ((x << 11) & 0xffffffff), y, z, w
        w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))
        yield w

random.randint() を毎回呼ぶより、xor128の方が若干速くなる。また、64bitの精度があればいいのであれば、演算回数を減らしたxor64がより速くなる。

第一回日本最強プログラマー学生選手権決勝 C 問題
- 提出 random.randint() 3841 ms
- 提出 xor128 3737 ms
- 提出 xor64 3586 ms
この問題はTreapのinsert以外にも色々処理があるので、目安程度に

ノードの表現

木構造のノード表現には、主に以下の形式が思いつく。

クラス
配列

        
              # クラス実装
class Node:
    def __init__(self, x):
        self.data = x
        self.priority = random.random()
        self.left = None
        self.right = None
 
# 配列実装
node = [x, random.random(), None, None]

ただ、特にPyPyで実行することを考えると、データ構造をなるべく型を統一した単純な形にすることで、型推論が働きやすくなり、高速になるといわれている。（この辺、どういったデータ構造ならいいのかいまいちわかっていないが）

PyPy - Performance

Keep it simple

Simple is better than complex. The PyPy JIT is not very smart; the simpler your code is the better it will run. Here again, though, you face a tradeoff: you may need to pay with more algorithmic complexity in order to avoid brute-force operations that are O(n**2) or worse.

Write plain-vanilla code in plain-vanilla ways. The PyPy JIT has many productions that optimize a common usage pattern against an uncommon usage pattern.

よって、このような表現にすることで、若干の高速化が期待できる。

        
              # 1情報1配列で保持し、ノードはその共通indexとして表現する
 
node = 1
 
left     = [0, 2, 0, 1, ...]
right    = [1, 2, 3, 0, ...]
data     = [3, 4, 7, 9, ...]
priority = [0, 5, 10, 15, ...]

ただし、クラスによる実装では node.left.data = xx「ノードの左の子の値はxx」と、日本語と考える順番が一致するので読みやすいが、共通indexによる実装では data[left[node]] = xx となり、若干読みにくい。

末端ノード

上記の表現をする上で、Noneにあたるindexを1つ決めておく。（たとえば0）

例えば、部分木のサイズを示す count という情報も管理し、ちょくちょくアクセスするときなど、末端ノードをNoneで持っていると「node is None なら0, それ以外ならnode.count」と場合分けの必要があるが、共通indexでは末端ノードを示すindexにも情報を与えておくことで場合分けの必要が無くなり、高速になる。

ただし、「自身の親」など、同じ末端ノードでも位置によって値が変化する情報を持たせたい場合は、このような共通の末端ノードを用いる方法は使えない。

slots

Pythonではクラスに __slots__ を定義することができる。これは、インスタンスの属性をslotsに限定し、新たな属性の追加を禁止する役割がある。

        
              class Image(object):
    __slots__ = ['id', 'caption', 'url']
 
    def __init__(self, id, caption, url):
        self.id = id
        self.caption = caption
        self.url = url

メモリの節約と同時に、属性へのアクセスも若干速くなるとされている。

しかし、Treapをクラス化して用いる場合、slotsを定義してもほとんど効果が得られなかった。

提出 slots 定義 3692 ms
提出 slots 未定義 3687 ms

何だろう、独自slotsを定義するのに時間かかるのかな。

スコープの隔離が主な目的でクラスを定義し、インスタンス化するのは1個、というシングルトンみたいなクラスは、slotsの恩恵が受けにくいのかも知れない。もっと大量にインスタンス化するようなクラス向けということか。それとも時間計測に用いた問題ではたまたま効果が無くなるような要因があった？

関数内ローカル変数化

Treapをクラス化して用いる場合、各クラスメンバは self.left などと self からアクセスする。

頻繁にアクセスする場合、関数冒頭で left = self.left などとローカル変数化すると、若干高速になる。

すごく泥臭いし無駄に可読性が下がるが、なかなか無視できないくらいの効果はある？

提出ローカル変数化（上記slots 定義の再掲） 3692 ms
提出ローカル変数化なし 1ケースでTLE（実行制限 4s）

ただ、TLEになったケース以外では、ローカル変数化してない方が逆に高速な例もあった。いまいちよくわからん。