LINQ で最小値・最大値を柔軟に求める
1. LINQ で最小値・最大値を求める
1.1 普通のやり方
LINQ で最小値を求めるには次のようにします。
var array = new[] { 10, 2, 3, 1, 8 };
var min = array.Min();
Console.WriteLine(min);
1
要素が IComparable を実装している集合はこのように簡単に最小値を求めることができます。
文字列でも可能です。
var array = new[] { "かきくけこ", "あいうえお", "さしすせそ" };
var min = array.Min();
Console.WriteLine(min);
あいうえお
Max() も全く同じ使い方ができ、こちらは最大値を求めます。
1.2 不満
このように簡単に最小値・最大値を求めることができるのですが、時々不満があります。
Min() には引数を与えることができますが、この引数が selector という名前にも関わらず結果まで書き換えてしまうことです。
例えば次のコード
var array = new[] { 3, -5, -1, 10, -2 };
var min = array.Min(a => Math.Abs(a));
Console.WriteLine(min);
1
絶対値が最小となる数を求めて欲しいのですが、得られる値は -1 でなく 1 です。
変換するなら selector ではなく converter という名前にして欲しい。
いや変換していいなら次のようにすればいいだけなのでそもそも必要ありません。
var array = new[] { 3, -5, -1, 10, -2 };
var min = array.Select(a => Math.Abs(a)).Min();
Console.WriteLine(min);
私が欲しいのは元の値なのです。
2. 作ってみる
2-1. ソース
以下のソースは古いものです。その次のソースを使ってください。
public static class Linq
{
public static IEnumerable<T> MinBy<T, U>(this IEnumerable<T> source, Func<T, U> selector)
{
var lookup = source.ToLookup(selector);
return lookup[lookup.Min(a => a.Key)];
}
public static IEnumerable<T> MaxBy<T, U>(this IEnumerable<T> source, Func<T, U> selector)
{
var lookup = source.ToLookup(selector);
return lookup[lookup.Max(a => a.Key)];
}
}
コメントで指摘を受け、OrderBy, OrderByDescending で Min(), Max() の代わりになると教えていただきました。
その時に思ったのが、「集合全体のソートは計算量 O(log N) で、最小値・最大値を求めるのは O(N) であろうから上記ソースの方が速度では勝るはず」ということでした。
ところが実際に計測してみると、条件にもよりますがほとんどの場合でソートの方が速いという結果になりました。
おそらく Lookup の作成に時間がかかっているのだろうと検討をつけ、以下のように再実装したところ、ソートに圧勝できるようになりました。
勉強になりました。
public static IEnumerable<T> MinBy<T, U>(this IEnumerable<T> source, Func<T, U> selector)
{
return SelectBy(source, selector, (a, b) => Comparer<U>.Default.Compare(a, b) < 0);
}
public static IEnumerable<T> MaxBy<T, U>(this IEnumerable<T> source, Func<T, U> selector)
{
return SelectBy(source, selector, (a, b) => Comparer<U>.Default.Compare(a, b) > 0);
}
private static IEnumerable<T> SelectBy<T, U>(IEnumerable<T> source, Func<T, U> selector, Func<U, U, bool> comparer)
{
var list = new LinkedList<T>();
U prevKey = default(U);
foreach (var item in source)
{
var key = selector(item);
if (list.Count == 0 || comparer(key, prevKey))
{
list.Clear();
list.AddLast(item);
prevKey = key;
}
else if (Comparer<U>.Default.Compare(key, prevKey) == 0)
{
list.AddLast(item);
}
}
return list;
}
2-2. 相違点
Min() と MinBy()、Max() と MaxBy() の仕様は二点違います。
引数が必須になったことと、戻り値が IEnumerable<T> になったことです。
var array = new[] { 3, -5, -1, 10, -2 };
var min = array.MinBy(a => Math.Abs(a));
Console.WriteLine(min.First());
-1
したがって、戻り値が一つだけ欲しい時には上記のように First() をつけなければなりません。
一見不便になったようにも見えますが、たとえば次の結果を見てください。
var array = new[] { 3, -5, -1, 10, -2, 1 };
var min = array.MinBy(a => Math.Abs(a));
foreach (var i in min)
{
Console.WriteLine(i);
}
-1
1
標準の Min() の場合は値を書き換えてしまうので複数返す必要はありません。
どちらも 1 になるので複数返しても 1 が二つ並ぶだけです。
しかし、値を書き換えないなら複数返すべきなのです。
2-3. 色々な使い方
2-3-1 文字列の最後の文字が最小のものを出力
var array = new[] { "Hello", "World!" };
var min = array.MinBy(a => a.LastOrDefault());
foreach (var i in min)
{
Console.WriteLine(i);
}
World!
2-3-2 プロパティが最小となるものを出力
var array = new[]
{
new { Name = "佐藤", Age = 30 },
new { Name = "鈴木", Age = 15 },
new { Name = "スズキの砂糖漬け", Age = 150 }
};
var min = array.MinBy(a => a.Age);
foreach (var i in min)
{
Console.WriteLine(i);
}
{ Name = "鈴木", Age = 15 }
2-3-3 文字列の中の数字が最小となるものを出力
var array = new[]
{
"Sato30",
"Suzuki15",
"Duke150"
};
var min = array.MinBy(a => int.Parse(Regex.Match(a, @"\d+").Value));
foreach (var i in min)
{
Console.WriteLine(i);
}
Suzuki15
執筆日: 2018/03/22
Discussion