Проверка, соответствует ли какой-либо элемент в списке какому-либо элементу в другом списке

#c# #algorithm #.net-3.5

#c# #алгоритм #.net-3.5

Вопрос:

Коллега попросил меня написать однострочный текст для замены следующего метода:

 public static bool IsResourceAvailableToUser(IEnumerable<string> resourceRoles, IEnumerable<string> userRoles)
{
    foreach (var userRole in userRoles)
        foreach (var resourceRole in resourceRoles)
            if (resourceRole == userRole)
                return true;
    return false;
}
  

Мы с Resharper придумали это:

 public static bool IsResourceAvailableToUser(IEnumerable<string> resourceRoles, IEnumerable<string> userRoles)
{
    return userRoles.Where(resourceRoles.Contains).Count() > 0;
}
  

Есть ли способ лучше?

Ответ №1:

Учитывая LINQ, да:

 return userRoles.Intersect(resourceRoles).Any();
  

Обратите внимание, что помимо использования Intersect для преобразования его в O (m) O (n) вместо O (m * n), использование Any более эффективно, чем использование Count() > 0 — вы знаете ответ, как только нашли первое совпадение.

Комментарии:

1. Возможно, это неподходящее место для вопроса, но раз уж мы об этом заговорили; где я могу прочитать и узнать о соображениях производительности методов LINQ.

2. Говоря из интереса как человек, не знакомый с C # (я уловил тег «algorithm»), что гарантирует, что это линейно? Конечно, коллекции должны быть отсортированы для этого: не так ли?

3. @Steve: В основном используется набор хэшей — построение набора хэшей из userRoles должно быть сокращено на O (m), а поиск каждого элемента из resourceRoles набора хэшей должен составлять всего O (n).

4. D’oh. Также существуют алгоритмы, не связанные с онлайн 😉 Спасибо.

Ответ №2:

Вы могли бы написать универсальный метод расширения, который обрабатывал бы множество случаев. Основная часть самой функции составляет одну строку.

 /// <summary>
/// Compares both lists to see if any item in the enumerable 
/// equals any item in the other enumerable. 
/// </summary>
public static bool AnyItem<T>(this IEnumerable<T> source, IEnumerable<T> other, IEqualityComparer<T> comparer = null)
{
    return (comparer == null ? source.Intersect(other) : source.Intersect(other, comparer)).Any();
}
  

Более старый, менее эффективный ответ

 public static bool AnyItem<T>(this IEnumerable<T> source, IEnumerable<T> other)
{
    return source.Any(s => other.Any(o => EqualityComparer<T>.Default.Equals(s, o)));
}
  

Я думаю, что это также более эффективно, чем текущий ответ (Это не так). Мне пришлось бы проверить, дорого ли обходится получение EqualityComparer, но я готов в этом усомниться.


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

 public static bool AnyItem<T, TResult>(
        this IEnumerable<T> source, 
        IEnumerable<T> other, 
        Expression<Func<T, TResult>> compareProperty = null)
{
    if (compareProperty == null)
    {
        return source.Any(s => other.Any(o => EqualityComparer<T>.Default.Equals(s, o)));
    }

    return source.Any(s => other.Any(o => 
                    EqualityComparer<TResult>.Default.Equals(
                    s.GetPropertyValue(compareProperty),
                    o.GetPropertyValue(compareProperty))));
}

public static TValue GetPropertyValue<TTarget, TValue>(
    this TTarget target, Expression<Func<TTarget, TValue>> memberLamda)
{
    var memberSelectorExpression = memberLamda.Body as MemberExpression;
    var property = memberSelectorExpression?.Member as PropertyInfo;
    return (TValue)property?.GetValue(target);
}
  

Комментарии:

1. Нет, это значительно менее эффективно, чем мой ответ, по крайней мере, по времени. Это O (a * b) вместо O (a b), где a — количество элементов в source, а b — количество элементов в other. Это O (1) в пространстве, где у меня есть O (n), хотя.

2. @JonSkeet Мне пришлось перепроверить вас, и на самом деле замечательно, насколько лучше Intersect в этом случае, он даже близок в некоторых оптимальных случаях для Any. Я обязательно переработаю ответ, но OP, вероятно, следует отметить ваш принятый ответ