Есть ли разница в производительности между этими двумя алгоритмами тасования IEnumerable? - PullRequest
Новая
       23

Есть ли разница в производительности между этими двумя алгоритмами тасования IEnumerable?

4 голосов
/ 10 декабря 2010

Эти два вопроса дают аналогичные алгоритмы для тасования IEnumerable:

Вот два метода бок о бок: 

public static IEnumerable<T> Shuffle1<T> (this IEnumerable<T> source)
{
    Random random = new Random ();
    T [] copy = source.ToArray ();

    for (int i = copy.Length - 1; i >= 0; i--) {
        int index = random.Next (i + 1);
        yield return copy [index];
        copy [index] = copy [i];
    }
}


public static IEnumerable<T> Shuffle2<T> (this IEnumerable<T> source)
{
    Random random = new Random ();
    List<T> copy = source.ToList ();

    while (copy.Count > 0) {
        int index = random.Next (copy.Count);
        yield return copy [index];
        copy.RemoveAt (index);
    }
}

Они в основном идентичны, кроме одногоиспользует List, а один использует массив.Концептуально второй кажется мне более понятным.Но можно ли получить существенный выигрыш в производительности от использования массива?Даже если время Big-O такое же, но оно в несколько раз быстрее, оно может заметно измениться.

Ответы [ 3 ]

7 голосов
/ 10 декабря 2010

Вторая версия, вероятно, будет немного медленнее из-за RemoveAt.Списки - это действительно массивы, которые растут при добавлении к ним элементов, и поэтому вставка и удаление в середине происходит медленно (фактически MSDN утверждает, что RemoveAt имеет сложность O (n)).

В любом случае,Лучше всего просто использовать профилировщик для сравнения обоих методов.

2 голосов
/ 10 декабря 2010

Первый не компилируется, хотя очевидно, что вы пытаетесь переписать перечислимое, а затем реализовать Fisher-Yates; это, вероятно, правильный подход, и он не должен быть непонятным для любого, кто когда-либо переставлял массив. Второе использование RemoveAt плохо по причинам, указанным другими комментаторами.

РЕДАКТИРОВАТЬ: Ваша верхняя реализация выглядит сейчас правильно, и это хороший способ сделать это.

2 голосов
/ 10 декабря 2010

Первым алгоритмом является O (n), так как он имеет цикл, который выполняет перестановку O (1) на каждой итерации.Второй алгоритм - O (n ^ 2), так как он выполняет операцию O (n) RemoveAt на каждой итерации.Кроме того, индексаторы в списках работают медленнее, чем индексы в массивах, поскольку первый - это вызов метода, а второй - инструкция IL.

Таким образом, первый из них, вероятно, будет быстрее.Тем не менее, если вы после выступления, зачем беспокоиться о достижении результатов?Он уже преобразуется в массив, поэтому просто перетасуйте его на место и верните массив напрямую (или оберните в ReadOnlyCollection<T>, если вы беспокоитесь о том, что люди его изменят), что, вероятно, еще быстрее.обратите внимание, что оба метода имеют ошибки, что поведение Random при использовании несколькими потоками не определено, поэтому они, вероятно, должны использовать потокобезопасный генератор случайных чисел .

...