ゼロフィルのリンクトリスト
配列が与えられる。前から順に走査したい。削除をしたい。
要件
元の配列が長さNでも、削除後が長さMならO(M)で走査できる必要がある
ダミーの値を代入して読み飛ばす方式はNG
削除はO(1)でなければならない
要素を詰めるのはNG
PythonのリストのremoveはNG
与えられた配列と同じサイズのゼロフィルされた配列next, prevを用意する
削除する時
pythonprev[pos + 1 + next[pos]] += prev[pos] + 1
next[pos - 1 - prev[pos]] += next[pos] + 1要するに双方向リンクトリスト。
単純に構築すると
next[pos] = pos + 1 が初期値になるわけだが、そこからの差分だけを持つことでゼロフィルで初期化できるようにしたわけだ。削除しかしないなら絶対アドレスを持つ必要がないからこれでよい。挿入もするなら普通の双方向リストが良い。
先頭要素は番兵。削除してはいけない。
削除するとどうなるかはまだ考察してない。
作成時のインデックスでのランダムアクセスはO(1)
Related Pages
- →座標圧縮×setはメモリ食い×numba×numbaに複雑な型を渡す×numba_bisect×numpy.unique×長方形グラフ探索×番兵×numba_np.concatenate×csr_matrix×リンクトリスト×mprof×atcoder→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]