Список <T>.Contains () является очень медленным?

Мог любой объяснять меня почему дженерики List.Contains() функция является настолько медленной?

У меня есть a List<long> приблизительно с миллионом чисел и кодом, который постоянно проверяет, существует ли определенное число в этих числах.

Я пытался делать использование того же самого Dictionary<long, byte> и Dictionary.ContainsKey() функция, и это было приблизительно в 10-20 раз быстрее, чем со Списком.

Конечно, я действительно не хочу использовать Словарь с этой целью, потому что он не был предназначен, чтобы использоваться тот путь.

Так, реальный вопрос здесь, там любая альтернатива List<T>.Contains(), но не столь эксцентричный как Dictionary<K,V>.ContainsKey() ?

82
задан ASh 9 October 2019 в 12:49
поделиться

6 ответов

Если вы просто проверяете наличие, HashSet в .NET 3.5 - ваш лучший вариант - производительность, подобная словарю, но без пары ключ / значение - просто значения:

    HashSet<int> data = new HashSet<int>();
    for (int i = 0; i < 1000000; i++)
    {
        data.Add(rand.Next(50000000));
    }
    bool contains = data.Contains(1234567); // etc
149
ответ дан 24 November 2019 в 09:09
поделиться

A SortedList будет быстрее искать (но медленнее вставлять элементы)

2
ответ дан 24 November 2019 в 09:09
поделиться

List.Contains - операция O (n).

Dictionary.ContainsKey - операция O (1), поскольку она использует хеш-код объектов в качестве ключа, который дает вам более быстрая возможность поиска.

Я не думаю, что было бы хорошо иметь список, содержащий миллион записей. Я не думаю, что класс List был разработан для этой цели. :)

Разве нельзя сохранить эти миллионные сущности, например, в RDBMS и выполнить запросы к этой базе данных?

Если это невозможно, тогда я все равно буду использовать словарь.

28
ответ дан 24 November 2019 в 09:09
поделиться

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

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

Я думаю, что есть также HashSet класс в .NET 3.5, он также допускает только уникальные элементы.

5
ответ дан 24 November 2019 в 09:09
поделиться

Почему словарь не подходит?

Чтобы увидеть, есть ли конкретное значение в списке, вам нужно пройти по всему списку. С помощью словаря (или другого контейнера, основанного на хэше) гораздо быстрее сузить количество объектов, с которыми нужно сравнивать. Ключ (в вашем случае число) хэшируется, и это дает словарю дробное подмножество объектов для сравнения.

1
ответ дан 24 November 2019 в 09:09
поделиться

Я использую это в Compact Framework, где нет поддержки HashSet, я выбрал словарь, в котором обе строки представляют собой значение, которое я ищу.

Это означает, что я получить список <> функциональность с производительностью словаря. Это немного взломано, но работает.

0
ответ дан 24 November 2019 в 09:09
поделиться
Другие вопросы по тегам:

Похожие вопросы: