12

（この質問は、ここで始まった議論から生じます）

usingでtrue値を探すタイミングと手巻きループのタイミングを比較していました。List<bool>List.Contains()

他の人が報告した結果とは異なる結果が見られます。いくつかのシステムで試してみましたが、試したすべてのシステムでループが 2 倍から 3.5 倍速くなったようです。これらのシステムは、XP と .Net 4 を実行する 5 年前のラップトップから、Windows 8 と .Net 4.5 を実行する最近の PC までさまざまです。

他の人々は、異なる結果を報告しています。つまりList.Contains()、ループとほぼ同じか、わずかに速い速度です。

これが私のテストコードです。

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    internal class Program
    {
        private static void Main()
        {
            int size = 10000000;
            int count = 10;
            List<bool> data = new List<bool>(size);

            for (int i = 0; i < size; ++i)
                data.Add(false);

            var sw = new Stopwatch();

            for (int trial = 0; trial < 5; ++trial)
            {
                sw.Restart();

                for (int i = 0; i < count; ++i)
                    TestViaLoop(data);

                sw.Stop();
                Console.WriteLine(sw.ElapsedMilliseconds + " TestViaLoop()");
                sw.Restart();

                for (int i = 0; i < count; ++i)
                    TestViaListContains(data);

                sw.Stop();
                Console.WriteLine(sw.ElapsedMilliseconds + " TestViaListContains()");
                Console.WriteLine();
            }
        }

        static bool TestViaLoop(List<bool> data)
        {
            for (int i = 0; i < data.Count; ++i)
                if (data[i])
                    return true;

            return false;
        }

        static bool TestViaListContains(List<bool> data)
        {
            return data.Contains(true);
        }
    }
}

このコードをテストするには、x86 RELEASE ビルドとしてコンパイルし、デバッガーの外部から実行する必要があります。

以下は、.Net 4.5 フレームワークを使用した Windows 8 x64 PC の結果です (ただし、.Net 4 でも同様の結果が得られます)。

Times are in milliseconds

126 TestViaLoop()
441 TestViaListContains()

122 TestViaLoop()
428 TestViaListContains()

131 TestViaLoop()
431 TestViaListContains()

138 TestViaLoop()
426 TestViaListContains()

122 TestViaLoop()
439 TestViaListContains()

ご覧のとおり、ループには私のシステムの約 1/3 の時間がかかります。

Resharper実装を見ると、List.Contains()次のようになります。

bool Contains(T item)
{
    if (item == null)
    {
        for (int j = 0x0; j < this._size; j++)
        {
            if (this._items[j] == null)
            {
                return true;
            }
        }
        return false;
    }
    EqualityComparer<T> comparer = EqualityComparer<T>.Default;
    for (int i = 0x0; i < this._size; i++)
    {
        if (comparer.Equals(this._items[i], item))
        {
            return true;
        }
    }
    return false;
}

使用していますがComparer.Equals()（ループよりも遅くなるはずです）、プライベート_items[]配列も直接使用しているため、ループの実装に使用されるインデックス範囲チェックが回避されます。

3 つの質問があります。

  1. 他の誰かが私が見ている結果を再現できますか? (デバッガーの外部でリリース ビルドを実行することを忘れないでください。)
  2. もしそうなら、私のループが よりもはるかに速くなる方法を誰か説明できますList.Contains()か?
  3. そうでない場合、ループが高速になっている理由を誰か説明できますか?

私は大量の数値データを処理し、可能な限り高速である必要があるコードを書いているので、これは私にとって単に学術的な関心事ではありません。(注: はい、私は物事をプロファイリングし、最適化が必要なものだけを最適化しようとします...時期尚早の最適化の問題については知っています。)

[編集]

これはプロセッサに関連している可能性があると思います。3.8 GHz のクアッド コアから 1.6 GHz の Pentium M シングル コアまで非常に異なるモデルではありますが、私が試したすべてのシステムには Intel プロセッサが搭載されています。

ループの実行速度が遅いと感じている方のために、Intel プロセッサを使用していますか?

4

2 に答える 2

1

ループの実装は と同じ出力を生成しContainsますが、一般的なケースでは使用できません。Equalsつまり、より複雑なオブジェクトの比較を使用する必要があります。Contains実装は実装よりも多くの作業を実行しているため、この場合、実装が高速になると期待する理由がわかりません。

カスタムPersonオブジェクトのリストがあり、それらのと などEqualsを比較するメソッドをオーバーライドした場合、ループはほぼ同じパフォーマンス コストで実行されます。Address Name SSNumberDateOfBirth

私はプリミティブ値を期待します。そうであれば、ループ反復はジェネリックよりも優れていますが、これは時期尚早の最適化であり、より複雑なオブジェクト比較Containsよりも (実質的に) 優れているとは言えません。Contains

于 2013-04-17T14:41:18.873 に答える