要約
$O(\log N)$ で挿入・削除する方法
-
std.container.rbtree.RedBlackTreeを利用する
以下の方法では $ O(N) $になってしまう。
std.algorithm.mutation.remove()- スライスと配列の結合(
~)を使った方法
単純な queue を実装する場合は、先頭の要素を取得・削除するだけでいいので std.range.primitives.popFrontで十分。
参考: popFornt
計算回数が O(N) になる方法について
std.algorithm.mutation.remove()
こんな書き方。
import std;
void main() {
int[] array = [1, 2, 3, 4, 5, 6];
array = array.remove(2); // array = [1, 2, 4, 5, 6]
}
remove() 後の配列は使えないので、再代入する必要がある。
array.remove(2) 直後(再代入前)のarrayは[1, 2, 4, 5, 6, 6] と削除された分を前に詰めた配列に変更されている。そのときの処理で $O(N)$ のループがあるらしい。
詳細は、以下のコードにある。
std.algorithm.mutation.d
スライスと配列の結合(~)を使った方法
import std;
void main() {
int[] array = [1, 2, 3, 4];
array = array[0..2] ~ array[3..$]; // array = [1, 2, 4]
array = array[0..1] ~ 5 ~ array[1..$]; // array = [1, 5, 2, 4]
}
スライスを取る操作は$O(1)$であるが、後ろ側のスライスを結合する際に$O(N)$の時間がかかってしまっているらしい。
計算回数 O(log N) にするにはどうするか
RedBlackTree を使う。
赤黒木という二分木構造がある。
例えば以下のようにできる。
テンプレート引数の true は同じ値の重複を許すことを意味する。
（デフォルトは false なので、この引数を指定しないと木の要素のうち同じ値は1つだけになる。）
実行例のように、重複する要素を削除するときは1つだけ削除される。
import std;
void main() {
auto tree = redBlackTree!(true, int)();
foreach(_; 0..20) {
int n = uniform(0, 10);
tree.insert(n);
}
writeln("## Insert 完了 ##");
tree.length.writeln;
tree[].writeln;
writeln("## 0を1つ削除 ##");
tree.removeKey(0);
tree.length.writeln;
tree[].writeln;
}
## Insert 完了 ##
20
[0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 3, 4, 6, 6, 6, 6, 7, 7, 8, 8]
## 0を1つ削除 ##
19
[0, 0, 0, 0, 0, 2, 2, 2, 2, 3, 4, 6, 6, 6, 6, 7, 7, 8, 8]
本当に $O(\log N)$ で挿入・削除ができているのか確かめてみる。
さっきのコードのループを$10^5$回に増やして時間を計測する。
（仮に1回の挿入・削除に $O(N)$ かかっていれば、N回ループを回しているので全体の計算回数は $O(N^2) \sim 10^{10}回$ となり、現実的な実行時間にならない。）
import std;
void main() {
auto tree = redBlackTree!(true, int)();
auto insertStart = Clock.currTime();
foreach(_; 0..10e5) {
int n = uniform(0, 10);
tree.insert(n);
}
auto insertEnd = Clock.currTime();
writeln("## INSERT完了 ##");
writeln(insertEnd - insertStart);
auto removeStart = Clock.currTime();
foreach(i; 0..10e5) {
int n = i.to!int % 10;
tree.removeKey(n);
}
auto removeEnd = Clock.currTime();
writeln("## REMOVE完了 ##");
writeln(removeEnd - removeStart);
}
## INSERT完了 ##
323 ms and 341 μs
## REMOVE完了 ##
226 ms and 932 μs
良さげ。
まとめ
AtCoderのコンテストで、remove で1回、スライスの結合で1回TLEを出しました。
$N \sim O(10^5)$ 回くらいのループの中で array.sum() を使って、予期せずTLEを出したこともあるので、組み込み関数の中での計算回数を失念しがちです。
使う関数全ての公式ドキュメントを読むのは非現実的だとしても、利用する関数の中でどんな処理をしているか（計算回数、副作用 etc）を意識しておかないといけないなと思います。