計算量と速度
「計算量と速度」を扱った15問。日付を開くと、その日のドリルがそのまま読めます。日付の横の動物は難易度で、ハリネズミ・孔雀・バイソン・クジラの順に重くなります。
- C / DEBUG · 2026-10-31 測る処理が消えた ベンチマーク, 最適化による削除, デッドコード除去, as-ifルール, 観測できる動作, dead code elimination, as-if rule, microbenchmark
- C++ / DEBUG · 2026-10-30 一致しないと止まらない 破滅的バックトラック, 正規表現の曖昧さ, ReDoS, 入れ子の繰り返し, catastrophic backtracking, regex denial of service
- Rust / READ · 2026-10-26 両端から詰める挿入順 二分探索木の高さ, 挿入順による偏り, 退化した木, flat_map, binary search tree height, degenerate tree
- Rust / DEBUG · 2026-10-26 等しいキーで伸びる木 二分探索木の重複キー, 退化した木, matchのガード, duplicate keys, degenerate tree
- Rust / WRITE · 2026-10-13 葉から並んだパス 文字列の連結, 連結の計算量, 先頭への挿入, insert_str, push_str, string concatenation, quadratic time
- Rust / READ · 2026-10-13 連結のあとのas_ptr 文字列の連結, バッファの再利用, Add for String, 容量, ムーブ, string concatenation, buffer reuse, as_ptr
- Rust / DEBUG · 2026-10-13 取り出したまま帰る std::mem::take, 文字列の連結, 早期リターン, オペランドの評価順, データの消失, string concatenation, early return, evaluation order
- C / WRITE · 2026-10-12 末尾を返す追記 文字列の連結, 連結の計算量, 末尾ポインタ, strcat の再走査, string concatenation, stpcpy, end pointer
- C / READ · 2026-10-12 終端の1つ先から連結 文字列の連結, 連結の計算量, 末尾ポインタ, 後置インクリメント, ヌル終端, string concatenation cost, Shlemiel the painter, end pointer
- C / DEBUG · 2026-10-12 足し込んだ長さの先で溢れる snprintf の返り値, 切り捨て, size_t の回り込み, 文字列の連結, snprintf return value, truncation, unsigned wraparound, string concatenation
- Rust / WRITE · 2026-10-08 行に字下げを足す push_str, 文字列の連結, 字下げ, 償却定数時間, format!で毎回コピー, String building, linear time concatenation
- Rust / READ · 2026-10-08 連結後の先頭アドレス Stringの+演算子, 文字列連結, バッファの再利用, with_capacity, as_ptr, String concatenation, Add for String
- Rust / DEBUG · 2026-10-08 100万行の逆順 Stringの+演算子, 文字列を先頭に連結, 2乗の計算量, 行を逆順にする, quadratic string concatenation, prepend string, tac
- Rust / WRITE · 2026-09-18 先に容量を確保 with_capacity, 再確保, 文字列連結, capacity
- Rust / DEBUG · 2026-09-18 毎回作り直す文字列 format!, push_str, 計算量, string building