配列存在チェックのために二分探索メソッドを実装する（速度比較も）【C#】
例によってAtcoderを解いてて詰まったから作りました。
(2022-08-27 ABC266-F)
配列に該当項目が存在するか？のためにListから.Contains(i)をしているとTLEします。
効率よい探索が必要。
Pythonならmap機能でinで探すだけで高速に見つけてくれるが、C#には無いので自作します。
探索方法検討
自作の前に...
そもそも、c#には色々便利なリストがあります。これらを利用できないか。
ということで、以下を比較検討しました。
１．Generic.SortedSetクラス
２．System.Collections.SortedListクラス
３．Generic.SortedList＜TKey,TValue＞ クラス
４．IOrderdEnumerableクラス
５．自作二分探索クラス
map.cs
public class Map
{
private long[] _sortedAry;
public Map(IEnumerable<long> t)
{
_sortedAry = t.OrderBy(p => p).ToArray();
}
public Map(IEnumerable<int> t)
{
_sortedAry = t.Select(p => (long)p).OrderBy(p => p).ToArray();
}
public Map(IOrderedEnumerable<long> t)
{
_sortedAry = t.ToArray();
}
public int this[long i] //1次元
{
get { return (_sortedAry.Length == 0) ? -1 : GetIndex(i, 0, _sortedAry.Length - 1); }
}
private int GetIndex(long i, int st = 0, int ed = -1)
{
if (ed - st <= 0)//最後1回
return (_sortedAry[st] == i) ? st : -1;
int half = st + (ed - st) / 2;
if (_sortedAry[half] > i)
return GetIndex(i, st, half);
else if (_sortedAry[half] < i)
return GetIndex(i, half + 1, ed);
else
return half;
}
}
※Contains(i)じゃなくて[i]で検索します。ついでにインデックスも帰ってくる。
実際にテストしてみる
テストに使用したコード
test.cs
public test()
{
const int SIZE = 200000;
const int SEARCH_COUNT = 10000;
var sw = new System.Diagnostics.Stopwatch();
Console.WriteLine("START");
sw.Start();
var q = new List<int>();
Random r1 = new System.Random();
for (int i = 0; i < SIZE; i++)
q.Add(r1.Next(0, SIZE * 2));
q = q.Distinct().ToList();
var qDic = q.ToDictionary(x => x, y => 0);
var sample_list = new int[SEARCH_COUNT];
for (int i = 0; i < SEARCH_COUNT; i++)
sample_list[i] = r1.Next(0, SIZE * 2);
sw.Stop();
Console.WriteLine(sw.Elapsed + " - Make Rand");
sw.Restart();
var pret = new bool[SEARCH_COUNT];
for (int c = 0; c < SEARCH_COUNT; c++)
pret[c] = q.Contains(sample_list[c]);
sw.Stop();
Console.WriteLine(sw.Elapsed + " - Pure Array Contains");
sw.Restart();
var y2 = q.OrderBy(p => p).ToArray();
sw.Stop();
Console.WriteLine(sw.Elapsed + " - Array(Sorted)");
sw.Restart();
var y2ret = new bool[SEARCH_COUNT];
for (int c = 0; c < SEARCH_COUNT; c++)
y2ret[c] = y2.Contains(sample_list[c]);
sw.Stop();
Console.WriteLine(sw.Elapsed + " - Array(Sorted) Contains");
sw.Restart();
var y1 = q.OrderBy(p => p);
sw.Stop();
Console.WriteLine(sw.Elapsed + " - IOrderdEnumerable");
sw.Restart();
var yret = new bool[SEARCH_COUNT];
for (int c = 0; c < SEARCH_COUNT; c++)
yret[c] = y1.Contains(sample_list[c]);
sw.Stop();
Console.WriteLine(sw.Elapsed + " - IOrderdEnumerable Contains");
sw.Restart();
SortedList x1 = new SortedList(qDic);
//SortedList x1 = new SortedList();
//for (int i = 0; i < q.Count(); i++)
// x1.Add(q[i], 0);
sw.Stop();
Console.WriteLine(sw.Elapsed + " - SortedList");
sw.Restart();
var xret = new bool[SEARCH_COUNT];
for (int c = 0; c < SEARCH_COUNT; c++)
xret[c] = x1.Contains(sample_list[c]);
sw.Stop();
Console.WriteLine(sw.Elapsed + " - SortedList Contains");
sw.Restart();
var x2 = new System.Collections.Generic.SortedList<int, int>(qDic);
//var x2 = new System.Collections.Generic.SortedList<int, int>();
//for (int i = 0; i < q.Count(); i++)
// x2.Add(q[i], 0);
sw.Stop();
Console.WriteLine(sw.Elapsed + " - Generic.SortedList");
sw.Restart();
var x2ret = new bool[SEARCH_COUNT];
for (int c = 0; c < SEARCH_COUNT; c++)
x2ret[c] = x2.ContainsKey(sample_list[c]);
sw.Stop();
Console.WriteLine(sw.Elapsed + " - Generic.SortedList Contains");
sw.Restart();
var x3 = new SortedSet<int>(q);
//var x3 = new SortedSet<int>();
//for (int i = 0; i < q.Count(); i++)
// x3.Add(q[i]);
sw.Stop();
Console.WriteLine(sw.Elapsed + " - Generic.SortedSet");
sw.Restart();
var x3ret = new bool[SEARCH_COUNT];
for (int c = 0; c < SEARCH_COUNT; c++)
x3ret[c] = x3.Contains(sample_list[c]);
sw.Stop();
Console.WriteLine(sw.Elapsed + " - Generic.SortedSet Contains");
sw.Restart();
var z1 = new Map(q);
sw.Stop();
Console.WriteLine(sw.Elapsed + " - Map[Custom Class]");
sw.Restart();
var zret = new bool[SEARCH_COUNT];
for (int c = 0; c < SEARCH_COUNT; c++)
zret[c] = z1[sample_list[c]] != -1;
sw.Stop();
Console.WriteLine(sw.Elapsed + " - Map[Custom Class] Contains");
}
比較のために未ソート、ソートしてからToArray()も入れています。
結果
縦軸は検索回数(SEARCH_COUNT)=nとして表記
配列SIZE=1000のとき
配列作成にかかる時間
| ＼ | Pure Array | Array(Sorted) | IOrderdEnumerable | SortedList | Generic.SortedList | Generic.SortedSet | 二分探索カスタムクラス |
|---|---|---|---|---|---|---|---|
| - | - | 0.0025350 | NaN | 0.0012768 | 0.0005517 | 0.0009834 | 0.0000847 |
検索回数
| ＼ | Pure Array | Array(Sorted) | IOrderdEnumerable | SortedList | Generic.SortedList | Generic.SortedSet | 二分探索カスタムクラス |
|---|---|---|---|---|---|---|---|
| n=100 | 0.0000582 | 0.0000846 | 0.0095038 | 0.0000370 | 0.0000895 | 0.0001719 | 0.0001320 |
| n=10000 | 0.0010369 | 0.0011975 | 0.6199364 | 0.0016111 | 0.0007442 | 0.0007591 | 0.0018011 |
| n=10000000 | 0.9748624 | 1.0208422 | 測定不能 | 1.2198101 | 0.5478009 | 0.5386517 | 1.6215458 |
配列SIZE=200000のとき
配列作成にかかる時間
| ＼ | Pure Array | Array(Sorted) | IOrderdEnumerable | SortedList | Generic.SortedList | Generic.SortedSet | 二分探索カスタムクラス |
|---|---|---|---|---|---|---|---|
| - | - | 0.0261035 | NaN | 0.0524448 | 0.0102246 | 0.0207644 | 0.0337261 |
検索回数
| ＼ | Pure Array | Array(Sorted) | IOrderdEnumerable | SortedList | Generic.SortedList | Generic.SortedSet | 二分探索カスタムクラス |
|---|---|---|---|---|---|---|---|
| n=10 | 0.0002383 | 0.0005216 | 0.2703895 | 0.0000534 | 0.0002125 | 0.0000051 | 0.0002183 |
| n=100 | 0.0016324 | 0.0296529 | 2.5551150 | 0.0001112 | 0.0001635 | 0.0000370 | 0.0003051 |
| n=10000 | 0.1601330 | 0.1715653 | 測定不能 | 0.0032967 | 0.0013078 | 0.0028416 | 0.0035492 |
配列SIZE=10000000のとき
配列作成にかかる時間
| ＼ | Pure Array | Array(Sorted) | IOrderdEnumerable | SortedList | Generic.SortedList | Generic.SortedSet | 二分探索カスタムクラス |
|---|---|---|---|---|---|---|---|
| - | - | 2.5203717 | NaN | 6.2385000 | 0.6050261 | 1.4195260 | 2.5881175 |
検索回数
| ＼ | Pure Array | Array(Sorted) | IOrderdEnumerable | SortedList | Generic.SortedList | Generic.SortedSet | 二分探索カスタムクラス |
|---|---|---|---|---|---|---|---|
| n=100 | 0.1959737 | 0.1902311 | 測定不能 | 0.0002974 | 0.0003365 | 0.0004881 | 0.0004014 |
結論
-
基本Generic.SortedSetが最強
-
ただし、データ件数によってはGeneric.SortedListが配列の作成時間的に有利になることも(元データがDictionary型だとSortedList有利)
-
Arrayをソートしておいても特に結果が変わるわけではない
-
ソートしてもIOrderdEnumerableのまま使うとかえって遅くなる
-
SortedListはごく少ないリストの時、最速になる可能性がある
-
二分探索カスタムクラスは勝てない...
SortedList、SortedSetは配列の再作成コストが重いです。初期値の後でデータを追加/削除することが多い(10^6回以上ぐらい)ときは、
その場合は二分探索カスタムクラスがワンチャンあります。
（2*10^5回の追加でList＜int＞は0.0014sに対し、SortedList：2.21s、Generic.SortedList：0.68s、SortedSet：0.057s、Generic.SortedSet：0.036s）
SortedList、Generic.SortedList、SortedSet、Generic.SortedSetは、重複キーが許可されません。
今回は必要としませんでしたが、存在チェック後にそれに紐づくデータを取得したい場合は、DictionaryやGeneric.SortedListが俄然便利です。
おまけ
要素が２つある形の二分探索クラスも作りました。
グリッド上の(x,y)を探したいときなどに便利？(Dictionaryだとxがキー重複してしまうため)
Map2D.cs
public class Map
{
//2次元バージョン------------------------------------------------------------------------------------------------
private long[][] _sortedAry2D;
public Map(long[][] tary)
{
var t = new List<long[]>();
t.AddRange(tary);
_sortedAry2D = t.OrderBy(p => p[0]).ThenBy(p => p[1]).ToArray();
}
public Map(List<long[]> t)
{
_sortedAry2D = t.OrderBy(p => p[0]).ThenBy(p => p[1]).ToArray();
}
public Map(List<int[]> t)
{
_sortedAry2D = t.Select(p => { return Array.ConvertAll(p, e => (long)Convert.ChangeType(e, typeof(long))); }).OrderBy(p => p[0]).ThenBy(p => p[1]).ToArray();
}
//二分探索でi,jが存在するか確認 存在する場合はindex,ない場合は-1を返す
public int this[long i, long j] //2次元バージョン
{
get { return (_sortedAry2D.GetLength(0) == 0) ? -1 : GetIndex2D(i, j, 0, _sortedAry2D.GetLength(0) - 1); }
}
private int GetIndex2D(long i, long j, int st = 0, int ed = -1)
{
if (ed - st <= 0)//最後1回
return (_sortedAry2D[st][0] == i && _sortedAry2D[st][1] == j) ? st : -1;
int half = st + (ed - st) / 2;
if (_sortedAry2D[half][0] > i)
return GetIndex2D(i, j, st, half);
else if (_sortedAry2D[half][0] < i)
return GetIndex2D(i, j, half + 1, ed);
else
{
if (_sortedAry2D[half][1] > j)
return GetIndex2D(i, j, st, half);
else if (_sortedAry2D[half][1] < j)
return GetIndex2D(i, j, half + 1, ed);
else
return st;
}
}
}