読者です 読者をやめる 読者になる 読者になる

速度のために 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> インターフェースを実装しているなら、インデックスによるアクセスで最後の要素を取得しています。

まとめ