FC2ブログ
ヽ|∵|ゝ(Fantom) の 開発blog? ホーム » C# »【C#】ソート済み List を動的に作る拡張メソッド

【C#】ソート済み List を動的に作る拡張メソッド  


 今回は二分探索によるリスト処理の高速化できる拡張メソッドを作ってみよう。

 普段、何気なく List に値を Add したり、Remove したりしてはいないだろうか?
 また検索というと、標準で使える List.ContainsList.FindList.FindIndex 等や、Linq の FistOrDefault などを使う機会も多いだろう。
 しかし、これらは逐次探索(O(n))のため、要素数に比例して、検索速度は遅くなる。特に1000を超えるデータを頻繁に扱うとなると、かなり実行速度に影響が出る。

 そのような場合、ケースにもよるのだが、List に追加する要素の順番は必要ないとき、または ID のように昇順で並んでいる方が便利なとき等、常に List をソート済みにしておくと、二分探索(BinaraySearch)が使えるようになる。
 二分探索のオーダーは O(log n) のため、要素が多くなっても、検索速度はそれほど落ちない。

 もし、ただの1回のみのソートで良いのなら、全て要素を追加した後に、単純に List.Sort や Linq の OrderBy を使う方が良いだろう。しかし、頻繁にデータを追加したり、削除したりする場合は、動的にソート済みリストを作っていく拡張メソッドを作っておくと便利だ。



●動的にソート済みリストに要素を追加、削除していく拡張メソッド
using System.Collections.Generic;

public static class Extentions //※名前は任意
{
/// <summary>
/// 昇順で要素を追加する
/// 2021/02/02 Fantom
/// http://fantom1x.blog130.fc2.com/blog-entry-392.html
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list">対象リスト</param>
/// <param name="value">追加する要素</param>
/// <returns>true = 新規追加 / false = 既存あり(重複で追加)</returns>
public static bool AddSorted<T>(this List<T> list, T value)
{
int idx = list.BinarySearch(value);
if (idx < 0)
{
list.Insert(~idx, value);
return true;
}
list.Insert(idx, value);
return false;
}

/// <summary>
/// 昇順で要素をユニーク追加する
/// 2021/02/02 Fantom
/// http://fantom1x.blog130.fc2.com/blog-entry-392.html
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list">対象リスト</param>
/// <param name="value">追加する要素</param>
/// <returns>true = 新規追加 / false = 既存あり(追加しない)</returns>
public static bool AddSortedUniq<T>(this List<T> list, T value)
{
int idx = list.BinarySearch(value);
if (idx < 0)
{
list.Insert(~idx, value);
return true;
}
return false;
}

/// <summary>
/// 昇順のリストから要素を削除
/// 2021/02/02 Fantom
/// http://fantom1x.blog130.fc2.com/blog-entry-392.html
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list">対象リスト</param>
/// <param name="value">削除する要素</param>
/// <returns>true = 削除した / false = 既存なし(削除失敗)</returns>
public static bool RemoveSorted<T>(this List<T> list, T value)
{
int idx = list.BinarySearch(value);
if (idx >= 0)
{
list.RemoveAt(idx);
return true;
}
return false;
}
}

●メインコード例
using System;
using System.Collections.Generic;

string[] array =
{
"Apple", "Banana", "Candy", "Donuts", "Egg", "Fish", "Candy", "Egg"
};

array.Shuffle(); //※Shuffle は以前の記事を参照
Console.WriteLine(array.Dump()); //※Dump は以前の記事を参照

var list1 = new List(array.Length);
var list2 = new List(array.Length);
foreach (var item in array)
{
list1.AddSorted(item); //昇順で追加
list2.AddSortedUniq(item); //昇順でユニーク追加
}

Console.WriteLine("list1 : " + list1.Dump()); //※Dump は以前の記事を参照
Console.WriteLine("list2 : " + list2.Dump()); //※Dump は以前の記事を参照

//昇順リストから削除
list1.RemoveSorted("Candy");
list1.RemoveSorted("Egg");
Console.WriteLine("list1 (Removed) : " + list1.Dump()); //※Dump は以前の記事を参照
Console.WriteLine("list2 (Removed) : " + list2.Dump()); //※Dump は以前の記事を参照

//二分探索
int idx1 = list1.BinarySearch("Candy");
Console.WriteLine($"idx1 = {idx1}");
int idx2 = list1.BinarySearch("Egg");
Console.WriteLine($"idx2 = {idx2}");

[Banana, Egg, Apple, Candy, Egg, Donuts, Fish, Candy]
list1 : [Apple, Banana, Candy, Candy, Donuts, Egg, Egg, Fish]
list2 : [Apple, Banana, Candy, Donuts, Egg, Fish]
list1 (Removed) : [Apple, Banana, Candy, Donuts, Egg, Fish]
list2 (Removed) : [Apple, Banana, Candy, Donuts, Egg, Fish]
idx1 = 2
idx2 = 4

 DumpShuffle の拡張メソッドは以前に作ったものだ。

Dump の拡張メソッド
Shuffle の拡張メソッド

 どのように追加されているかに注目して欲しい。常に昇順に並び替えたリストと同義となるため、追加するたびソート(List.Sort)する必要はもちろん無い。
 取得するときは List.BinarySearch が使えるので、ちょっとやそっと要素数が増えた所で、検索速度が落ちることはない(実際に 100000 [10万] くらいの要素数があっても、検索速度は速い)。

 また、この例ではコンストラクタで new List(int capacity) を使っているが、これは予め格納できるサイズを確保しておくコンストラクタだ。色々なコードを見ていても、ほとんどが引数なし new List() で使われているが、実はこれはとても重要だ。と言うのは、List の様な動的に増やせるコレクションというのは、現在格納できるサイズを超えると、メモリの再割当てをし(サイズ拡大)、コピーする動作を頻繁に繰り返すからだ。要素が多くなると、負荷がかかるのは言うまでもない。はじめからわかっている、または想定できるなら、capacity を指定した方が、要素を追加するとき、無駄な処理が走らない(Dictionary なども同じ)。

 以下は Unity 上で、毎フレーム逐次検索(List.ContainsList.Find)していた箇所を、二分探索探索に置き換えただけのもので、パフォーマンスを比較してみたものだ。
 青い部分はスクリプトの負荷で、激減していることが分かる。実際にほんの数行置き換えただけなのだが、圧倒的なパフォーマンスを出すことができることさえある(この時は約5倍以上になった)。



 ここでは、List.BinarySearch しか使ってないが、以前に紹介した LowerBounds, UpperBounds も併用して使うと良いだろう。

【C#】 LowerBound, UpperBound (二分探索)

 二分探索は上手く使えば、かなりのパフォーマンス改善になる場合があることも少なくない。開発現場では簡潔だからか Linq が使われることが多い気がするが、実はとても遅く、GCを発生させ易いので、利用には注意が必要だ(要は使い処である)。

Unity のパフォーマンスに関する推奨事項 - コストのかかる操作を避ける
LINQとfor, ListとArray(配列)での実行速度を比較してみる
【Unity】CPUプロファイラでパフォーマンスを改善する - GCの発生要因を減らす






(関連記事)
【C#】配列やListなどの中身(要素)を見る拡張メソッド Dump
【Unity】【C#】配列・リストのシャッフル
【C#】二分探索の実装(範囲インデクス指定実装)
【C#】 LowerBound, UpperBound (二分探索)
【Ruby】二分探索, lower_bound, upper_bound
【Unity】【C#】LINQとfor, ListとArray(配列)での実行速度を比較してみる
【C#】連想配列(Dictionary)を値 or キーでソート
【C#】2次元配列(ジャグ配列・多次元配列)のソート
【C#】多次元配列とジャグ配列(2次元配列)のサイズ(長さ)、相互変換など


関連記事
スポンサーサイト



category: C#

thread: プログラミング

janre: コンピュータ

tag: C#ライブラリ  配列操作  二分探索 
tb: 0   cm: --


トラックバック

トラックバックURL
→http://fantom1x.blog130.fc2.com/tb.php/392-43f31950
この記事にトラックバックする(FC2ブログユーザー)

プロフィール

Social

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop