c# - 関数を ArrayList で "Contains" と同じくらい速く実行するにはどうすればよいですか?

Question

Containsメソッドが要素を見つけるのArrayListにかかる時間と、私が書いた小さな関数が同じことをするのにかかる時間との不一致を理解できません。ドキュメントにContainsは、線形検索を実行すると記載されているためO(n)、他の高速な方法ではなく、そうであると想定されています。ただし、正確な値は関係ないかもしれませんがContains、00:00:00.1087087関数が00:00:00.1876165. 大したことではないかもしれませんが、この違いはさらに大きな配列を扱う場合により顕著になります。何が欠けていますContainsか? のパフォーマンスに合わせて関数をどのように記述すればよいですか?

.NET 3.5 で C# を使用しています。

public partial class Window1 : Window
{
    public bool DoesContain(ArrayList list, object element)
    {
        for (int i = 0; i < list.Count; i++)
            if (list[i].Equals(element)) return true;

        return false;
    }

    public Window1()
    {
        InitializeComponent();

        ArrayList list = new ArrayList();
        for (int i = 0; i < 10000000; i++) list.Add("zzz " + i);

        Stopwatch sw = new Stopwatch();
        sw.Start();

        //Console.Out.WriteLine(list.Contains("zzz 9000000") + " " + sw.Elapsed);
        Console.Out.WriteLine(DoesContain(list, "zzz 9000000") + " " + sw.Elapsed);
    }
}

編集：

よし、さあ、みんな、見て。

public partial class Window1 : Window
{
    public bool DoesContain(ArrayList list, object element)
    {
        int count = list.Count;
        for (int i = count - 1; i >= 0; i--)
            if (element.Equals(list[i])) return true;

        return false;
    }


    public bool DoesContain1(ArrayList list, object element)
    {
        int count = list.Count;
        for (int i = 0; i < count; i++)
            if (element.Equals(list[i])) return true;

        return false;
    }

    public Window1()
    {
        InitializeComponent();

        ArrayList list = new ArrayList();
        for (int i = 0; i < 10000000; i++) list.Add("zzz " + i);

        Stopwatch sw = new Stopwatch();
        long total = 0;
        int nr = 100;

        for (int i = 0; i < nr; i++)
        {
            sw.Reset();
            sw.Start();
            DoesContain(list,"zzz");
            total += sw.ElapsedMilliseconds;
        }
        Console.Out.WriteLine(total / nr);


        total = 0;
        for (int i = 0; i < nr; i++)
        {
            sw.Reset();
            sw.Start();
            DoesContain1(list, "zzz");
            total += sw.ElapsedMilliseconds;
        }
        Console.Out.WriteLine(total / nr);


        total = 0;
        for (int i = 0; i < nr; i++)
        {
            sw.Reset();
            sw.Start();
            list.Contains("zzz");
            total += sw.ElapsedMilliseconds;
        }
        Console.Out.WriteLine(total / nr);
    }
  }

関数の 2 つのバージョン (順方向ループと逆方向ループ) と既定の関数で、平均 100 回の実行時間を記録しましたContains。私が得た時間は、私の機能ではミリ秒で136あり、バージョン133でははるかに勝者です。さて、データが不足していると主張する前に、最初の単独の実行に基づいて結論を出したとしたら、このテストについてどう思いますか? 平均してパフォーマンスが向上するだけでなく、実行ごとに一貫してより良い結果が得られます。では、サードパーティの機能に関して、ここになんらかの欠点がありますか?87ContainsContains

score 11 · Accepted Answer

まず、何度も実行して平均を比較していません。

第二に、メソッドは実際に実行されるまでジットされません。そのため、ジャストインタイムのコンパイル時間が実行時間に追加されます。

真のテストでは、それぞれ複数回実行し、結果を平均します (合計 Y 回のうち X を実行するために、いずれかが遅くなる原因になる可能性があります)。

score 5 · Accepted Answer

ArrayList.NET 3.5 を使用しているのに、最初から .NET 3.5 ではなくを使用しているのはなぜList<string>ですか?

試してみるいくつかのこと：

ループforeachの代わりに使用することが役立つかどうかを確認できますfor

カウントをキャッシュできます：

public bool DoesContain(ArrayList list, object element)
{
    int count = list.Count;
    for (int i = 0; i < count; i++)
    {
        if (list[i].Equals(element))
        {
            return true;
        }
        return false;
    }
}

比較を逆にすることができます：
```
if (element.Equals(list[i]))
```

これらのどれもが有意な (プラスの) 違いをもたらすとは思いませんが、次に試してみたいことです。

この封じ込めテストを複数回行う必要がありますか? その場合は、を作成しHashSet<T>て繰り返し使用することをお勧めします。

score 2 · Accepted Answer

Reflector コードの投稿が許可されているかどうかはわかりませんが、Reflector を使用してメソッドを開くと、本質的に同じであることがわかります(null 値に対していくつかの最適化がありますが、テストハーネスには null が含まれていません)。）。

私が見ることができる唯一の違いは、呼び出しlist[i]は境界チェックを行うiのに対し、Contains メソッドはそうしないことです。

score 1 · Accepted Answer

以下のコードを使用して、次のタイミングを比較的一貫して (数ミリ秒以内に) 取得することが
でき
ました
。

ここで注目すべき点がいくつかあります。

これは、コマンドラインからリリースコンパイルされたコードで実行されます。多くの人が、Visual Studio デバッグ環境内でコードのベンチマークを行うという間違いを犯しています。

はlist[i].Equals(element)よりも少し遅いようですelement.Equals(list[i])。

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


namespace ArrayListBenchmark
{
class Program
{
    static void Main(string[] args)
    {
        Stopwatch sw = new Stopwatch();
        const int arrayCount = 10000000;
        ArrayList list = new ArrayList(arrayCount);
        for (int i = 0; i < arrayCount; i++) list.Add("zzz " + i);
    sw.Start();
    DoesContainRev(list, "zzz");
    sw.Stop();
    Console.WriteLine(String.Format("1: {0}", sw.ElapsedMilliseconds));
    sw.Reset();

    sw.Start();
    DoesContainRev1(list, "zzz");
    sw.Stop();
    Console.WriteLine(String.Format("2: {0}", sw.ElapsedMilliseconds));
    sw.Reset();

    sw.Start();
    DoesContainFwd(list, "zzz");
    sw.Stop();
    Console.WriteLine(String.Format("3: {0}", sw.ElapsedMilliseconds));
    sw.Reset();

    sw.Start();
    DoesContainFwd1(list, "zzz");
    sw.Stop();
    Console.WriteLine(String.Format("4: {0}", sw.ElapsedMilliseconds));
    sw.Reset();

    sw.Start();
    list.Contains("zzz");
    sw.Stop();
    Console.WriteLine(String.Format("5: {0}", sw.ElapsedMilliseconds));
    sw.Reset();

    Console.ReadKey();
}
public static bool DoesContainRev(ArrayList list, object element)
{
    int count = list.Count;
    for (int i = count - 1; i >= 0; i--)
        if (element.Equals(list[i])) return true;

    return false;
}
public static bool DoesContainFwd(ArrayList list, object element)
{
    int count = list.Count;
    for (int i = 0; i < count; i++)
        if (element.Equals(list[i])) return true;

    return false;
}
public static bool DoesContainRev1(ArrayList list, object element)
{
    int count = list.Count;
    for (int i = count - 1; i >= 0; i--)
        if (list[i].Equals(element)) return true;

    return false;
}
public static bool DoesContainFwd1(ArrayList list, object element)
{
    int count = list.Count;
    for (int i = 0; i < count; i++)
        if (list[i].Equals(element)) return true;

    return false;
}
         }
        }

score 1 · Accepted Answer

まず、事前に知っている型を使用している場合は、ジェネリックを使用することをお勧めします。したがって、ArrayList の代わりに List を使用します。ボンネットの下で、ArrayList.Contains は実際にあなたがしていることよりも少し多くのことを行います。以下はリフレクターからのものです。

public virtual bool Contains(object item)
{
    if (item == null)
    {
        for (int j = 0; j < this._size; j++)
        {
            if (this._items[j] == null)
            {
                return true;
            }
        }
        return false;
    }
    for (int i = 0; i < this._size; i++)
    {
        if ((this._items[i] != null) && this._items[i].Equals(item))
        {
            return true;
        }
    }
    return false;
}

item に null 値が渡されると、それ自体が fork することに注意してください。ただし、例のすべての値がnullではないため、最初と2番目のループでのnullの追加チェックには、理論的には時間がかかります。

完全にコンパイルされたコードを扱っていると確信していますか? つまり、コードが初めて実行されるときに、フレームワークが明らかに既にコンパイルされている場合に、JIT コンパイルが行われます。

score 1 · Accepted Answer

本当に優れたオプティマイザーでは、セマンティクスが同じように見えるため、違いはまったくないはずです。ただし、既存のオプティマイザーは、ハードコーディングされた最適化が最適化されているため、関数を最適化できませんContains。最適化のポイント:

毎回プロパティと比較すると、カウントダウンして 0 と比較するよりも遅くなる可能性があります
関数呼び出し自体にパフォーマンス上のペナルティがあります
明示的なインデックス作成の代わりに反復子を使用すると、より高速になります (foreachプレーンではなくループfor)

score 1 · Accepted Answer

編集後、コードをコピーし、いくつかの改善を加えました。
違いは再現できませんでした。測定/丸めの問題であることが判明しました。

それを確認するには、実行を次の形式に変更します。

    sw.Reset();
    sw.Start();
    for (int i = 0; i < nr; i++)
    {          
        DoesContain(list,"zzz");            
    }
    total += sw.ElapsedMilliseconds;
    Console.WriteLine(total / nr);

一部の行を移動しただけです。この繰り返し回数では、JIT の問題は重要ではありませんでした。

score 0 · Accepted Answer

コメントを読んだ後に改訂：

高速検索を有効にするためにハッシュアルゴリズムを使用しません。

score 0 · Accepted Answer

私の推測では、ArrayList は C++ で記述されており、いくつかのマイクロ最適化を利用している可能性があります (注: これは推測です)。

たとえば、C++ では、ポインター演算 (具体的にはポインターをインクリメントして配列を反復処理する) を使用して、インデックスを使用するよりも高速にすることができます。

score 0 · Accepted Answer

キーに基づく高速アクセスにはSortedList<TKey,TValue>、Dictionary<TKey, TValue>またはを使用します。System.Collections.ObjectModel.KeyedCollection<TKey, TValue>

var list = new List<myObject>(); // Search is sequential
var dictionary = new Dictionary<myObject, myObject>(); // key based lookup, but no sequential lookup, Contains fast
var sortedList = new SortedList<myObject, myObject>(); // key based and sequential lookup, Contains fast

KeyedCollection<TKey, TValue>も高速で、インデックス付きルックアップが可能ですが、抽象的であるため継承する必要があります。したがって、特定のコレクションが必要です。ただし、次を使用すると、ジェネリックを作成できますKeyedCollection。

public class GenericKeyedCollection<TKey, TValue> : KeyedCollection<TKey, TValue> {
   public GenericKeyedCollection(Func<TValue, TKey> keyExtractor) {
      this.keyExtractor = keyExtractor;
   }

   private Func<TValue, TKey> keyExtractor;

   protected override TKey GetKeyForItem(TValue value) {
      return this.keyExtractor(value);
   }
}

KeyedCollection を使用する利点は、Add メソッドでキーを指定する必要がないことです。

score 0 · Accepted Answer

配列構造を使用すると、追加情報がなければ O(n) よりも高速に検索できません。配列がソートされていることがわかっている場合は、バイナリ検索アルゴリズムを使用して o(log(n)) のみを使用できます。それ以外の場合は、セットを使用する必要があります。

c# - 関数を ArrayList で "Contains" と同じくらい速く実行するにはどうすればよいですか?

11 に答える 11

Related

Reference