脳log[20260223]

2026年02月23日 (月) 「HalMat4194304 (@mat4194304): "ChatGPT『Ruby の Array#shift は「先頭を取り除き、残り全要素をずらす」ので、1回が O(配列長)』 へー5年やってて初めて知った | nitter」■嘘だよ。読んでね。真意が皮肉だとしても誰も得してないよ。「ruby/array.c at master · ruby/ruby」 8910 行目に rb_ary_shift_m の名前があって、rb_ary_shift_m を見ると無引数の場合は rb_ary_shift を呼んでいるのがわかる。rb_ary_shift を見ると rb_ary_behead を１を引数にして呼んでいる。rb_ary_behead を見ると要素が埋め込まれている場合と ARY_DEFAULT_SIZE (16) 未満の場合に MEMMOVE でずらしているけど、これはサイズが小さいときの例外で多くは ARY_INCREASE_PTR と ARY_INCREASE_LEN というマクロで済まされている。このマクロはもちろん線形時間を要するものではない。■ところで Enumerable#each_cons はなんか幅に比例した時間がかかるみたいで配列のスライスではないんだよな。Enumerable モジュールが Array#each しか利用できないとしても線形のメモリと時間で済ませられると思うんだけど、実際は二乗レベルの時間がかかって TLE の原因にしたことがある。