Каков наилучший способ оптимизации вложенного предложения where с несколькими условиями?

Question

Я пытаюсь найти список ReturnItems, в котором количество возвращаемого отдельного товара превышает исходное заказанное количество для этого товара. Таким образом, здесь есть 2 разных списка объектов - IEnumerable<ReturnItem> и IEnumerable<OrderItem>. Проблема заключается в том, что в зависимости от источника для возврата (в нашем рабочем процессе есть несколько мест, где можно сделать возврат), ItemNumber для данного ReturnItem может быть нулевым. В этом случае нам нужно полагаться на ReturnItem.OrderItemId, чтобы сопоставить его с OrderItem.

Я решил проблему с помощью LINQ, но для этого требуется вложенный цикл for (под капотом), поэтому я стараюсь избегать этого, если это возможно, в то же время сохраняя читабельность. Другими словами, я хочу избежать времени выполнения O (N ^ 2) и ищите O (N) или лучше, но опять же, сохраняя читабельность (я знаю, что здесь много чего спрашиваю, но я решил, что у меня будет творческое решение). Я создал решение, в котором у меня есть два словаря для элементов заказа. Один из них, ключ - это номер позиции, а другой ключ - идентификатор позиции заказа. Это работает и решает проблему производительности, но я полностью теряю удобочитаемость.

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

// ItemsForReturn = IEnumerable<ReturnItem>
// OrderItems = IEnumerable<OrderItem>

var invalidQuantityItems = message.ItemsForReturn.Where(returnItem =>
{
    var matchingOrderItemQuantity = message.OrderItems
        .Where(orderItem => orderItem.ItemNumber.Equals(returnItem.ItemNumber) || orderItem.OrderItemId == returnItem.OrderItemId)
        .Sum(orderItem => orderItem.Quantity);

    return matchingOrderItemQuantity < returnItem.Quantity;
});

и соответствующие типы переменных, использованные выше:

public class ReturnItem
{
    public int OrderItemId {get; set;}
    public string ItemNumber {get; set;}
    public int Quantity {get; set;}
    // There's more properties but these are the ones that matter
{

public class OrderItem
{
    public int OrderItemId {get; set;}
    public string ItemNumber {get; set;}
    public int Quantity {get; set;}
    // There's more properties but these are the ones that matter
{

Я ожидаю, что var invalidQuantityItems будет IEnumerable<ReturnItems>, чье количество для отдельного предмета больше, чем заказанное количество (т. Е. Они пытаются вернуть больше, чем они заказали в первую очередь).

Ура!

Answer 1

Небольшая поправка - временная сложность текущей реализации составляет O (N * M), и лучшее, что вы можете получить, это O (N + M).

Проблема состоит в том, как эффективно коррелировать два набора,В LINQ это достигается с помощью объединений , а для этого типа корреляции один-ко-многим - объединение групп .Эквивалентом || критериев будет Объединение результатов двух объединений групп (подходящих наборов).

Если говорить о читабельности, LINQ и объединениях, то лучше всего будет использовать LINQ запрос синтаксис (есть причина, по которой некоторые люди также называют его понимание синтаксис).

Таким образом, рассматриваемый запрос может быть эффективно (и, надеюсь, читабелен) переписан следующим образом:

var invalidQuantityItems =
    from returnItem in message.ItemsForReturn
    join orderItem in message.OrderItems on returnItem.ItemNumber equals orderItem.ItemNumber
    into matchingOrderItems1
    join orderItem in message.OrderItems on returnItem.OrderItemId equals orderItem.OrderItemId
    into matchingOrderItems2
    let matchingOrderItemQuantity = matchingOrderItems1.Union(matchingOrderItems2)
        .Sum(orderItem => orderItem.Quantity)
    where matchingOrderItemQuantity < returnItem.Quantity
    select returnItem;

Answer 2

Я думаю, что словарный подход - лучший путь.

По поводу читабельности, думаю, это должно быть не так уж и плохо:

var quantityByItemNumber = message.OrderItems.
    Where(i => i.ItemNumber != null).
    ToDictionary(
        i => i.ItemNumber,
        i => i.Quantity);

var quantityByOrderItemId = message.OrderItems.ToDictionary(
    i => i.OrderItemId,
    i => i.Quantity);

var invalidQuantityItems = message.ItemsForReturn.Where(returnItem =>
{
    int matchingOrderItemQuantity;
    var isNumberMatch = returnItem.ItemNumber != null) &&
        quantityByItemNumber.TryGetValue(returnItem.ItemNumber, out matchingOrderItemQuantity);

    if (!isNumberMatch)
        quantityByOrderItemId.TryGetValue(returnItem.OrderItemId, out matchingOrderItemQuantity)

    return matchingOrderItemQuantity < returnItem.Quantity;
});

На самом деле, я думаю, что это даже более читабельно, потому что не ошибочно притворяется, что существует более одного совпадения OrderItem, количество которого нужно суммировать.

Answer 3

Что касается оптимизации нескольких условий:

1. Всегда ставьте наиболее вероятные условия, которые в первую очередь завершат оценку (вам придется определять это на основе существующих данных или ваших знаний о системе).
2. Если нет большой вероятности того, что одно условие встречается чаще, чем другое, тогда мы можем рассмотреть саму оценку.Например, если сравнение int выполняется быстрее, чем сравнение string, поместите сначала сравнение int.

Кроме того, для получения кода не требуется отдельная строкаSum;Вы можете сделать это в том же выражении:

var invalidQuantityItems = message.ItemsForReturn.Where(returnItem =>
    message.OrderItems
        .Where(orderItem =>
            orderItem.OrderItemId == returnItem.OrderItemId ||
            orderItem.ItemNumber.Equals(returnItem.ItemNumber))
        .Sum(orderItem => orderItem.Quantity) < returnItem.Quantity);