c# более быстрое n-арное декартово произведение для

Question

Я искал способ найти продукт из нескольких списков; Я использовал популярный ответ, который использует Aggregate + SelectMany. Проблема в том, что мой пример работает очень медленно: у меня есть 4 списка по 3К записей в каждом, и мне нужно перечислить каждую возможную комбинацию.

Кто-нибудь знает более быстрый путь в C#?

Я сделал скрипку здесь , которой в настоящее время не хватает памяти.

Ниже приведен код ссылки скрипты

public static void Main()
{
    var sources = new[]
    {
        Enumerable.Range(1, 3000),  
        Enumerable.Range(1, 3000),
        Enumerable.Range(1, 3000),
        Enumerable.Range(1, 3000),
    };
    var sw = new System.Diagnostics.Stopwatch();
    sw.Start();
    Console.Write("linq way...");

    foreach(var l in NCartesian(sources))
    {
        // just enumerate   
    }

    Console.WriteLine("{0}ms", sw.ElapsedMilliseconds);
}

public static IEnumerable<IEnumerable<T>> NCartesian<T>(
    IEnumerable<IEnumerable<T>> sequences)
{
    if (sequences == null)
    {
        return null;
    }

    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() 
};

    return sequences.Aggregate(
        emptyProduct,
        (accumulator, sequence) => accumulator.SelectMany(
            accseq => sequence,
            (accseq, item) => accseq.Concat(new[] { item })));
}

Answer 1

Я сделал тот, который использует меньше памяти, чем выше, но все же медленно:

public static IEnumerable<IEnumerable<T>> NCartesian<T>(
        IEnumerable<IEnumerable<T>> sequences)
    {
        if (sequences == null)
        {
            throw new ArgumentNullException(nameof(sequences));
        }

        var enumerators = new List<IEnumerator<T>>();
        foreach (IEnumerator<T> enumerator in sequences
            .Select(s => s.GetEnumerator()))
        {
            enumerator.MoveNext(); // move to the first position
            enumerators.Add(enumerator);
        }

        bool done = false;
        while (!done)
        {
            IList<T> result = enumerators.Select(e => e.Current).ToList();

            yield return result;

            for (int idx = enumerators.Count - 1; idx >= 0; idx--)
            {
                bool hasNext = enumerators[idx].MoveNext();
                if (hasNext)
                {
                    break;
                }

                if (idx == 0)
                {
                    // the first enumerator is done
                    done = true;
                    break;
                }

                enumerators[idx].Reset();
                enumerators[idx].MoveNext();
            }
        }
    }