膨大な量のリストの中から不要な項目を削除する処理を高速化する方法があればご教示お願いします。

Question

＊現状
現在C#にてプログラミングをしているのですが、どうしても処理の遅さがネックとなって先に進めない状態が続いているため質問させていただきました。

＊質問内容
膨大な量のリストの中から不要な項目を削除する処理を高速化する方法があればご教示お願いします。

＊要件

• 約６００万件近いデータのリストがあり、その中から不要な項目を削除したいと考えております。
• 削除したい件数も５０万件近くあります。
• 削除したいデータが必ずしも６００万件のリストの中に存在するわけではないので、１つづつ存在するかを確認しなければなりません。
• １件１件のデータ自体は文字列で、例えば「花太郎」、「小太郎」みたいな文字列となっています。

＊問題点
データ内容自体は異なるのですが、下記のコードでも処理に約１時間ほどかかっています。

＊コード内容
データ内容を単純化するためにデータを文字数字にしています。

static void Main(string[] args)
{
    // 600万件分のリストを作成
    List<string> mainList = new List<string>();
    for(int i=0; i<6000000; i++)
    {
        mainList.Add(i.ToString());
    }

    // 50万件分のリストを作成
    List<string> deleteList = new List<string>();
    for(int i=0; i<500000; i++)
    {
        deleteList.Add(i.ToString());
    }

    // mainListの中にdeleteListの項目があれば削除する
    // ここの処理を高速化できないかを悩み中です。
    foreach (string deleteStr in deleteList)
    {
        mainList.Remove(deleteStr);
    }
}

＊補足
データベースが利用できない状況なので、リストで処理を行っています。
処理が早くできればList<string>である必要はないです。

Answer 1

Listからの削除は大変重い処理です。これはListが「配列(array)」と言われるデータ構造であるため、インデックスアクセスがO(1)になる代わりに、削除がO(n)になってしまうからです。ましてや、Removeで添字ではなくオブジェクトを指定する場合は、検索もO(n)になるため、さらに遅い原因になります。

つまり、オリジナルコードは削除のリスト分繰り返しているためO(n × m)です。(nはmainのサイズ、mはdeleteのサイズ)

解決策は二つ(順序重複維持あり)＋二つ(順序重複維持なし)ほどです。

###順序と重複を維持する場合

順序を維持し、また、重複している場合は重複したままにする場合です。

####連結リストを使う

「連結リスト(linked list)」といわれるデータ構造の場合は、削除はO(1)になります(代わりに、インデックスアクセスがO(n)です)。C#では連結リストとしてLinkedListが用意されていますので、こちらを使用すれば、速度アップになります。

と言いたいところですが、この方法ではそれほど速くなりません。

なぜなら、Removeで該当のオブジェクトを探す検索がO(n)の計算量が必要になるからです。削除が速いだけで見つけるのが速くなるわけではありません。結局O(n × m)になってしまいます。

####新たに配列を作る

削除するのではなく、削除対象ではない物だけ抜き出して、新しい配列にします。処理はLINQを使うとコードがすっきりするでしょう。また、削除のリストにHashSetを使うと削除対象かどうかのチェックも高速に行うことができます。

HashSetの作成はO(n)ですが、検索はO(1)です。配列作成も内部がO(1)ならO(n)になりますので、計算量はO(n + m)とかなり改善されます。

###順序と重複を維持しない場合

順序を維持し、また、重複している場合は重複したままにする場合です。

####並び替え済みリストを使う

並び替え済みリストの場合、検索がO(1)と高速になります。C#には並び替え済みのSortedListがありますのでこれが使用できます。ただし、削除はO(n)であり、オリジナルより速い程度です。結局O(n × m)になってしまいます。

重複は維持されますが、順序はソートされるために維持できません。

####ハッシュ化された集合を使う

順序や重複を維持しなければいいのであれば、ハッシュ化された集合が使用できます。検索も削除もほぼO(1)になるため、極めて高速です。

ハッシュ化された集合としてHashSetが使用できます。なお、HashSetでは順序もそのまま維持されるようです(正式ドキュメントが見つけられなかったので、知っている人は教えて欲しい)。ただし、重複は維持されません。

ただし、ハッシュ化された集合自体の作成にO(n)必要になりますので、そこは注意してください。ということで、計算量はO(n + m)とかなり改善されます。。

###検証コード

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

class MainClass
{
    static void Main(string[] args)
    {
        //int mainListSize = 6000000;
        //int deleteListSize = 500000;
        int mainListSize = 60000;
        int deleteListSize = 5000;

        Console.WriteLine("{0}個中{1}個を削除",
                          mainListSize, deleteListSize);

        // 600万件分のリストを作成
        var mainStopwatch = new Stopwatch();
        mainStopwatch.Start();
        var mainList = Enumerable.Range(0, mainListSize)
                                 .Select(i => i.ToString())
                                 .OrderBy(a => Guid.NewGuid())
                                 .ToList();
        mainStopwatch.Stop();
        Console.WriteLine("main 作成完了: {0} ms",
                          mainStopwatch.ElapsedMilliseconds);

        // 50万件分のリストを作成
        var deleteStopwatch = new Stopwatch();
        deleteStopwatch.Start();
        var deleteList = Enumerable.Range(0, deleteListSize)
                                   .Select(i => i.ToString())
                                   .OrderBy(a => Guid.NewGuid())
                                   .ToList();
        deleteStopwatch.Stop();
        Console.WriteLine("delete 作成完了: {0} ms",
                          deleteStopwatch.ElapsedMilliseconds);

        Console.WriteLine();

        List<string> list;

        list = Original(new List<String>(mainList),
                        new List<String>(deleteList));
        Console.WriteLine("サイズ: {0}", list.Count);
        Console.WriteLine("最初: {0}", list[0]);

        Console.WriteLine();

        list = UseLinkedList(new List<String>(mainList),
                             new List<String>(deleteList));
        Console.WriteLine("サイズ: {0}", list.Count);
        Console.WriteLine("最初: {0}", list[0]);

        Console.WriteLine();

        list = CreateListWithHashset(new List<String>(mainList),
                          new List<String>(deleteList));
        Console.WriteLine("サイズ: {0}", list.Count);
        Console.WriteLine("最初: {0}", list[0]);

        Console.WriteLine();

        list = UseSortedList(new List<String>(mainList),
                          new List<String>(deleteList));
        Console.WriteLine("サイズ: {0}", list.Count);
        Console.WriteLine("最初: {0}", list[0]);

        Console.WriteLine();

        list = UseHashSet(new List<String>(mainList),
                      new List<String>(deleteList));
        Console.WriteLine("サイズ: {0}", list.Count);
        Console.WriteLine("最初: {0}", list[0]);
    }

    static List<String> Original(List<String> mainList,
                                 List<String> deleteList)
    {
        Console.WriteLine("start Original");
        var runStopwatch = new Stopwatch();
        runStopwatch.Start();

        // mainListの中にdeleteListの項目があれば削除する
        // ここの処理を高速化できないかを悩み中です。
        foreach (string deleteStr in deleteList)
        {
            mainList.Remove(deleteStr);
        }

        runStopwatch.Stop();
        Console.WriteLine("run 完了: {0} ms",
                          runStopwatch.ElapsedMilliseconds);
        return mainList;
    }

    static List<String> UseLinkedList(List<String> mainList,
                                 List<String> deleteList)
    {
        Console.WriteLine("start UseLinkedList");
        var runStopwatch = new Stopwatch();
        runStopwatch.Start();

        // LinkedListに変換して処理をする。
        var mainLinkedList = new LinkedList<String>(mainList);
        foreach (string deleteStr in deleteList)
        {
            mainLinkedList.Remove(deleteStr);
        }
        var newList = mainLinkedList.ToList();

        runStopwatch.Stop();
        Console.WriteLine("run 完了: {0} ms",
                          runStopwatch.ElapsedMilliseconds);
        return newList;
    }

    static List<String> CreateListWithHashset(List<String> mainList,
                                     List<String> deleteList)
    {
        Console.WriteLine("start CreateListWithHashset");
        var runStopwatch = new Stopwatch();
        runStopwatch.Start();

        // 削除用のHashSetを作成して、処理をする。
        var deleteSet = new HashSet<String>(deleteList);
        var newList = mainList
            .Where((s) => !deleteSet.Contains(s)).ToList();

        runStopwatch.Stop();
        Console.WriteLine("run 完了: {0} ms",
                          runStopwatch.ElapsedMilliseconds);
        return newList;
    }

    static List<String> UseSortedList(List<String> mainList,
                                 List<String> deleteList)
    {
        Console.WriteLine("start UseSortedList");
        var runStopwatch = new Stopwatch();
        runStopwatch.Start();

        // SortedListに変換して処理をする。
        var mainSortedList = new SortedList<String, String>(
            mainList.ToDictionary(s => s));
        foreach (string deleteStr in deleteList)
        {
            mainSortedList.Remove(deleteStr);
        }
        var newList = mainSortedList.Select(pair => pair.Value)
                                    .ToList();

        runStopwatch.Stop();
        Console.WriteLine("run 完了: {0} ms",
                          runStopwatch.ElapsedMilliseconds);
        return newList;
    }

    static List<String> UseHashSet(List<String> mainList,
                                 List<String> deleteList)
    {
        Console.WriteLine("start UseHashSet");
        var runStopwatch = new Stopwatch();
        runStopwatch.Start();

        // HashSetに変換して処理をする。
        var mainHashSet = new HashSet<String>(mainList);
        foreach (string deleteStr in deleteList)
        {
            mainHashSet.Remove(deleteStr);
        }
        var newList = mainHashSet.ToList();

        runStopwatch.Stop();
        Console.WriteLine("run 完了: {0} ms",
                          runStopwatch.ElapsedMilliseconds);
        return newList;
    }

}

データの並びはランダム化しています。連結リストの場合は削除するデータがどこにあるかによって処理時間が大きく変わるからです。

600万件中50万件だとオリジナルや連結リストが遅すぎるので、6万件中5千件での実行結果です。

60000個中5000個を削除
main 作成完了: 368 ms
delete 作成完了: 26 ms

start Original
run 完了: 4572 ms
サイズ: 55000
最初: 57539

start UseLinkedList
run 完了: 3258 ms
サイズ: 55000
最初: 57539

start CreateListWithHashset
run 完了: 13 ms
サイズ: 55000
最初: 57539

start UseSortedList
run 完了: 2628 ms
サイズ: 55000
最初: 10000

start UseHashSet
run 完了: 16 ms
サイズ: 55000
最初: 57539

UseSortedListの最初の要素は異なります。UseHashSetの場合は重複が維持されないことに注意です。なお、順序づけしておきたい場合はSortedSetを使うという手段もあります。

Comments

[oryou]

本当にありがとうございます。
実際に自分の環境で検証コードを実行させていただきましたが、１時間もかかっていた処理が僅か１秒程しかかからないのですごく感動しました。
HashSetを利用するだけで、こんなにも処理時間が変わってくるとは思ってもいませんでした。
本当に感謝しています。
ありがとうございました。

Answer 2

こんにちは。

コレクションの内部実装を見るとList<T>ってソートしてないので頭から１つ1つ比較するので遅いです。更に連続したメモリを確保するようなのでRemoveも遅そうです。（多量のメモリコピーが発生するため）

mainListの数は最初600万、最後550万ですね。検索で見つかるのに平均して全体の半分と比較したと仮定すると最初平均300万回、最後は275万回の比較を行います。更に平均して287.5万回です。
これを50万回繰り返すので、287.5万回x50万回の比較を行います。

mainListをSortedSet<T>に変更すると、2分探索になりますので、600万個（＜2の23乗）から見つける時に必要な比較回数は23回です。それを50万回繰り返します。

287.5万回/23回なので125,000倍の速度アップを期待できます。
SortedSet<T>は一般に言うリスト構造なのでRemoveは高速ですので、更に速くなる筈。

---

ご提示されたコードは600万個の頭の50万個に削除するものが集中しているから、1削除当たり平均25万回の比較になるため、25万回x50万回の比較になりますね。
ですので、25万回/23回なので1万倍程高速化することが期待できます。1秒かからない筈。

と思ったけど違いますね。常に削除対象が先頭になるので、1削除当たり1回の比較しかしてないはずですね。
となると比較回数は確実に増えます。ご提示のソースの場合、Remove処理がほぼ全てです。リスト構造になることでRemoveは高速になりますから、速度が上がる可能性もあります。やってみないと解らないです。

なお、実データの場合は、こんな極端な偏りがないなら高速化できる筈です。

---

すいません。実際にはやったことないので、上記は理論値です。
計算間違いもあるかも知れません。違ってたらごめんなさい。

Comments

[oryou]

回答ありがとうございます。
今回は他の回答者がHashSetを紹介してくださったので、hashsetを利用して処理をしましたが、SortedSetという方法もあるのですね。
調べたところ、SortedSetはhashsetにソート機能を追加したクラスのようなので、今回のような処理でさらにソートが必要になった場合に利用したいと思います。
プラスアルファで知識が増えたので回答に感謝しています。
ありがとうございました。

Answer 3

Removeするより新しいListを再生成した方が早いような気が..

Comments

[oryou]

回答ありがとうございます。
重複していない要素のみを新規リストに追加していくのも確かにありですね。

Answer 4

どうしてもオンメモリで処理しなければならないのでしょうか？

処理対象のデータがデータベースに格納されているなら、データベースの機能をつかってデータの操作を行った方が良いように思います。

Comments

[oryou]

回答ありがとうございます。
今回は、データベースを利用できない為オンメモリでの処理となりましたが、やはりデータベースで処理する方が高速化につながるのですね。
データベースを利用できる環境で質問することもあると思いますので、またその時はご教示よろしくお願いします。

Answer 5

List<T>は連続領域に要素を順番に配置した配列のような構造となっているため、「１件ずつ削除する」のは非常にコストの高い処理になるのは他の方がおっしゃるとおりと思います。途中の要素を削除した場合、それ以降の要素をひとつずつ前に「詰めなければならない」ので処理時間は詰めなければならない要素の数に比例=(リストのサイズに比例)するのでO(n)ということになります。

よって削除しなければならない要素を一つずつRemoveすると大変遅くなりますが、ListにはRemoveAllというメソッドも用意されています。このメソッドはRemoveを繰り返し呼び出すような実装にはなっていません。以下のリファレンスの備考にあるように計算量はO(n)です。

MSDN: RemoveAll

RemoveAllが内部でRemoveの繰り返しにより実装されているのであれば処理時間はO(n^2)相当になるはずですがO(n)になっているのは、複数の要素を削除する際、削除の度にそれ以降の要素を一つずつずらすようなことをしなくてよい実装になっているからだと思います。(例えば以下のような雰囲気に)

class List<T> {
  public void RemoveAll(Predicate<T> predicate) {
    int curIndex = 0;
    for (int i = 0; Count; i++) {
      T element = this[i];
      if (!predicate(element)) {
        if (curIndex < i) {
          this[curIndex++] = element;
        }
      }
    }
    RemoveRange(curIndex, Count - curIndex);
  }
}

この考えに基づくなら後は「削除すべき要素かどうかを高速に判定する」ということに配慮しHashSetを用いるとよいと思います。(ソートしてバイナリーサーチする方法とHashSetによりサーチする方法を比べれば検索時間はやはりHashSetの方が早いと思います。既にソートされているかどうかや消費メモリー量など条件によっても違うでしょうが...)

以上の考えから、次のように書き換えるとそこそこのスピードになってくれると思います。

// 質問者さんのコード
...
foreach (string deleteStr in deleteList) {
  mainList.Remove(deleteStr);
}

// 変更後のコード
...
HashSet<string> deleteSet = new HashSet<string>(deleteList);
mainList.RemoveAll(element => deleteSet.contains(element));

なお、削除すべきリストを作っている部分を最初からHashSetとして作ればスピードとメモリーの消費量は若干よくなると思います。

Comments

[KSwordOfHaste]

あ、書き忘れましたが上記はオリジナルのリストの順番をかえない方法です。つまり質問者さんのオリジナルのアルゴリズムと結果が同一になるという前提です。

[oryou]

回答ありがとうございます。
なぜ、Listでの削除処理が遅いのかがよくわかりました。
リストの要素を削除する度に、後ろの要素を前に持ってくる処理が走るのでそこで時間がかかっていたのですね。
基本的な処理の動きを教えて頂きありがとうございます。
Listを使うメリット、デメリットを考える要素が１つ増えたので感謝しています。
ありがとうございました。

[KSwordOfHaste]

自分の回答意図はRemoveをm回呼び出すよりRemoveAllを1回呼び出す方がぐっと早くなる(RemoveAllはRemoveを単にm回呼び出すだけの便利機能ではなくちゃんと性能上の意味がある)ということでした。大した機能差がないと思えるようなAPIにも自分で論理を組むよりはずっとよいことがあるという一例として参考にしていただければと思います。

Answer 6

600万件をデータベースも使わずにソートするとか
ぞっとしない話ですが、もし可能なら…

1. (元データ + 削除データ + 削除データ) を作成
2. 上記をソート
3. 2つ以上同じものがあったら削除

イメージ的にはこんな感じ

src_file='hoge.txt' # 元データ
del_file='piyo.txt' # 削除対象
dst_file='fuga.txt' # 出力ファイル

cat $src_file $del_file $del_file | \
sort | \
uniq -c | \
awk '{if ($1 == 1) print $2}' > $dst_file

Comments

[oryou]

回答ありがとうございます。
シェルコマンドでの処理方法を提示してくださってありがとうございます。
やはりプログラミング言語よりもシェルコマンドの方が処理をイメージしやすいですね。
ありがとうございました。

Answer 7

前提条件として
0. メモリが十分に備わっている
0. mainListの要素の並び順が意味を持っている
0. 削除キーが重複してない｡

とします｡

さて､提示されたサンプルコードは削除するために､約600万件ものデータを総なめする必要があるため余り効率が良くないです｡
また､削除する際のコストも結構かかるので､一度辞書にしてしまって再度リストにすれば良いのではないでしょうか?

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp3
{
	class Program
	{
		static void Main(string[] args)
		{
			// 600万件分のリストを作成
			List<string> mainList = new List<string>();
			for (int i = 0; i < 6000000; i++)
			{
				mainList.Add(i.ToString());
			}

			// 50万件分のリストを作成
			List<string> deleteList = new List<string>();
			for (int i = 0; i < 500000; i++)
			{
				deleteList.Add(i.ToString());
			}

			//mainListを辞書化する(元の位置を覚えておく為インデックスを持っておく)
			var mainDictionary = mainList.Select((s, i) => (value:s, index:i)).ToDictionary(t => t.value, t => t.index);

			//辞書に対して削除を行う｡
			foreach (var deleteStr in deleteList)
			{
				mainDictionary.Remove(deleteStr);
			}
			
			//mainDictionaryからListを再作成(インデックスを元に元の並びを復元する)
			mainList = mainDictionary.OrderBy(p => p.Value).Select(p => p.Key).ToList();

			

		}
	}
}

Comments

[oryou]

回答ありがとうございます。
今回はHashsetを利用することで高速化を図ることができました。
Dictionaryを使う方法もあるのですね。
調べると「hashsetはキーだけを扱う一種のDictionaryのようなコレクションと見れる」と書かれていたので、そういう処理の方法をDictionaryで実現しているのかなと思いました。

Answer 8

main,deleteデータをソートしておく。（順に並んでいれば何もしない）

1.mainを読む
2.deleteを読む
3.main<deleteならmain出力。main読み込み。main終わりならプログラム終了。
main>deleteならdelete読み込み。delete終わりなら残りのmainをすべて出力してプログラム終了。
main=deleteならmain読み込み。main終わりならプログラム終了。
4.3.の繰り返し

これでどうですか？
マッチングというやつです。
メモリーに貯めることもせず、データを比較して新しいマスターを作っていくものです。

Comments

[oryou]

回答ありがとうございます。
今回はHashsetを利用することで、高速化をはかることができました。
マッチングという方法も試してみたいと思います。
ありがとうございました。

Answer 9

50万件のリストを作成せず、消していけばいけないのですか？