Re: Linq проверка уникальности всех значений
От: QrystaL Украина  
Дата: 19.06.13 18:03
Оценка: 12 (2) +3
Здравствуйте, Аноним, Вы писали:
А>Как быстро определить что коллекция содержит только уникальные значения. Спасибо.

var input = Enumerable.Range(1, 1000);
var hs = new HashSet<int>();
var uniqueElementsOnly = input.All(hs.Add);
Re: Linq проверка уникальности всех значений
От: Doc Россия http://andrey.moveax.ru
Дата: 20.06.13 08:54
Оценка: 12 (2)
Здравствуйте, Аноним, Вы писали:

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


Из любопытства на скорую руку сравнил три описанных выше метода.
Первые два сопоставимы по памяти и скорости. Последний — в 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());
        }
    }
Re[2]: Первый способ самый лучший
От: igor-booch Россия  
Дата: 20.06.13 09:36
Оценка: +2
Doc>Первые два сопоставимы по памяти и скорости.

Первый способ самый предпочтительный, так как дубликат с одинаковой вероятностью может находиться в любом месте коллекции, а не только в конце, как в тесте.
Отвечайте на это сообщение, только если у Вас хорошее настроение и в Вашем ответе планируются только конструктивные вопросы и замечания
http://rsdn.ru/Info/rules.xml
Re[3]: collection.GroupBy(e => e).Any(eg => eg.Count() > 0)
От: Sinix  
Дата: 20.06.13 07:21
Оценка: +1
Здравствуйте, igor-booch, Вы писали:

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

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

Минимальная стоимость будет точно не меньше, чем у QrystaL, GroupBy в любом случае пройдёт по коллекции как минимум 1 раз, у QrystaL проход прервётся при первой неудаче.
Re[6]: collection.GroupBy(e => e).Any(eg => eg.Count() > 0)
От: igor-booch Россия  
Дата: 20.06.13 08:06
Оценка: +1
S>2 раз — Any(). В худшем случае — полный перебор всех значений лукапа.

Any разве по коллекции будет ходит?
По моему нет.
По коллекции ходит GroupBy.
Any ходит по System.Linq.Lookup<int, ValueContainer>.Grouping
Этот класс реализует IList<TElement>.
поэтому vcg.Count() сразу возьмет значение свойства Count и не будет походить по коллекции
Это так же подтверждают результаты теста
Автор: igor-booch
Дата: 20.06.13
.
Отвечайте на это сообщение, только если у Вас хорошее настроение и в Вашем ответе планируются только конструктивные вопросы и замечания
http://rsdn.ru/Info/rules.xml
Linq проверка уникальности всех значений
От: Аноним  
Дата: 19.06.13 17:35
Оценка:
Как быстро определить что коллекция содержит только уникальные значения. Спасибо.
Re: Linq проверка уникальности всех значений
От: Doc Россия http://andrey.moveax.ru
Дата: 20.06.13 01:09
Оценка:
Здравствуйте, Аноним, Вы писали:

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


Первое что пришло в голову (возможно не самое оптимальное)
bool uniqueOnly = collection.Count() == collection.Distinct().Count();
Re: collection.GroupBy(e => e).Any(eg => eg.Count() > 0)
От: igor-booch Россия  
Дата: 20.06.13 06:48
Оценка:
collection.GroupBy(e => e).Any(eg => eg.Count() > 0)
Отвечайте на это сообщение, только если у Вас хорошее настроение и в Вашем ответе планируются только конструктивные вопросы и замечания
http://rsdn.ru/Info/rules.xml
Re[2]: collection.GroupBy(e => e).Any(eg => eg.Count() > 0)
От: igor-booch Россия  
Дата: 20.06.13 06:53
Оценка:
Есть шанс, что при первом же найденном дубликате вычисления остановятся
Отвечайте на это сообщение, только если у Вас хорошее настроение и в Вашем ответе планируются только конструктивные вопросы и замечания
http://rsdn.ru/Info/rules.xml
Re[3]: collection.GroupBy(e => e).Any(eg => eg.Count() > 0)
От: Mihas  
Дата: 20.06.13 07:05
Оценка:
Здравствуйте, igor-booch, Вы писали:

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

А по моим субъективным ощущениям, GroupBy() довольно тормозной.
Re[4]: collection.GroupBy(e => e).Any(eg => eg.Count() > 0)
От: igor-booch Россия  
Дата: 20.06.13 07:32
Оценка:
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 раз? Зачем ему больше одного раза проходить?
Отвечайте на это сообщение, только если у Вас хорошее настроение и в Вашем ответе планируются только конструктивные вопросы и замечания
http://rsdn.ru/Info/rules.xml
Re[5]: collection.GroupBy(e => e).Any(eg => eg.Count() > 0)
От: Sinix  
Дата: 20.06.13 07:44
Оценка:
Здравствуйте, 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(). В худшем случае — полный перебор всех значений лукапа.
Re[2]: Linq проверка уникальности всех значений
От: Qodomoc Россия  
Дата: 20.06.13 09:29
Оценка:
Интересно было бы сравнить что-то вот такое:

collection[50] = 1; // duplicate


Т.е. дубликат ближе к началу списка.
Re[3]: Первый способ самый лучший
От: Doc Россия http://andrey.moveax.ru
Дата: 20.06.13 10:11
Оценка:
Здравствуйте, igor-booch, Вы писали:

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


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


А ведь верно. У второго время будет константа, т.к. от места положения Count() не зависит.
Re[3]: Linq проверка уникальности всех значений
От: fddima  
Дата: 20.06.13 11:08
Оценка:
Здравствуйте, 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
Re: Linq проверка уникальности всех значений
От: Аноним  
Дата: 20.06.13 12:11
Оценка:
Здравствуйте, Аноним, Вы писали:

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


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

O(NlogN)
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.