Построение «плоских», а не «деревовидных» выражений LINQ

Я использую некоторый код (доступный здесь в MSDN) для динамического построения выражений LINQ, содержащих несколько «предложений» ИЛИ.

Соответствующий код

var equals = values.Select(value => (Expression)Expression.Equal(valueSelector.Body, Expression.Constant(value, typeof(TValue))));

var body = equals.Aggregate<Expression>((accumulate, equal) => Expression.Or(accumulate, equal));

Это генерирует выражение LINQ, которое выглядит примерно так:

(((((ID = 5) OR (ID = 4)) OR (ID = 3)) OR (ID = 2)) OR (ID = 1))

Я достигаю предела рекурсии (100) при использовании этого выражения, поэтому я хотел бы сгенерировать выражение, которое выглядит так:

(ID = 5) OR (ID = 4) OR (ID = 3) OR (ID = 2) OR (ID = 1)

Как мне изменить код построения выражения, чтобы сделать это?


.net linq wcf-data-services
person Ian Gregory    schedule 30.05.2010    source источник

Ответы (2)


arrow_upward
6
arrow_downward

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

 Your code               Better
 ---------              --------
    OR                     OR
 #1    OR              OR      OR
     #2  OR          #1  #2  #3  #4
       #3  #4

Как видите, даже в этом простом случае лучший подход — не такой глубокий (рекурсивно вложенный). Код для создания лучшего дерева выражений можно написать в виде рекурсивного метода на C#:

Expression GenerateTree(List<Expression> exprs, int start, int end) {
  // End of the recursive processing - return single element
  if (start == end) return exprs[start];

  // Split the list between two parts of (roughly the same size)
  var mid = start + (end - start)/2;
  // Process the two parts recursively and join them using OR
  var left = GenerateTree(exprs, start, mid);
  var right = GenerateTree(exprs, mid+1, end);
  return Expression.Or(left, right);
}

// Then call it like this:
var equalsList = equals.ToList();
var body = GenerateTree(equalsList, 0, equalsList.Length);

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

person Tomas Petricek    schedule 30.05.2010
comment
Небольшое изменение — замените equalsList.Length на equalsList.Count-1 — и все работает отлично. Спасибо. - person Ian Gregory; 02.06.2010

arrow_upward
1
arrow_downward

Если это действительно LINQ to Objects в соответствии с вашими тегами, зачем вы вообще строите деревья выражений? Вы можете очень легко использовать делегатов, и у них не будет ограничений на рекурсию.

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

var query = from item in source
            where idCollection.Contains(item.Id)
            ...
person Jon Skeet    schedule 30.05.2010
comment
Извините, моя пометка была неправильной. Я использую службы данных WCF, где встречается ограничение рекурсии. - person Ian Gregory; 31.05.2010
comment
@Ian: Службы данных WCF не позволяют использовать «Содержит»? Это все равно будет предпочтительным подходом IMO... - person Jon Skeet; 31.05.2010
comment
В .NET 3.5 этого нет. Он не может преобразовать contains в синтаксис URI. - person Ian Gregory; 31.05.2010
comment
Также с LinqToSql есть проблема со строками Contains и ANSI, поэтому мне пришлось использовать OR, чтобы справиться с этим. - person Giedrius; 22.08.2012
comment
@Giedrius: Что именно вы подразумеваете под строками ANSI? - person Jon Skeet; 22.08.2012
comment
Столбцы типа @JonSkeet varchar в базе данных sql, описание проблемы и решение здесь stackoverflow.com/questions/1699382/, но мы переписали дерево выражений вместо изменения параметров dbCommand. - person Giedrius; 22.08.2012