差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:data_structure:treap [2019/10/18] – [__slots__] ikatakos | programming_algorithm:data_structure:treap [2019/10/18] – [ノードの表現] ikatakos | ||
---|---|---|---|
行 77: | 行 77: | ||
ただ、特にPyPyで実行することを考えると、データ構造をなるべく型を統一した単純な形にすることで、型推論が働きやすくなり、高速になるといわれている。 | ただ、特にPyPyで実行することを考えると、データ構造をなるべく型を統一した単純な形にすることで、型推論が働きやすくなり、高速になるといわれている。 | ||
(この辺、どういったデータ構造ならいいのかいまいちわかっていないが) | (この辺、どういったデータ構造ならいいのかいまいちわかっていないが) | ||
+ | |||
+ | * [[https:// | ||
+ | |||
+ | > 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. | ||
+ | |||
+ | |||
よって、このような表現にすることで、若干の高速化が期待できる。 | よって、このような表現にすることで、若干の高速化が期待できる。 | ||
行 91: | 行 101: | ||
</ | </ | ||
- | ただし、1つのノードの情報を縦断的に確認するのはすげーやりづらいので、視認性は下がる。 | + | ただし、クラスによる実装では '' |
- | + | 共通indexによる実装では '' | |
- | また、クラスによる実装では '' | + | |
- | 共通indexによる実装では '' | + | |
===末端ノード=== | ===末端ノード=== |