Быстрый способ проверить, не содержит ли IEnumerable <T> дубликатов (= отлично)

Есть ли быстрый встроенный способ проверить, содержит ли IEnumerable<string> только отдельные строки?

В начале я начал с:

var enumAsArray = enum.ToArray();
if (enumAsArray.Length != enumAsArray.Distinct().Count())
    throw ...

Однако, похоже, что это O (2n) - не так ли? ToArray() может быть O (1)?

Это выглядит быстрее:

var set = new HashSet<string>();
foreach (var str in enum)
{
    if (!set.Add(str))
        throw ...
}

Это должно быть O (n), однако есть ли встроенный способ?

Изменить: Может быть, Distinct() использует это внутри?

Решение: Рассмотрев все комментарии и ответ, я написал метод расширения для моего второго решения, поскольку это, по-видимому, самая быстрая версия и наиболее читаемая:

public static bool ContainsDuplicates<T>(this IEnumerable<T> e)
{
    var set = new HashSet<T>();
    // ReSharper disable LoopCanBeConvertedToQuery
    foreach (var item in e)
    // ReSharper restore LoopCanBeConvertedToQuery
    {
        if (!set.Add(item))
            return true;
    }
    return false;
}

Ответы

Ответ 1

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

Если ваше использование этого конкретного решения не вызовет проблемы с производительностью после того, как вы заметили проблемы и проверили тестирование производительности, я оставил бы это как есть. Учитывая, как мало места я вижу для улучшения в целом, это не кажется вероятным. Это не достаточно длительное или сложное решение, которое пытается найти что-то "короче" или более кратким, будет стоить вашего времени и усилий.

Короче говоря, в вашем коде есть почти наверняка лучшие места, чтобы тратить свое время; что у вас уже хорошо.

Чтобы ответить на ваши конкретные вопросы:

  • Однако, похоже, что это O (2n) - это?

    Да, это так.

  • ToArray() может быть O (1)?

    Нет, это не так.

  • Может быть, Distinct() использует это внутренне?

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

  • Есть ли встроенный способ?

    Хорошо, вы показали один, это не так эффективно. Я не думаю, что ни одно решение на основе LINQ не будет эффективным, как то, что вы показали. Лучшее, о чем я могу думать, будет: data.Except(data).Any(). Это немного лучше, чем ваше отличие по сравнению с обычным счетчиком, поскольку вторая итерация может быть короткой (но не первой), но она также повторяет последовательность дважды и все еще хуже, чем ваше решение, отличное от LINQ, поэтому оно все еще не стоит использовать.

Ответ 2

Вот возможная доработка ответа OP:

public static IEnumerable<T> Duplicates<T>(this IEnumerable<T> e)
{
    var set = new HashSet<T>();
    // ReSharper disable LoopCanBeConvertedToQuery
    foreach (var item in e)
    // ReSharper restore LoopCanBeConvertedToQuery
    {
        if (!set.Add(item))
            yield return item;
    }
}

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

collection.Duplicates().Any()

Ответ 3

Просто дополнение к существующему решению:

public static bool ContainsDuplicates<T>(this IEnumerable<T> items)
{
    return ContainsDuplicates(items, EqualityComparer<T>.Default);
}

public static bool ContainsDuplicates<T>(this IEnumerable<T> items, IEqualityComparer<T> equalityComparer)
{
    var set = new HashSet<T>(equalityComparer);

    foreach (var item in items)
    {
        if (!set.Add(item))
            return true;
    }

    return false;
}

Эта версия позволяет выбрать сопоставитель равенства, это может оказаться полезным, если вы хотите сравнивать элементы на основе правил, отличных от стандартного.

Например, чтобы сравнить набор строк без учета регистра, просто передайте его StringComparer.OrdinalIgnoreCase.