Algorithm

はじめに 動かしながらゼロから学ぶLinuxカーネルの教科書 第2版 上記の技術書を読んでいてLinuxスケジューラの話が出てきた。CFSもEEVDFも赤黒木を使っている。赤黒木とは何かを調べていくうちにAVL木との比較が面白かったので、両方Pythonで実装してベンチマークを取った。 実装コードはClaude (Anthropic) により生成。リポジトリは以下。 https://github.com/wasuken/avl-rb-tree 自己平衡二分探索木とは まず前提として、ただの二分探索木には問題がある。 挿入順: 1, 2, 3, 4, 5 1 \ 2 \ 3 \ 4 ← 一直線になる 挿入順によっては木が一直線になり、検索がO(n)に劣化する。これを解決するのが自己平衡二分探索木で、挿入・削除のたびに自動でバランスを取り直す。AVL木と赤黒木はどちらもこのカテゴリに属する。 AVL木 1962年にソ連の数学者Adelson-VelskyとLandis（AVLの名前の由来）が考案した世界初の自己平衡二分探索木。 バランスの管理方法 各ノードに高さ（height）を持たせ、左右の高さの差（バランス係数）が常に1以内になるよう管理する。 def _balance_factor(self, node): return self._height(node.left) - self._height(node.right) 差が2以上になったら回転で修正する。 回転 回転は「親子関係を1段入れ替えるだけ」の操作。二分探索木の順序を壊さずに形だけ変える。 rotate_right(y): y x / \ / \ x C → A y / \ / \ A t2 t2 C t2 は回転で行き場を失う孫ノード。二分探索木の順序的に x < t2 < y が保証されているので、yの左に付け替えるだけでよい。 バランス崩れのパターンは4つ（LL, RR, LR, RL）で、それぞれ1〜2回の回転で解消できる。 挿入・削除 挿入・削除のたびに _rebalance が呼ばれ、高さの更新とバランスチェックが走る。 ...

問題概要 整数で表される小惑星の配列 asteroids が与えられる。各小惑星について： 絶対値：大きさ 符号：方向（正=右、負=左） 全て同じ速度で移動 衝突ルール： 小さい方が爆発 同じ大きさなら両方爆発 同じ方向に移動する小惑星は衝突しない 全ての衝突後の状態を返せ。 失敗した実装 from collections import deque class Solution: def asteroidCollision(self, asteroids: List[int]) -> List[int]: stack = [] for aster in asteroids: if len(stack) <= 0 or (aster <= 0) == (stack[-1] <= 0): stack.append(aster) else: while len(stack) > 0 and (aster <= 0) != (stack[-1] <= 0) and abs(aster) > abs(stack[-1]): stack.pop() if len(stack) <= 0 or (stack[-1] <= 0) == (aster <= 0): stack.append(aster) elif abs(aster) == abs(stack[-1]): stack.pop() return stack 問題点 同じ条件判定 if len(stack) <= 0 or (stack[-1] <= 0) == (aster <= 0) が2箇所に重複 制御フローが複雑で読みにくい (aster <= 0) != (stack[-1] <= 0) は「符号が異なる」を検出するが、衝突しないケースも含む 最適解 class Solution: def asteroidCollision(self, asteroids: List[int]) -> List[int]: stack = [] for asteroid in asteroids: while stack and asteroid < 0 < stack[-1]: # 右向き vs 左向きの衝突が発生 if abs(stack[-1]) < abs(asteroid): # 右向きが小さい → 爆発して次の右向きとも衝突判定 stack.pop() continue elif abs(stack[-1]) == abs(asteroid): # 同じ大きさ → 両方爆発 stack.pop() break else: # 衝突しなかった or 左向きが勝った stack.append(asteroid) return stack わかったこと 1. ループ条件の本質 asteroid < 0 < stack[-1] これは (asteroid < 0) and (0 < stack[-1]) と同じ。つまり： ...