Оптимизация функции OrderBy () при использовании Any () - PullRequest
6 голосов
/ 24 января 2012

Итак, у меня достаточно стандартная настройка LINQ-to-Object.

var query = expensiveSrc.Where(x=> x.HasFoo)
                        .OrderBy(y => y.Bar.Count())
                        .Select(z => z.FrobberName);    

// ...

if (!condition && !query.Any())
 return; // seems to enumerate and sort entire enumerable 

// ...

foreach (var item in query)
   // ...

Это перечисляет все дважды. Что плохо

var queryFiltered = expensiveSrc.Where(x=> x.HasFoo);

var query = queryFiltered.OrderBy(y => y.Bar.Count())
                         .Select(z => z.FrobberName); 

if (!condition && !queryFiltered.Any())
   return;

// ...

foreach (var item in query)
   // ...

Работает, но есть ли лучший способ?

Был бы какой-нибудь ненормальный способ "просветить" Any (), чтобы обойти ненужные операции? Я думаю, что помню этот вид оптимизации, идущий в EduLinq.

Ответы [ 7 ]

9 голосов
/ 24 января 2012

Почему бы просто не избавиться от лишнего:

if (!query.Any())
 return; 

Похоже, что он действительно не служит какой-либо цели - даже без него тело foreach не будет выполнено, если запрос не даст результатов. Таким образом, при регистрации Any() вы ничего не сохраняете на быстром пути и дважды перечисляете на медленном пути.

С другой стороны, если вы должны знать, были ли найдены какие-либо результаты после окончания цикла, вы также можете просто использовать флаг:

bool itemFound = false;

foreach (var item in query)
{
    itemFound = true;
    ... // Rest of the loop body goes here.
}

if(itemFound)
{
   // ...
}

Или вы можете использовать перечислитель напрямую, если вы действительно обеспокоены избыточной установкой флага в теле цикла:

using(var erator = query.GetEnumerator())
{
    bool itemFound = erator.MoveNext();

    if(itemFound)
    {
       do
       {
           // Do something with erator.Current;
       } while(erator.MoveNext())
    }

   // Do something with itemFound
}
2 голосов
/ 08 июля 2012

Был бы какой-нибудь ненормальный способ "просветить" Any (), чтобы обойти ненужные операции?Я думаю, что помню этот вид оптимизации, идущий в EduLinq.

Ну, я не собираюсь игнорировать любой вопрос, который упоминает Edulinq:)

В этом случае Edulinq вполне может бытьбыстрее, чем LINQ to Objects, поскольку его реализация OrderBy настолько ленива, насколько это возможно - она ​​сортирует столько, сколько нужно для извлечения возвращаемых элементов.

Однако, по сути, это все еще должен прочитать всю последовательность прежде, чем она возвратит что-нибудь.В конце концов, последний элемент в последовательности может быть первым, который должен быть возвращен.

Если вы контролируете весь стек, вы могли бы заставить Any() обнаружитьчто он вызывается в вашей «известной» реализации IOrderedEnumerable и идет прямо к первоисточнику.Обратите внимание, что это действительно создает изменение в наблюдаемом поведении, хотя - если итерация по всей последовательности вызывает исключение (или имеет любой другой побочный эффект), то этот побочный эффект будет потерян оптимизацией.Конечно, можно утверждать, что все в порядке - то, что считается «действительной» оптимизацией в LINQ, является весьма сложной областью.

Еще одна возможность, которая довольно ужасна, но которая решит эту конкретную проблему, заключается в создании итератора.возвращается из IOrderedEnumerable, просто возьмите первое значение MoveNext() из источника.Этого достаточно для нормальной реализации Any, и в этот момент нам не нужно знать, что такое первый элемент.Мы могли бы отложить фактическую сортировку до первого использования свойства Current.

Хотя это довольно частная оптимизация - и я бы с осторожностью ее реализовал.Я думаю, что подход Ани является лучшим - просто используйте тот факт, что итерации по query с использованием foreach никогда не попадут в тело цикла, если результаты запроса будут пустыми.

2 голосов
/ 06 июля 2012

Существует не так много информации, которую можно извлечь из перечислимого, поэтому, может быть, лучше превратить запрос в IQueryable? Этот метод расширения Any спускается по дереву выражений, пропуская все нерелевантные операции, затем превращает важную ветвь в делегат, который можно вызывать для получения оптимизированного IQueryable. Стандартный Any метод применяется к нему явно, чтобы избежать рекурсии. Не уверен насчет угловых случаев, и, возможно, имеет смысл кэшировать скомпилированные запросы, но с такими простыми запросами, как ваш, похоже, это работает.

static class QueryableHelper {
    public static bool Any<T>(this IQueryable<T> source) {
        var e = source.Expression;
        while (e is MethodCallExpression) {
            var mce = e as MethodCallExpression;
            switch (mce.Method.Name) {
                case "Select":
                case "OrderBy":
                case "ThenBy": break;
                default: goto dun;
            }
            e = mce.Arguments.First();
        }
        dun:
        var d = Expression.Lambda<Func<IQueryable<T>>>(e).Compile();
        return Queryable.Any(d());
    }
}

Сами запросы должны быть изменены следующим образом:

var query = expensiveSrc.AsQueryable()
                        .Where(x=> x.HasFoo)
                        .OrderBy(y => y.Bar.Count())
                        .Select(z => z.FrobberName); 
2 голосов
/ 06 июля 2012

Редактировать (исправлено): В этом ответе рассматривается проблема выполнения запроса дважды, которая, как я считаю, является ключевой.Ниже показано, почему:

Умнее Any() - это то, что могут делать только разработчики Linq, IMO ... Или это было бы грязное приключение с использованием отражения.

Использование класса, как показанониже вы можете кэшировать вывод исходного перечислимого и позволить его перечислить дважды:

public class CachedEnumerable<T> 
{
    public CachedEnumerable(IEnumerable<T> enumerable)
    {
        _source = enumerable.GetEnumerator();
    }

    public IEnumerable<T> Enumerate()
    {
        int itemIndex = 0;
        while (true)
        {
            if (itemIndex < _cache.Count)
            {
                yield return _cache[itemIndex];
                itemIndex++;
                continue;
            }

            if (!_source.MoveNext())
                yield break;

            var current = _source.Current;
            _cache.Add(current);
            yield return current;
            itemIndex++;                 
        }

    }

    private List<T> _cache = new List<T>();
    private IEnumerator<T> _source;
}

Таким образом, вы сохраняете ленивый аспект LINQ, сохраняете код читабельным и универсальным.Это будет медленнее, чем напрямую, используя IEnumerator<>.Существует множество возможностей для расширения и оптимизации этого класса, таких как политика удаления старых элементов, избавления от сопрограммы и т. Д. Но я думаю, что это не относится к этому вопросу.

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

Почему это было бы оптимальным?

Давайте рассмотрим два варианта: перечисление можетСодержать элементы или нет.

  • Если он содержит элементы, этот подход является оптимальным, поскольку запрос выполняется только один раз.
  • Если он не содержит элементов, у вас возникнет соблазн исключить часть ваших запросов OrderBy и Select, поскольку они не добавляют значения.Но ... если после предложения Where() есть ноль элементов, то есть ноль элементов для сортировки, что будет стоить ноль времени (ну, почти).То же самое относится и к предложению Select().

Что, если это еще не достаточно быстро? В этом случае моей стратегией было бы обойти Linq.Теперь я действительно люблю linq, но его элегантность имеет свою цену.Таким образом, на каждые 100 раз использования Linq обычно требуется одно или два вычисления, которые важны для очень быстрого выполнения, которое я пишу со старым добрым значением для циклов и списков.Частью освоения технологии является признание того, где она не подходит.Linq не является исключением из этого правила.

1 голос
/ 06 июля 2012

, но я потерял потоковую / ленивую загрузку, что вдвое меньше точки linq

Ленивая загрузка (отложенное выполнение) и 2 запроса LINQ с разрозненнойрезультаты не могут быть оптимизированы (уменьшены) до 1 выполнения запроса.

1 голос
/ 06 июля 2012

Попробуйте это:

var items = expensiveSrc.Where(x=> x.HasFoo)
                        .OrderBy(y => y.Bar.Count())
                        .Select(z => z.FrobberName).ToList();   

// ...

if (!condition && items.Count == 0)
 return; // Just check the count

// ...

foreach (var item in items)
   // ...

Запрос выполняется только один раз.

0 голосов
/ 13 июля 2012

почему вы не используете .ToArray ()

var query = expensiveSrc.Where(x=> x.HasFoo)
                    .OrderBy(y => y.Bar.Count())
                    .Select(z => z.FrobberName).ToArray();    

если нет элементов, сортировка и выборка не должны давать больших накладных расходов. если вы сортируете, то вам все равно нужен кеш, где хранятся данные, поэтому накладных расходов .ToArray не должно быть так много. если вы декомпилируете класс OrderedEnumerable, вы обнаружите, что там сформирован массив int [], содержащий ссылки, поэтому вы просто создаете с помощью .ToArray (или .ToList) новый ссылочный массив.

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

...