Список <T>.Contains () является очень медленным?
Мог любой объяснять меня почему дженерики List.Contains() функция является настолько медленной?
У меня есть a List<long> приблизительно с миллионом чисел и кодом, который постоянно проверяет, существует ли определенное число в этих числах.
Я пытался делать использование того же самого Dictionary<long, byte> и Dictionary.ContainsKey() функция, и это было приблизительно в 10-20 раз быстрее, чем со Списком.
Конечно, я действительно не хочу использовать Словарь с этой целью, потому что он не был предназначен, чтобы использоваться тот путь.
Так, реальный вопрос здесь, там любая альтернатива List<T>.Contains(), но не столь эксцентричный как Dictionary<K,V>.ContainsKey() ?
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
A SortedList будет быстрее искать (но медленнее вставлять элементы)
List.Contains - операция O (n).
Dictionary.ContainsKey - операция O (1), поскольку она использует хеш-код объектов в качестве ключа, который дает вам более быстрая возможность поиска.
Я не думаю, что было бы хорошо иметь список, содержащий миллион записей. Я не думаю, что класс List был разработан для этой цели. :)
Разве нельзя сохранить эти миллионные сущности, например, в RDBMS и выполнить запросы к этой базе данных?
Если это невозможно, тогда я все равно буду использовать словарь.
Словарь не так уж и плох, потому что ключи в словаре предназначены для быстрого поиска. Чтобы найти число в списке, нужно перебрать весь список.
Конечно, словарь работает только в том случае, если ваши числа уникальны и не упорядочены.
Я думаю, что есть также HashSet класс в .NET 3.5, он также допускает только уникальные элементы.
Почему словарь не подходит?
Чтобы увидеть, есть ли конкретное значение в списке, вам нужно пройти по всему списку. С помощью словаря (или другого контейнера, основанного на хэше) гораздо быстрее сузить количество объектов, с которыми нужно сравнивать. Ключ (в вашем случае число) хэшируется, и это дает словарю дробное подмножество объектов для сравнения.
Я использую это в Compact Framework, где нет поддержки HashSet, я выбрал словарь, в котором обе строки представляют собой значение, которое я ищу.
Это означает, что я получить список <> функциональность с производительностью словаря. Это немного взломано, но работает.