Хэш - набор противПроизводительность списка

Question

Понятно, что производительность поиска общего HashSet<T> класс выше, чем у универсального List<T> класс.Просто сравните ключ на основе хэша с линейным подходом в List<T> класс.

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

Мой вопрос:где же безубыточность?

Чтобы упростить сценарий (и быть справедливым), давайте предположим, что List<T> класс использует элемент Equals() способ идентификации элемента.

Answer 1

Многие люди говорят, что как только вы достигнете размера, когда скорость действительно станет проблемой, это HashSet<T> всегда будет бить List<T>, но это зависит от того, что вы делаете.

Допустим, у вас есть List<T> в нем всегда будет в среднем только 5 предметов.В течение большого количества циклов, если в каждом цикле добавляется или удаляется один элемент, вам, возможно, будет лучше использовать List<T>.

Я провел тест для этого на своей машине, и, ну, он должен быть очень-очень маленьким, чтобы получить преимущество от List<T>.Для списка коротких строк преимущество исчезло после размера 5, для объектов после размера 20.

1 item LIST strs time: 617ms
1 item HASHSET strs time: 1332ms

2 item LIST strs time: 781ms
2 item HASHSET strs time: 1354ms

3 item LIST strs time: 950ms
3 item HASHSET strs time: 1405ms

4 item LIST strs time: 1126ms
4 item HASHSET strs time: 1441ms

5 item LIST strs time: 1370ms
5 item HASHSET strs time: 1452ms

6 item LIST strs time: 1481ms
6 item HASHSET strs time: 1418ms

7 item LIST strs time: 1581ms
7 item HASHSET strs time: 1464ms

8 item LIST strs time: 1726ms
8 item HASHSET strs time: 1398ms

9 item LIST strs time: 1901ms
9 item HASHSET strs time: 1433ms

1 item LIST objs time: 614ms
1 item HASHSET objs time: 1993ms

4 item LIST objs time: 837ms
4 item HASHSET objs time: 1914ms

7 item LIST objs time: 1070ms
7 item HASHSET objs time: 1900ms

10 item LIST objs time: 1267ms
10 item HASHSET objs time: 1904ms

13 item LIST objs time: 1494ms
13 item HASHSET objs time: 1893ms

16 item LIST objs time: 1695ms
16 item HASHSET objs time: 1879ms

19 item LIST objs time: 1902ms
19 item HASHSET objs time: 1950ms

22 item LIST objs time: 2136ms
22 item HASHSET objs time: 1893ms

25 item LIST objs time: 2357ms
25 item HASHSET objs time: 1826ms

28 item LIST objs time: 2555ms
28 item HASHSET objs time: 1865ms

31 item LIST objs time: 2755ms
31 item HASHSET objs time: 1963ms

34 item LIST objs time: 3025ms
34 item HASHSET objs time: 1874ms

37 item LIST objs time: 3195ms
37 item HASHSET objs time: 1958ms

40 item LIST objs time: 3401ms
40 item HASHSET objs time: 1855ms

43 item LIST objs time: 3618ms
43 item HASHSET objs time: 1869ms

46 item LIST objs time: 3883ms
46 item HASHSET objs time: 2046ms

49 item LIST objs time: 4218ms
49 item HASHSET objs time: 1873ms

Вот эти данные, отображаемые в виде графика:

Вот код:

static void Main(string[] args)
{
    int times = 10000000;


    for (int listSize = 1; listSize < 10; listSize++)
    {
        List<string> list = new List<string>();
        HashSet<string> hashset = new HashSet<string>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add("string" + i.ToString());
            hashset.Add("string" + i.ToString());
        }

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove("string0");
            list.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");


        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove("string0");
            hashset.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }


    for (int listSize = 1; listSize < 50; listSize+=3)
    {
        List<object> list = new List<object>();
        HashSet<object> hashset = new HashSet<object>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add(new object());
            hashset.Add(new object());
        }

        object objToAddRem = list[0];

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove(objToAddRem);
            list.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");



        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove(objToAddRem);
            hashset.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }

    Console.ReadLine();
}

Answer 2

Ты неправильно смотришь на это.Да, линейный поиск по списку превзойдет хэш-набор для небольшого количества элементов.Но разница в производительности обычно не имеет значения для таких маленьких коллекций.Как правило, вам приходится беспокоиться о больших коллекциях, и именно здесь вы думайте в терминах Big-O.Однако, если вы измерили реальное узкое место в производительности HashSet, то вы можете попытаться создать гибридный список / HashSet, но вы сделаете это, проведя множество эмпирических тестов производительности, не задавая вопросов по SO.

Answer 3

По сути, бессмысленно сравнивать две структуры для Производительность которые ведут себя по-другому.Используйте структуру, которая передает намерение.Даже если ты скажешь свое List<T> не было бы дубликатов, и порядок итераций не имеет значения, что делает его сравнимым с HashSet<T>, это все еще плохой выбор для использования List<T> потому что он относительно менее отказоустойчив.

Тем не менее, я проверю некоторые другие аспекты эффективности,

+------------+--------+-------------+-----------+----------+----------+-----------+
| Collection | Random | Containment | Insertion | Addition |  Removal | Memory    |
|            | access |             |           |          |          |           |
+------------+--------+-------------+-----------+----------+----------+-----------+
| List<T>    | O(1)   | O(n)        | O(n)      | O(1)*    | O(n)     | Lesser    |
| HashSet<T> | O(n)   | O(1)        | n/a       | O(1)     | O(1)     | Greater** |
+------------+--------+-------------+-----------+----------+----------+-----------+

* Even though addition is O(1) in both cases, it will be relatively slower in HashSet<T> since it involves cost of precomputing hash code before storing it.

** The superior scalability of HashSet<T> has a memory cost. Every entry is stored as a new object along with its hash code. This article might give you an idea.

Answer 4

Следует ли использовать HashSet<> или Список<> сводится к как вам нужно получить доступ к вашей коллекции.Если вам нужно гарантировать порядок товаров, используйте Список.Если вы этого не сделаете, используйте HashSet.Пусть Microsoft побеспокоится о реализации своих алгоритмов хеширования и объектов.

Хэш-набор будет получать доступ к элементам без необходимости перечислять коллекцию (сложность O(1) или рядом с ним), и поскольку список гарантирует порядок, в отличие от HashSet, некоторые элементы придется перечислять (сложность O(n)).

Answer 5

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

1. Несколько (12-20) небольших строк (длиной от 5 до 10 символов)
2. Много (~ 10 Тыс.) маленьких строк
3. Несколько длинных строк (длиной от 200 до 1000 символов)
4. Много строк длиной (~ 5 Тыс.)
5. Несколько целых чисел
6. Много (~ 10 Тысяч) целых чисел

И для каждого сценария ищем значения, которые появляются:

1. В начале списка ("начало", индекс 0)
2. Ближе к началу списка ("ранний", индекс 1)
3. В середине списка ("middle", количество индексов /2)
4. Ближе к концу списка ("поздно", количество индексов-2)
5. В конце списка ("конец", количество индексов-1)

Перед каждым сценарием я генерировал списки случайных строк произвольного размера, а затем передавал каждый список в hashset.Каждый сценарий повторялся, по существу, 10 000 раз:

(тестовый псевдокод)

stopwatch.start
for X times
    exists = list.Contains(lookup);
stopwatch.stop

stopwatch.start
for X times
    exists = hashset.Contains(lookup);
stopwatch.stop

Выборочный вывод

Протестировано на Windows 7, 12 ГБ оперативной памяти, 64-разрядная версия, Xeon 2.8 ГГц

---------- Testing few small strings ------------
Sample items: (16 total)
vgnwaloqf diwfpxbv tdcdc grfch icsjwk
...

Benchmarks:
1: hashset: late -- 100.00 % -- [Elapsed: 0.0018398 sec]
2: hashset: middle -- 104.19 % -- [Elapsed: 0.0019169 sec]
3: hashset: end -- 108.21 % -- [Elapsed: 0.0019908 sec]
4: list: early -- 144.62 % -- [Elapsed: 0.0026607 sec]
5: hashset: start -- 174.32 % -- [Elapsed: 0.0032071 sec]
6: list: middle -- 187.72 % -- [Elapsed: 0.0034536 sec]
7: list: late -- 192.66 % -- [Elapsed: 0.0035446 sec]
8: list: end -- 215.42 % -- [Elapsed: 0.0039633 sec]
9: hashset: early -- 217.95 % -- [Elapsed: 0.0040098 sec]
10: list: start -- 576.55 % -- [Elapsed: 0.0106073 sec]


---------- Testing many small strings ------------
Sample items: (10346 total)
dmnowa yshtrxorj vthjk okrxegip vwpoltck
...

Benchmarks:
1: hashset: end -- 100.00 % -- [Elapsed: 0.0017443 sec]
2: hashset: late -- 102.91 % -- [Elapsed: 0.0017951 sec]
3: hashset: middle -- 106.23 % -- [Elapsed: 0.0018529 sec]
4: list: early -- 107.49 % -- [Elapsed: 0.0018749 sec]
5: list: start -- 126.23 % -- [Elapsed: 0.0022018 sec]
6: hashset: early -- 134.11 % -- [Elapsed: 0.0023393 sec]
7: hashset: start -- 372.09 % -- [Elapsed: 0.0064903 sec]
8: list: middle -- 48,593.79 % -- [Elapsed: 0.8476214 sec]
9: list: end -- 99,020.73 % -- [Elapsed: 1.7272186 sec]
10: list: late -- 99,089.36 % -- [Elapsed: 1.7284155 sec]


---------- Testing few long strings ------------
Sample items: (19 total)
hidfymjyjtffcjmlcaoivbylakmqgoiowbgxpyhnrreodxyleehkhsofjqenyrrtlphbcnvdrbqdvji...
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0018266 sec]
2: list: start -- 115.76 % -- [Elapsed: 0.0021144 sec]
3: list: middle -- 143.44 % -- [Elapsed: 0.0026201 sec]
4: list: late -- 190.05 % -- [Elapsed: 0.0034715 sec]
5: list: end -- 193.78 % -- [Elapsed: 0.0035395 sec]
6: hashset: early -- 215.00 % -- [Elapsed: 0.0039271 sec]
7: hashset: end -- 248.47 % -- [Elapsed: 0.0045386 sec]
8: hashset: start -- 298.04 % -- [Elapsed: 0.005444 sec]
9: hashset: middle -- 325.63 % -- [Elapsed: 0.005948 sec]
10: hashset: late -- 431.62 % -- [Elapsed: 0.0078839 sec]


---------- Testing many long strings ------------
Sample items: (5000 total)
yrpjccgxjbketcpmnvyqvghhlnjblhgimybdygumtijtrwaromwrajlsjhxoselbucqualmhbmwnvnpnm
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: list: start -- 132.73 % -- [Elapsed: 0.0021517 sec]
3: hashset: start -- 231.26 % -- [Elapsed: 0.003749 sec]
4: hashset: end -- 368.74 % -- [Elapsed: 0.0059776 sec]
5: hashset: middle -- 385.50 % -- [Elapsed: 0.0062493 sec]
6: hashset: late -- 406.23 % -- [Elapsed: 0.0065854 sec]
7: hashset: early -- 421.34 % -- [Elapsed: 0.0068304 sec]
8: list: middle -- 18,619.12 % -- [Elapsed: 0.3018345 sec]
9: list: end -- 40,942.82 % -- [Elapsed: 0.663724 sec]
10: list: late -- 41,188.19 % -- [Elapsed: 0.6677017 sec]


---------- Testing few ints ------------
Sample items: (16 total)
7266092 60668895 159021363 216428460 28007724
...

Benchmarks:
1: hashset: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: hashset: end -- 100.45 % -- [Elapsed: 0.0016284 sec]
3: list: early -- 101.83 % -- [Elapsed: 0.0016507 sec]
4: hashset: late -- 108.95 % -- [Elapsed: 0.0017662 sec]
5: hashset: middle -- 112.29 % -- [Elapsed: 0.0018204 sec]
6: hashset: start -- 120.33 % -- [Elapsed: 0.0019506 sec]
7: list: late -- 134.45 % -- [Elapsed: 0.0021795 sec]
8: list: start -- 136.43 % -- [Elapsed: 0.0022117 sec]
9: list: end -- 169.77 % -- [Elapsed: 0.0027522 sec]
10: list: middle -- 237.94 % -- [Elapsed: 0.0038573 sec]


---------- Testing many ints ------------
Sample items: (10357 total)
370826556 569127161 101235820 792075135 270823009
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0015132 sec]
2: hashset: end -- 101.79 % -- [Elapsed: 0.0015403 sec]
3: hashset: early -- 102.08 % -- [Elapsed: 0.0015446 sec]
4: hashset: middle -- 103.21 % -- [Elapsed: 0.0015618 sec]
5: hashset: late -- 104.26 % -- [Elapsed: 0.0015776 sec]
6: list: start -- 126.78 % -- [Elapsed: 0.0019184 sec]
7: hashset: start -- 130.91 % -- [Elapsed: 0.0019809 sec]
8: list: middle -- 16,497.89 % -- [Elapsed: 0.2496461 sec]
9: list: end -- 32,715.52 % -- [Elapsed: 0.4950512 sec]
10: list: late -- 33,698.87 % -- [Elapsed: 0.5099313 sec]

Answer 6

Безубыточность будет зависеть от стоимости вычисления хэша.Вычисления хэша могут быть как тривиальными, так и нет...:-) Всегда есть Система.Коллекции.Специализированный.Класс HybridDictionary, который поможет вам не беспокоиться о точке безубыточности.

Answer 7

Ответ, как всегда, таков: "Это зависит".Я предполагаю, судя по тегам, что вы говорите о C #.

Ваш лучший выбор - определить

1. Набор данных
2. Требования к использованию

и напишите несколько тестовых примеров.

Это также зависит от того, как вы сортируете список (если он вообще отсортирован), какие сравнения необходимо выполнить, сколько времени занимает операция "Сравнить" для конкретного объекта в списке или даже от того, как вы собираетесь использовать коллекцию.

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

Дополнительный:

Конечно, в моих приведенных выше комментариях предполагается, что "производительность" означает доступ к данным.Есть еще кое-что, о чем стоит подумать:на что вы обращаете внимание, когда говорите "производительность"?Повышается ли индивидуальная ценность производительности?Является ли это управлением большими (10000, 100000 или более) наборами значений?Является ли это производительностью заполнения структуры данных данными?Удаление данных?Доступ к отдельным битам данных?Замена значений?Перебираете значения?Использование памяти?Скорость копирования данных?Например, если вы обращаетесь к данным с помощью строкового значения, но вашим основным требованием к производительности является минимальное использование памяти, у вас могут возникнуть конфликтующие проблемы с дизайном.

Answer 8

Вы можете использовать HybridDictionary, который автоматически определяет точку прерывания и принимает нулевые значения, что делает его по существу таким же, как HashSet.

Answer 9

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

Answer 10

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

Конечно, вы могли бы довольно легко создать бенчмарк?

Answer 11

Одним из факторов, который вы не принимаете во внимание, является надежность функции GetHashCode().При идеальной хэш-функции HashSet явно будет иметь лучшую производительность поиска.Но по мере уменьшения хэш-функции уменьшается и время поиска по хэш-набору.

Answer 12

Зависит от множества факторов...Реализация списка, архитектура процессора, JVM, семантика цикла, сложность метода equals и т.д...К тому времени, когда список становится достаточно большим для эффективного бенчмарка (более 1000 элементов), бинарный поиск на основе хэша превосходит линейный поиск практически без изменений, и с этого момента разница только увеличивается.

Надеюсь, это поможет!