Как быстро определить что коллекция содержит только уникальные значения. Спасибо.

Здравствуйте, Аноним, Вы писали:
А>Как быстро определить что коллекция содержит только уникальные значения. Спасибо.

var input = Enumerable.Range(1, 1000);
var hs = new HashSet<int>();
var uniqueElementsOnly = input.All(hs.Add);

Здравствуйте, Аноним, Вы писали:

А>Как быстро определить что коллекция содержит только уникальные значения. Спасибо.

Первое что пришло в голову (возможно не самое оптимальное)

bool uniqueOnly = collection.Count() == collection.Distinct().Count();

collection.GroupBy(e => e).Any(eg => eg.Count() > 0)

Есть шанс, что при первом же найденном дубликате вычисления остановятся

Здравствуйте, igor-booch, Вы писали:

IB>Есть шанс, что при первом же найденном дубликате вычисления остановятся
А по моим субъективным ощущениям, GroupBy() довольно тормозной.

Здравствуйте, igor-booch, Вы писали:

IB>Есть шанс, что при первом же найденном дубликате вычисления остановятся
Есть шанс, что остановится даже без дубликатов (сравнивать надо с 1, не с 0).

Минимальная стоимость будет точно не меньше, чем у QrystaL, GroupBy в любом случае пройдёт по коллекции как минимум 1 раз, у QrystaL проход прервётся при первой неудаче.

S>Минимальная стоимость будет точно не меньше, чем у QrystaL, GroupBy в любом случае пройдёт по коллекции как минимум 1 раз, у QrystaL проход прервётся при первой неудаче.

Да, к сожалению, ленивость не сработала, проверил:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GroupByAnyCount
{
    class Program
    {
        static void Main(string[] args)
        {
            ValueContainer[] array = new ValueContainer[]
            {
                new ValueContainer{Value = 1},
                new ValueContainer{Value = 2},
                new ValueContainer{Value = 3},
                new ValueContainer{Value = 4},
                new ValueContainer{Value = 3},
                new ValueContainer{Value = 5},
                new ValueContainer{Value = 6},
                new ValueContainer{Value = 7}
            };

            array.GroupBy(vc => vc.Value).Any(vcg => vcg.Count() > 1);

            Console.ReadLine();
        }
    }

    class ValueContainer
    {
        private int _value;
        public int Value
        {
            get
            {
                Console.WriteLine("Access to ValueContainer.Value = {0}", _value);
                return this._value;
            }
            set { this._value = value; }
        }
    }
}

Access to ValueContainer.Value = 1
Access to ValueContainer.Value = 2
Access to ValueContainer.Value = 3
Access to ValueContainer.Value = 4
Access to ValueContainer.Value = 3
Access to ValueContainer.Value = 5
Access to ValueContainer.Value = 6
Access to ValueContainer.Value = 7

Проход не остановился на второй тройке.

А почему как минимум 1 раз? Зачем ему больше одного раза проходить?

Здравствуйте, igor-booch, Вы писали:

IB>А почему как минимум 1 раз? Зачем ему больше одного раза проходить?

1 раз — это сам вызов GroupBy, он внутри заполняет лукап (упрощённо — аналог Dictionary<TKey, List<TElement>>):

// System.Linq.Lookup<TKey, TElement>
internal static Lookup<TKey, TElement> Create<TSource>(IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer)
{
    ...
    Lookup<TKey, TElement> lookup = new Lookup<TKey, TElement>(comparer);
    foreach (TSource current in source)
    {
        lookup.GetGrouping(keySelector(current), true).Add(elementSelector(current));
    }
    return lookup;
}

2 раз — Any(). В худшем случае — полный перебор всех значений лукапа.

S>2 раз — Any(). В худшем случае — полный перебор всех значений лукапа.

Any разве по коллекции будет ходит?
По моему нет.
По коллекции ходит GroupBy.
Any ходит по System.Linq.Lookup<int, ValueContainer>.Grouping
Этот класс реализует IList<TElement>.
поэтому vcg.Count() сразу возьмет значение свойства Count и не будет походить по коллекции
Это так же подтверждают результаты теста

Автор: igor-booch
Дата: 20.06.13

.

Здравствуйте, Аноним, Вы писали:

А>Как быстро определить что коллекция содержит только уникальные значения. Спасибо.

Из любопытства на скорую руку сравнил три описанных выше метода.
Первые два сопоставимы по памяти и скорости. Последний — в 10 раз медленнее и использует в 10 раз больше памяти.

Вот как-то так.

Код:

class Program
    {
        static void Main()
        {
            var collection = new uint[1000000];

            for (uint i = 0; i < collection.Length; i++)
                collection[i] = i;

            collection[collection.Length - 1] = 1; // duplicate

            Console.WriteLine("Collection ready.\n");

            Console.WriteLine("collection.All(hs.Add);");
            Test(collection, c => {
                var hs = new HashSet<uint>();
                return c.All(hs.Add);
            });

            Console.WriteLine("collection.Count() == collection.Distinct().Count();");
            Test(collection, c => c.Count() == c.Distinct().Count());

            Console.WriteLine("collection.GroupBy(e => e).Any(eg => eg.Count() > 1);");
            Test(collection, c => !c.GroupBy(e => e).Any(eg => eg.Count() > 1));

            Console.WriteLine("Press any key...");
            Console.ReadKey(true);
        }

        private static void Test(uint[] collection, Func<uint[], bool> func)
        {
            var time = new List<Int64>();
            bool isUnique = false;
            var sw = new Stopwatch();

            for (var i = 0; i < 5; i++) {
                sw.Restart();
                isUnique = func(collection);
                time.Add(sw.ElapsedMilliseconds);
            }

            Console.WriteLine("Is unique: {0}. Time: {1}\n", isUnique, time.Average());
        }
    }

Интересно было бы сравнить что-то вот такое:

collection[50] = 1; // duplicate

Т.е. дубликат ближе к началу списка.

Doc>Первые два сопоставимы по памяти и скорости.

Первый способ самый предпочтительный, так как дубликат с одинаковой вероятностью может находиться в любом месте коллекции, а не только в конце, как в тесте.

Здравствуйте, igor-booch, Вы писали:

Doc>>Первые два сопоставимы по памяти и скорости.

IB>Первый способ самый предпочтительный, так как дубликат с одинаковой вероятностью может находиться в любом месте коллекции, а не только в конце, как в тесте.

А ведь верно. У второго время будет константа, т.к. от места положения Count() не зависит.

Здравствуйте, Qodomoc, Вы писали:

Q>Т.е. дубликат ближе к началу списка.
Тогда первый вариант всех рвёт, как и должно быть.

Collection ready.

collection.All(hs.Add);
Is unique: False. Time: 2

collection.Count() == collection.Distinct().Count();
Is unique: False. Time: 39,8

collection.GroupBy(e => e).Any(eg => eg.Count() > 1);
Is unique: False. Time: 279,4

Здравствуйте, Аноним, Вы писали:

А>Как быстро определить что коллекция содержит только уникальные значения. Спасибо.

1. Сортировка и проверка равенства соседних элементов.
2. Незначительная оптимизация. Перегружаем оператор сравнения, при равенстве сортировка прерывается. Правильность зависит от реализации сортировки, элемент не должен сравниваться сам с собой.

O(NlogN)