Уникальные значения HashSet vs Distinct

205

04 января 2019, 13:50

Замер скоростей поиска уникальных значений показал разницу в 2 раза

HashSet (9976672): 1179

Distinct(9976672): 2159

//Заполняем коллекцию
var l = new List<int>();
var rand = new Random();
for (int i = 0; i <= 10000000; ++i)
    l.Add(rand.Next());
//Дублируем несколько значений в исходной коллекции
for (int i = 0; i <= 100; ++i)
    l.Add(l.ElementAt(rand.Next(l.Count-1)));
var sw = new System.Diagnostics.Stopwatch();
//Замеряем скорость с HashSet
sw.Restart();
var list1 = (new HashSet<int>(l)).ToList();
sw.Stop();
Console.WriteLine($"HashSet ({list1.Count}): {sw.ElapsedMilliseconds}");
//Замеряем скорость с Distinct
sw.Restart();
var list2 = l.Distinct().ToList();
sw.Stop();
Console.WriteLine($"Distinct({list2.Count}): {sw.ElapsedMilliseconds}");

Выходит, что дистинктом пользоваться плохо?

Answer 1

Ваше тестирование некорректно и в нем есть несколько проблем:

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

Методы Linq же действуют лениво и берут из входной коллекции всегда по одному элементу. Соответственно, хештаблица, которая фактически создается внутри Distinct, просто не готова заранее к таким входным объемам и ей приходится периодически расширяться во время работы, но, с другой стороны, она и не должна быть готова к большим объемам, т. к. вы вполне можете написать .Distinct().Take(10) и усилия на выделение лишнего места будут потрачены впустую.

Во-вторых, в вашем коде аналогичная проблема с .ToList(), в первом случае вы вызываете его на экземпляре ICollection, во втором — на экземпляре IEnumerable.

Итого, если переписать ваш код так:

...
var list1 = (new HashSet<int>(l.Enumerate())).ToList(10000000);
...
var list2 = l.Enumerate().Distinct().ToList(10000000);
...

где:

static class Extensions
{
    public static IEnumerable<TSource> Enumerate<TSource>(this IEnumerable<TSource> source)
    {
        foreach (var item in source)
            yield return item;
    }
    public static List<TSource> ToList<TSource>(this IEnumerable<TSource> source, int capacity)
    {
        var list = new List<TSource>(capacity);
        list.AddRange(source);
        return list;
    }
}