C# функциональный quicksort перестал работать

Question

C# функциональный quicksort перестал работать

Я пытаюсь реализовать quicksort в функциональном стиле с помощью C# с помощью linq, и этот код случайным образом работает / работа, и я не могу выяснить почему.
Важный для упоминания: Когда я называю это на массиве или списке, он хорошо работает. Но на unknown-what-it-really-is IEnumerable, это сходит с ума (теряет значения или катастрофические отказы, обычно. иногда работы.)
Код:

   public static IEnumerable<T> Quicksort<T>(this IEnumerable<T> source)
        where T : IComparable<T>
    {
        if (!source.Any())
            yield break;
        var pivot = source.First();
        var sortedQuery = source.Skip(1).Where(a => a.CompareTo(source.First()) <= 0).Quicksort()
                          .Concat(new[] { pivot })
                          .Concat(source.Skip(1).Where(a => a.CompareTo(source.First()) > 0).Quicksort());
        foreach (T key in sortedQuery)
            yield return key;
    }

Можно ли найти какие-либо отказы здесь, которые заставили бы это перестать работать?

Править: Некоторый лучший тестовый код:

        var rand = new Random();
        var ienum = Enumerable.Range(1, 100).Select(a => rand.Next());
        var array = ienum.ToArray();
        try
        {
            array.Quicksort().Count();
            Console.WriteLine("Array went fine.");
        }
        catch (Exception ex)
        {
            Console.WriteLine("Array did not go fine ({0}).", ex.Message);
        }
        try
        {
            ienum.Quicksort().Count();
            Console.WriteLine("IEnumerable went fine.");
        }
        catch (Exception ex)
        {
            Console.WriteLine("IEnumerable did not go fine ({0}).", ex.Message);
        }

9

c# linq functional-programming quicksort

задан Rubys 24 April 2010 в 15:33

1 ответ

Другие вопросы по тегам:

c# linq functional-programming quicksort

Похожие вопросы:

score 7 · Accepted Answer

Некоторые перечисляемые экземпляры, например, возвращаемые запросами Linq to SQL или Entity Framework, предназначены только для однократного повторения. Ваш код требует нескольких итераций и будет давать сбой или вести себя странно на экземплярах этих типов. Вам нужно сначала материализовать эти перечисления с помощью ToArray () или аналогичного метода.

Вам также следует повторно использовать этот pivot , чтобы вам не приходилось повторять итерацию для первого и оставшихся элементов.Это может не решить проблему полностью, но в некоторых случаях поможет:

public static IEnumerable<T> Quicksort<T>(this IEnumerable<T> source)
    where T : IComparable<T>
{
    if (!source.Any())
        return source;
    var pivot = source.First();
    var remaining = source.Skip(1);
    return remaining
        .Where(a => a.CompareTo(pivot) <= 0).Quicksort()
        .Concat(new[] { pivot })
        .Concat(remaining.Where(a => a.CompareTo(pivot) > 0).Quicksort());
}

(Вам также не нужно перебирать через sortedQuery - просто верните его, это уже представляет собой IEnumerable .)

В связи с этим, почему вы чувствуете необходимость повторно реализовать эту функциональность? Enumerable.OrderBy уже сделает это за вас.

Ответ на обновление:

Ваши тесты не проходят, потому что ваш тест неверен , а не алгоритм.

Random - это недетерминированный источник ввода, и, как я объяснил выше, метод сортировки должен выполнять несколько итераций в одной и той же последовательности. Если последовательность полностью случайна, то на последующих итерациях она будет получать разные значения. По сути, вы пытаетесь быстро отсортировать последовательность, элементы которой постоянно меняются!

Если вы хотите, чтобы тест прошел успешно, вам нужно сделать вход согласованным . Используйте seed для генератора случайных чисел:

static IEnumerable<int> GetRandomInput(int seed, int length)
{
    Random rand = new Random(seed);
    for (int i = 0; i < length; i++)
    {
        yield return rand.Next();
    }
}

Затем:

static void Main(string[] args)
{
    var sequence = GetRandomInput(248917, 100);
    int lastNum = 0;
    bool isSorted = true;
    foreach (int num in sequence.Quicksort())
    {
        if (num < lastNum)
        {
            isSorted = false;
            break;
        }
        lastNum = num;
    }
    Console.WriteLine(isSorted ? "Sorted" : "Not sorted");
    Console.ReadLine();
}

Он вернется отсортированным.