差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| programming_algorithm:data_structure:treap [2019/10/18] – [__slots__] ikatakos | programming_algorithm:data_structure:balancing_binary_search_tree:treap [2019/11/28] (現在) – ↷ programming_algorithm:data_structure:treap から programming_algorithm:data_structure:balancing_binary_search_tree:treap へページを移動しました。 ikatakos | ||
|---|---|---|---|
| 行 11: | 行 11: | ||
| 多数のリスト参照が積もり積もって遅くなる。 | 多数のリスト参照が積もり積もって遅くなる。 | ||
| - | Treapは比較的、参照すべきノードが少ないので、若干有利となる。 | + | Treapは比較的、参照すべきノードが少ないので、その意味では若干有利となる可能性がある。 |
| ただし、木の平衡がきちんとは保たれず効率性は落ちるので、トレードオフ。 | ただし、木の平衡がきちんとは保たれず効率性は落ちるので、トレードオフ。 | ||
| 行 20: | 行 20: | ||
| * 基本的にこれ見ればわかる | * 基本的にこれ見ればわかる | ||
| - | =====高速化===== | + | =====Pythonでの高速化===== |
| なんかいろんな要因が絡みそうで、個別の検証は行っていない。 | なんかいろんな要因が絡みそうで、個別の検証は行っていない。 | ||
| 行 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による実装では '' | + | |
| ===末端ノード=== | ===末端ノード=== | ||
