0

編集：いくつかのベンチマーク結果を追加します。リスト内の項目は約 1000 ～ 5000 で、IListと をRemoveAt上回っISetてRemoveいますが、違いはわずかであるため、心配する必要はありません。コレクションのサイズが 10000 以上になると、本当の楽しみが始まります。それらのデータのみを掲載しています

昨夜ここで質問に答えていて、奇妙な状況に直面しました。

まず、単純なメソッドのセット:

static Random rnd = new Random();
public static int GetRandomIndex<T>(this ICollection<T> source)
{
    return rnd.Next(source.Count);
}

public static T GetRandom<T>(this IList<T> source)
{
    return source[source.GetRandomIndex()];
}

-------------------------------------------------- -------------------------------------------------- --------------------------------

コレクションから N 個のアイテムをランダムに削除しているとしましょう。私はこの関数を書きます：

public static void RemoveRandomly1<T>(this ISet<T> source, int countToRemove)
{
    int countToRemain = source.Count - countToRemove; 
    var inList = source.ToList();

    int i = 0;
    while (source.Count > countToRemain)
    {
        source.Remove(inList.GetRandom()); 
        i++;
    }
}

また

public static void RemoveRandomly2<T>(this IList<T> source, int countToRemove)
{
    int countToRemain = source.Count - countToRemove;

    int j = 0;
    while (source.Count > countToRemain)
    {
        source.RemoveAt(source.GetRandomIndex()); 
        j++; 
    }
}

ご覧のとおり、最初の関数は an 用ISetに、2 番目の関数は normal 用に記述されていますIList。最初の関数では、 からアイテムごとに、 からインデックスごとに削除していますが、どちらも. 特にリストが大きくなると、2 番目の関数のパフォーマンスが最初の関数よりも大幅に低下するのはなぜですか?ISetIListO(1)

オッズ (私の見解):

1) 最初の関数では、 (からランダムな項目を取得するために)ISetが に変換されますが、2 番目の関数ではそのようなことは実行されません。IListIList

アドバンテージ IList。

2) 最初の関数では への呼び出しGetRandomItemが行われますが、2 番目の関数では への呼び出しGetRandomIndexが行われますが、これも 1 ステップ少なくなります。

些細なことですが、IList を活用してください。

3) 最初の関数では、別のリストからランダムなアイテムが取得されるため、取得されたアイテムは既に から削除されている可能性がありますISet。whileこれにより、最初の関数のループでより多くの反復が行われます。2 番目の関数では、反復されるソースからランダム インデックスが取得されるため、反復が繰り返されることはありません。私はこれをテストし、これを確認しました。

i > j 常に有利IList。

この動作の理由は、Listアイテムが追加または削除されたときに常にサイズを変更する必要があるためだと思いました。しかし、明らかに他のテストではそうではありません。私は走った：

public static void Remove1(this ISet<int> set)
{
    int count = set.Count;
    for (int i = 0; i < count; i++)
    {
        set.Remove(i + 1);
    }
}

public static void Remove2(this IList<int> lst)
{
    for (int i = lst.Count - 1; i >= 0; i--)
    {
        lst.RemoveAt(i);
    }
}

2 番目の関数の方が高速に実行されることがわかりました。

テスト ベッド:

var f = Enumerable.Range(1, 100000);

var s = new HashSet<int>(f);
var l = new List<int>(f);

Benchmark(() =>
{
    //some examples...

    s.RemoveRandomly1(2500);
    l.RemoveRandomly2(2500);

    s.Remove1();
    l.Remove2();

}, 1);

public static void Benchmark(Action method, int iterations = 10000)
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    for (int i = 0; i < iterations; i++)
        method();

    sw.Stop();
    MsgBox.ShowDialog(sw.Elapsed.TotalMilliseconds.ToString());
}

2つの構造が何であるかを知りたいだけです..ありがとう..

結果：

var f = Enumerable.Range(1, 10000);

s.RemoveRandomly1(7500); => 5ms
l.RemoveRandomly2(7500); => 20ms


var f = Enumerable.Range(1, 100000);

s.RemoveRandomly1(7500); => 7ms
l.RemoveRandomly2(7500); => 275ms


var f = Enumerable.Range(1, 1000000);

s.RemoveRandomly1(75000); => 50ms
l.RemoveRandomly2(75000); => 925000ms

ただし、最も一般的なニーズの場合は、リストで十分です..!

4

1 に答える 1

4

まず、IList と ISet は何かの実装ではありません。非常に異なる方法で実行される IList または ISet 実装を作成できるため、具体的な実装が重要です (この場合は List と HashSet)。

インデックスによるリスト項目へのアクセスは O(1)ですが、 O(n)による削除はRemoveAtありません。

何もコピーする必要がないため、最後からのリストの削除は高速です。基になる配列の空のスポットの数がしきい値を下回るまで、アイテムの数を格納する内部カウンターを減らすだけです。配列をより小さい配列にコピーします。基になる配列の最大容量に達すると、サイズが 2 倍の新しい配列が作成され、要素がコピーされます。特定のしきい値を下回ると、半分のサイズの配列が作成され、要素がコピーされます。未使用のスロットが存在しないように見えるように、長さプロパティでその大きさを追跡します。

リストからランダムに削除するということは、インデックスの後に来るすべての配列エントリをコピーして、1 つの場所にスライドさせる必要があることを意味します。これは、特にリストのサイズが大きくなるにつれて、本質的にかなり遅くなります。100 万のエントリを持つ List があり、インデックス 500,000 の何かを削除する場合、配列の後半を 1 つ下にコピーする必要があります。

于 2012-11-24T18:21:32.160 に答える