コレクション内の要素を削除するには

イディオム

コレクション内から特定の要素を削除するいくつかの手法を考えてみる。
（Objective-C, Java, C++ それぞれの場合。）


最も単純なのは、コレクションに対してインデックスを指定して削除するというものだ。

i番目の要素を削除する。

Objective-Cの場合1

NSMutableArray* array = [NSMutableArray array];
[array addObject:[NSNumber numberWithInt:0]];
[array addObject:[NSNumber numberWithInt:1]];
[array addObject:[NSNumber numberWithInt:2]];
[array addObject:[NSNumber numberWithInt:3]];
[array addObject:[NSNumber numberWithInt:4]];

// ...

[array removeObjectAtIndex:i];

Javaの場合1

List<Integer> list = new ArrayList<>();
list.add(0);
list.add(1);
list.add(2);
list.add(3);
list.add(4);

// ...

list.remove(i);

C++の場合1

std::vector<int> vct;
vct.push_back(0);
vct.push_back(1);
vct.push_back(2);
vct.push_back(3);
vct.push_back(4);

// ...

vct.erase(vct.begin() + i);


上記のやり方は簡単ではあるが、実際には、インデックスを指定して削除する、というよりも、コレクション内の要素を1つずつチェックして、ある条件を満たす場合に削除する、というシチュエーションの方が圧倒的に多いであろう。このとき、基本的には、「コレクション要素のイテレーション中」にコレクションの内容を変更してはならない。

たとえば、整数値コレクションから偶数要素を削除してみる。

以下のやり方はいずれもうまくいかない。

Objective-Cの場合2

int i = 0;

// ループ中に実行時エラーになる
for (NSNumber* n in array) {
    if (0 == [n integerValue] % 2) {
        [array removeObjectAtIndex:i];
    }
    else {
        ++ i;
    }
}

Javaの場合2

int i = 0;

// ループ中に実行時エラーになる
for (int n : list) {
    if (0 == n % 2) {
        list.remove(i);
    }
    else {
        ++ i;
    }
}

C++の場合2

int i = 0;

// 実行時エラーにはならないが、うまくいかない
std::for_each(vct.begin(), vct.end(), [&](int n)
{
    if (0 == n % 2)
    {
        vct.erase(vct.begin() + i);
    }
    else
    {
        ++ i;
    }
});


上記のやり方はいずれも、ループ内でコレクションのサイズを変更してしまっているために、イテレーションが途中からうまくいかなくなってしまっている。

単純な解決方法としては、コレクションをコピーした上でイテレーションすればよい。

Objective-Cの場合3

int i = 0;

// ARCを使わないのであれば、[[array copy] autorelease] と書くこと
for (NSNumber* n in [array copy]) {
    if (0 == [n integerValue] % 2) {
        [array removeObjectAtIndex:i];
    }
    else {
        ++ i;
    }
}

Javaの場合3

int i = 0;

for (int n : new ArrayList<>(list)) {
    if (0 == n % 2) {
        list.remove(i);
    }
    else {
        ++ i;
    }
}

C++の場合3

int i = 0;
std::vector<int> copy(vct);

std::for_each(copy.begin(), copy.end(), [&](int n)
{
    if (0 == n % 2)
    {
        vct.erase(vct.begin() + i);
    }
    else
    {
        ++ i;
    }
});

イテレーション中にコレクションを変更したいがためだけにコレクションを丸ごとコピーするなんてのは、いかにも非効率的に思えるが、まともに動くことは動く。ただ、いずれも拡張for文を備えた言語であるのに、ループ外にインデックス変数iを用意してしまっているのがどうにも煩わしい。

さて、ここまであえて3つの言語で似たような書き方をしてみたが、Objective-CとJavaにおけるコレクションというのは、要素がすべてオブジェクト型である。C++のvectorはテンプレートであり、上記の例では要素はint値である。

Objective-CやJavaのコレクションクラスには、論理的等価性検証（Objective-CのisEqual, Javaのequals）のオーバーライド（Objective-CのisEqual, Javaのequals）を使って「指定したオブジェクトを探し出し、削除する」というメソッドが用意されている。その機構を使えば、インデックスカウンタを使わずに、コレクションから要素を削除することができる。

C++で同じようなことをしたければ、operator==とremove_ifなどを使ってもっと効率的に実現できるが、vector自体にはどうも、「指定した値と==な要素を削除する」というメソッドは用意されていないようだ。まあ、もっとも、そんなものはなくても困らない。

Objective-Cの場合4

for (NSNumber* n in [array copy]) {
    if (0 == [n integerValue] % 2) {
        [array removeObject:n];    // nのisEqual:がtrueになるオブジェクトを探して削除する
    }
}

Javaの場合4

for (Integer n : new ArrayList<>(list)) {
    if (0 == n % 2) {
        list.remove(n);    // nのequalsがtrueになるオブジェクトを探して削除する
    }
}

Javaに関してはAuto Boxingとオーバーロードが重なっているので、少し判りづらいが、やっていることはObjective-Cの場合とほぼ同じである。「Javaの場合4」で呼び出しているremoveメソッドは、「Javaの場合3」までで呼び出していた
「インデックスを指定して削除する」
メソッドではなく、
「指定した要素とequalsな最初の要素を削除する」
メソッドである。そのために、引数にint値ではなく、明示的にIntegerを渡すように変更している。

しかしながら、結果的に、おそらく4のやり方は、3のやり方よりもかなり低速である。コレクションのイテレーション中に、さらにコレクションの先頭要素から、trueが返るまで、equalsやisEqualを呼び出しているであろうことは想像するに容易い。そもそも、3の時点で既に、コレクションをコピーするという点で明らかに無駄である。


まあ、4のやり方が良いなんてのは、もちろん冗談だ。
もう少しまともそうな方法もある。

Objective-Cの場合5

// 削除する要素をコピーしておくための別の配列を用意
NSMutableArray* discards = [NSMutableArray array];

for (NSNumber* n in array) {
    if (0 == [n integerValue] % 2) {
        [discards addObject:n];    // 削除条件を満たす要素を削除用配列に保存
    }
}

[array removeObjectsInArray:discards];    // 一括削除

上記のコードは、イテレーションのためのコピーは避けたものの、結局他の配列を用意してしまっている。削除メソッドの呼び出しが1回で済むことと、コレクションを丸ごとコピーするわけではないことを考えれば、他のObjective-Cでのイディオムに比べれば、幾分マシかもしれない。しかし、removeObjectsInArrayのロジックが、おそらく、4の場合と同じように、isEqualの検査が多数走っていると思われるため、結果的にどちらが高速になるかは微妙なところ。

Javaにはもう少しスマートなやり方がある。
さあ、今こそ拡張for文の呪縛から解き放たれるときだ。

Javaの場合5

for (Iterator<Integer> itr = list.iterator(); itr.hasNext(); ) {
    Integer n = itr.next();

    if (0 == n % 2) {
        itr.remove();
    }
}

元祖Iteratorの力を思い知った。「Objective-Cの場合5」に比べて、無駄なコードがなくて読みやすい。たぶん、Javaでは、多くの場合に、このやり方が一番効率的だと思う。



さて、本題はここからだ。

「C++の場合3」を改良して、「Javaの場合5」に近いやり方に変更してみる。

C++の場合4

for (auto itr = vct.begin(); vct.end() != itr; )
{
    if (0 == *itr % 2)
    {
        itr = vct.erase(itr);
    }
    else
    {
        ++ itr;
    }
}


ポイントはeraseメソッドの戻り値を使うことである。eraseメソッドは、要素を削除した後、次の要素を指すイテレーターを返してくれる。そいつを使ってイテレーションを先に進めるようにすれば、eraseによって要素を削除してしまっても、後続する要素をイテレーションできるという寸法だ。コレクションのコピーを無駄に生成していたのを排除することができたため、今までのやり方の中では最速であろう。

が、まだもう少しスマートに記述できる。

vectorの内部は動的配列の構造をしているため、線形リスト構造に比べて、要素の追加、削除が遅い。即ち、もし、vector内に削除すべき要素が多数存在する可能性が高いのであれば、要素を1つずつ削除するよりも、削除すべき要素だけ端にソートした上で一括削除した方が高速になる可能性は高い。

C++の場合5

auto tail_itr = std::remove_if(vct.begin(), vct.end(), [](int n)
{
    return 0 == n % 2;
});

vct.erase(tail_itr, vct.end());

このやり方が一番効率的な可能性が高いし、読みやすい。と思う。
それに、ラムダ式を使っているので、なんとなくカッコイイ。

remove_ifの第3引数には、bool operator()(int/* vectorの要素と同じ型 */)を持つ関数オブジェクトか、同じシグニチャのラムダ式を渡して、引数を検証の上、その値をvector内から削除するならばtrue, 保持するならfalseを返すようにする。remove_ifは実際に要素の削除を行うわけではなく、削除すべき要素をコレクションの後ろに隔離して、有効な要素の末尾の後ろを指すイテレーターを返す。従って、実際にvector内から不要な要素を削除するには、remove_if完了後に、eraseで実際の削除を実行する必要がある。

さらに無駄を省くならば、eraseの呼び出しさえも避けて、その後、tail_itr以降の要素を参照しないようにしてしまえばよい。

いずれにしても、削除条件さえ簡潔であれば、無理なく1行で書ける。

たとえば、きちんと削除する場合、

vct.erase(std::remove_if(vct.begin(), vct.end(), [](int n){return 0 == n % 2;}), vct.end());

エレガント。


【ベンチマーク】
※注意：コンパイルオプションなどは調整していないので、あまりアテにならない数字だと思います。

10万個のランダムな整数値のコレクションを構成し、
（ここから計測開始）
コレクション内から偶数の要素を完全に削除
（計測終了）
処理時間とコレクションに残った要素数を表示する。
要素数が5万前後であることを確認。

Objective-Cの場合3   227ミリ秒
Objective-Cの場合4    10秒以上（中断）
Objective-Cの場合5   245ミリ秒

Javaの場合3          438ミリ秒
Javaの場合4         2212ミリ秒
Javaの場合5          439ミリ秒

C++の場合3           351ミリ秒
C++の場合4           346ミリ秒
C++の場合5             2ミリ秒

Objective-Cの3, 5のやり方が、C++の3, 4のやり方と同等以上に高速というのは意外だった。なにやら最適化が働いているような気がする。「C++の場合5」に関しては、リリースモードでコンパイルすると、0〜1ミリ秒という結果になった。まさに圧倒的実行速度。

結論としてはやはり、それぞれの5のやり方が、可読性、実行効率、間違いにくさ、どれを取っても安定して良さそうな気がする。



おしまい