Оптимизация Join, GroupBy, Distinct, Min / Max на естественно отсортированных последовательностях

Question

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

Например, Join считывает всю внутреннюю последовательность в хеш-таблицу и только затем перебирает внешнюю последовательность. Если бы две последовательности были отсортированы, объединение могло бы быть реализовано как простое объединение без дополнительного поиска и поиска в хеш-таблице.

Существует ли библиотека, имеющая альтернативные высокопроизводительные функции LINQ, работающие с предварительно отсортированными последовательностями?

Answer 1

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace OrderedJoin
{
    public static class EnumerableExtension
    {
        private enum JoinType
        {
            Inner,
            Left,
            Right,
            Full
        }

        private static IEnumerable<TResult> OrderedJoinIterator<T, TResult>(
            this IEnumerable<T> left, IEnumerable<T> right, Func<T, T, TResult> resultSelector, JoinType jt, IComparer<T> comparer)
        {
            if (left == null) throw new ArgumentNullException("left");
            if (right == null) throw new ArgumentNullException("right");
            if (resultSelector == null) throw new ArgumentNullException("resultSelector");

            if (comparer == null)
                comparer = Comparer<T>.Default;

            var l = left.GetEnumerator();
            var r = right.GetEnumerator();

            var lHasData = l.MoveNext();
            var rHasData = r.MoveNext();

            while (lHasData || rHasData)
            {
                if (!lHasData && rHasData)
                {
                    if (jt == JoinType.Inner || jt == JoinType.Left)
                        yield break;
                    yield return resultSelector(default(T), r.Current);
                    rHasData = r.MoveNext();
                    continue;
                }
                if (!rHasData && lHasData)
                {
                    if (jt == JoinType.Inner || jt == JoinType.Right)
                        yield break;
                    yield return resultSelector(l.Current, default(T));
                    lHasData = l.MoveNext();
                    continue;
                }

                var comp = comparer.Compare(l.Current, r.Current);

                if (comp < 0)
                {
                    if (jt == JoinType.Left || jt == JoinType.Full)
                        yield return resultSelector(l.Current, default(T));
                    lHasData = l.MoveNext();
                }
                else if (comp > 0)
                {
                    if (jt == JoinType.Right || jt == JoinType.Full)
                        yield return resultSelector(default(T), r.Current);
                    rHasData = r.MoveNext();
                }
                else
                {
                    yield return resultSelector(l.Current, r.Current);
                    lHasData = l.MoveNext();
                    rHasData = r.MoveNext();
                }
            }
        }

        public static IEnumerable<TResult> OrderedInnerJoin<T, TResult>(
            this IEnumerable<T> left, IEnumerable<T> right, Func<T, T, TResult> resultSelector, IComparer<T> comparer = null)
        {
            return OrderedJoinIterator(left, right, resultSelector, JoinType.Inner, comparer);
        }

        public static IEnumerable<TResult> OrderedFullJoin<T, TResult>(
            this IEnumerable<T> left, IEnumerable<T> right, Func<T, T, TResult> resultSelector, IComparer<T> comparer = null)
        {
            return OrderedJoinIterator(left, right, resultSelector, JoinType.Full, comparer);
        }

        public static IEnumerable<TResult> OrderedLeftJoin<T, TResult>(
            this IEnumerable<T> left, IEnumerable<T> right, Func<T, T, TResult> resultSelector, IComparer<T> comparer = null)
        {
            return OrderedJoinIterator(left, right, resultSelector, JoinType.Left, comparer);
        }

        public static IEnumerable<TResult> OrderedRightJoin<T, TResult>(
            this IEnumerable<T> left, IEnumerable<T> right, Func<T, T, TResult> resultSelector, IComparer<T> comparer = null)
        {
            return OrderedJoinIterator(left, right, resultSelector, JoinType.Right, comparer);
        }
    }

    internal class TestEnum : IEnumerable<int>
    {
        public TestEnum(string name, IList<int> nums)
        {
            Name = name;
            Nums = nums;
        }

        public string Name { get; private set; }
        public IList<int> Nums { get; private set; }

        public IEnumerator<int> GetEnumerator()
        {
            foreach (var item in Nums)
            {
                Console.WriteLine("{0}: {1}", Name, item);
                yield return item;
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var e1 = new TestEnum("L", new List<int> { 1, 2, 5, 6 });
            var e2 = new TestEnum("R", new List<int> { 1, 3, 4, 6 });

            var print = new Action<IEnumerable<string>>(seq => { foreach (var item in seq) Console.WriteLine("\t" + item); });

            Console.WriteLine("Standard Inner Join:");
            print(e1.Join(e2, i => i, j => j, (i, j) => string.Format("{0} <=> {1}", i, j), EqualityComparer<int>.Default));

            Console.WriteLine("Ordered Inner Join:");
            print(e1.OrderedInnerJoin(e2, (i, j) => string.Format("{0} <=> {1}", i, j)));

            Console.WriteLine("Ordered Full Join:");
            print(e1.OrderedFullJoin(e2, (i, j) => string.Format("{0} <=> {1}", i, j)));

            Console.WriteLine("Ordered Left Join:");
            print(e1.OrderedLeftJoin(e2, (i, j) => string.Format("{0} <=> {1}", i, j)));

            Console.WriteLine("Ordered Right Join:");
            print(e1.OrderedRightJoin(e2, (i, j) => string.Format("{0} <=> {1}", i, j)));

            Console.ReadLine();
        }
    }
}

Answer 2

Как упоминает Рид, было бы очень трудно выяснить, по какой последовательности была отсортирована последовательность, чтобы определить, будет ли работать оптимизация.Вам не нужно накатывать дублирующиеся классы коллекций или привязывать себя к конкретным реализациям (например, IOrderedEnumerable<T>), чтобы записывать переопределения методов расширения LINQ.

Итак, что насчет простого добавления некоторых новыхоператоры или перегрузки, когда вы, как потребитель, гарантируете, что данные заказаны.Это могут быть методы расширения для IEnumerable<T>, и они не гарантируют успеха, если только коллекция не будет заказана.

Примером может быть OrderedJoin, где вам нужно будет указать IComparable<TKey> в порядкезнать, какую последовательность следует выполнить дальше, если текущая позиция в каждой последовательности не соответствует ключу.Вот подпись как стартер.Вы можете сообщить нам, когда внедрили всю свою библиотеку!

public static IEnumerable<TResult> OrderedJoin<TOuter, TInner, TKey, TResult>(
    this IEnumerable<TOuter> outer,
    IEnumerable<TInner> inner,
    Func<TOuter, TKey> outerKeySelector,
    Func<TInner, TKey> innerKeySelector,
    Func<TOuter, TInner, TResult> resultSelector,
    IComparable<TKey> comparer
)

Answer 3

Я развиваю Nito.LINQ , как у меня есть время. Он предоставляет ISortedEnumerable и ISortedList некоторые из предложенных вами оптимизаций. Я также включил более противоречивые оптимизации (например, Skip для IList, что немного меняет семантику).

Answer 4

Да, но не для LINQ to Objects. Большинство провайдеров LINQ, которые работают на IQueryable<T>, уже переводят «нативную» функцию, которая могла бы легко реализовать этот тип оптимизации. Например, при работе с Entity Framework поставщик EF превратит это в вызов SQL, а БД (надеюсь) оптимизирует это правильно.

LINQ to Objects немного отличается. Там большинство подпрограмм (включая все вышеперечисленное) предназначены для работы с несортированными данными и даже с различными реализациями IEqualityComparer<T> или IComparer<T>. Это будет означать, что «оптимизированная» версия будет работать не только с небольшим набором потенциальных данных, но и оптимизирована только для подмножества стандартных операций запроса.

При этом было бы довольно легко сделать это, используя ваши собственные обертки вокруг стандартных операций LINQ, для этих конкретных случаев. Однако вам потребуется заранее знать, что рассматриваемая коллекция отсортирована, что, вероятно, потребует вашего собственного отдельного интерфейса (или проверки во время выполнения, например, Count() оптимизаций, выполненных на ICollection).