速度のために List クラスに Last 拡張メソッドを定義しようとしたけど要らなかった
やろうとしたこと
- List<T> の最後の要素を取得するメソッドが欲しい
- Enumerable.Last メソッドがある
- だけど、シーケンスを辿るので O(N) で遅いのでは?
先に結論から言うと、IList<T> インターフェース を実装しているなら、 Enumerable.Last は O(N) ではなく O(1) になります。後ほど、Enumerable.Last の実装をみます。
List.MyLast 拡張メソッドを定義して、速度を計測してみた
using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; public static class Extension { public static T MyLast<T>(this List<T> list) { return list[list.Count - 1]; } } class Program { static void TestLast(int n, int m) { var xs = Enumerable.Range(0, m).ToList(); var sw = new Stopwatch(); sw.Start(); for (int i = 0; i < n; i++) { xs.Last(); } sw.Stop(); Console.WriteLine("Last : n:{0} time:{1}", n, sw.ElapsedMilliseconds); } static void TestMyLast(int n, int m) { var xs = Enumerable.Range(0, m).ToList(); var sw = new Stopwatch(); sw.Start(); for (int i = 0; i < n; i++) { xs.MyLast(); } sw.Stop(); Console.WriteLine("MyLast: n:{0} time:{1}", n, sw.ElapsedMilliseconds); } static void Main() { int size = 1000000; foreach (var x in new[] { 1000000, 10000000 }) { TestLast(x, size); TestMyLast(x, size); } } }
実行結果です。
Last : n:1000000 time:13 MyLast: n:1000000 time:5 Last : n:10000000 time:117 MyLast: n:10000000 time:45
2 倍程度しか差がありません。
Enumerable.Last の実装をみてみる
Reference Source の Enumerable.Last の実装 をみてみると、as 演算子で IList<T> インターフェース を実装しているか確認しています。もし、IList<T> インターフェースを実装しているなら、インデックスによるアクセスで最後の要素を取得しています。
まとめ
- IList<T> インターフェース を実装しているなら、Enumerable.Last は O(1) で速い