atcoder.jp

この問題を解いているときに気がついたこと。

LinkedList<>.Last()
LinkedList<>.Last

は速度が全く違います。

リスト内の要素が多いほどLast()の方が遅いです。

理屈は簡単で、以下Last()のソースから、

        public static TSource Last<TSource>(this IEnumerable<TSource> source) {
            if (source == null) throw Error.ArgumentNull("source");
            IList<TSource> list = source as IList<TSource>;
            if (list != null) {
                int count = list.Count;
                if (count > 0) return list[count - 1];
            }
            else {
                using (IEnumerator<TSource> e = source.GetEnumerator()) {
                    if (e.MoveNext()) {
                        TSource result;
                        do {
                            result = e.Current;
                        } while (e.MoveNext());
                        return result;
                    }
                }
            }
            throw Error.NoElements();
        }

LinkedList()はIListインターフェースを実装していないため、LinkedList内を頭から順に辿っていくことになります。これは$ O(N) $時間なので、要素数が増えるとどんどん重たくなります。

逆にLastのプロパティ版は以下の通り一瞬です。

        public LinkedListNode<T> Last {
            get { return head == null? null: head.prev;}
        }

速度比較してみました。プログラムは以下の通りです。

    class Program
    {
        static void Main(string[] args)
        {
            var e = new LinkedListSpeedTest();
            e.exec();
        }
    }


    public class LinkedListSpeedTest
    {
        public void exec()
        {
            int LoopCount = 10000;

            double Elapsed_Prop = 0.0;
            double Elapsed_Method = 0.0;
            int TestLoop = 10;
            for (int i = 0; i < TestLoop; ++i)
            {
                double elapsed = execProp(LoopCount);
                Console.WriteLine($"{i}: Property {elapsed}ms");
                Elapsed_Prop += elapsed;
            }
            Console.WriteLine($"Average Property {Elapsed_Prop / (double)TestLoop}ms");

            for (int i = 0; i < TestLoop; ++i)
            {
                double elapsed = execMethod(LoopCount);
                Console.WriteLine($"{i} : Method {elapsed}ms");
                Elapsed_Method += elapsed;
            }
            Console.WriteLine($"Average Method   {Elapsed_Method / (double)TestLoop}ms");
        }
        /// <summary>
        /// Lastプロパティでの速度調査
        /// </summary>
        /// <param name="LoopCount"></param>
        /// <returns></returns>
        public double execProp(int LoopCount)
        {
            var sw = new Stopwatch();
            sw.Start();
            var LL = new LinkedList<int>();
            LL.AddLast(0);
            for(int i = 1; i < LoopCount; ++i)
            {
                if(LL.Last.Value % 2 == 0)
                //以下特に意味がある操作ではない...
                {
                    LL.AddLast(i);
                }
                else
                {
                    LL.AddFirst(i);
                }
            }
            sw.Stop();
            return sw.ElapsedMilliseconds;
        }
        /// <summary>
        /// Last()での速度調査
        /// </summary>
        /// <param name="LoopCount"></param>
        /// <returns></returns>
        public double execMethod(int LoopCount)
        {
            var sw = new Stopwatch();
            sw.Start();

            var LL = new LinkedList<int>();
            LL.AddLast(0);
            for (int i = 1; i < LoopCount; ++i)
            {
                if (LL.Last() % 2 == 0)
                //以下特に意味がある操作ではない...
                {
                    LL.AddLast(i);
                }
                else
                {
                    LL.AddFirst(i);
                }
            }
            sw.Stop();
            return sw.ElapsedMilliseconds;
        }
    }

計測時間は以下の通り

0: Property 1ms
1: Property 0ms
2: Property 0ms
3: Property 0ms
4: Property 0ms
5: Property 0ms
6: Property 0ms
7: Property 0ms
8: Property 1ms
9: Property 0ms
Average Property 0.2ms
0 : Method 733ms
1 : Method 669ms
2 : Method 653ms
3 : Method 573ms
4 : Method 528ms
5 : Method 552ms
6 : Method 566ms
7 : Method 538ms
8 : Method 497ms
9 : Method 593ms
Average Method   590.2ms

リストの要素数が100個程度ではどちらも一瞬で終わり差が出ませんでしたが、要素数1000個あたりから数msほど微妙に差がでました。

ちなみに、First(), First(プロパティ)は、どちらもすぐに終わります。First()内部でIListを実装しているかで挙動が変わるのですが、先頭要素を返すだけなので、IListを実装してなくても探索がいらないからですね。

似たような見た目ですが、実装方法が全く違うので、間違うと思わぬ時間を食って、私のように競プロでTLEを食らう羽目になります。
気をつけましょう（泣）

参考

速度のために List クラスに Last 拡張メソッドを定義しようとしたけど要らなかった - C#練習日記

BenchmarkDotNet

記事を書いた後に知ったのですが、C#でベンチマーク測定ができるパッケージがあるようです。

github.com

いろいろベンチマークオプションがあるので、うまく使えたか正確性が怪しいんですが、やってみたらはっきり差が出ました。結果としてLastプロパティのほうが速いのは変わらないはず。

umem0chiの日記

LinkedListのLast(), Lastプロパティの速度比較について

参考

BenchmarkDotNet