#.net #performance #collections #parallel-processing
#.net #Производительность #Коллекции #параллельная обработка
Вопрос:
Допустим, у нас есть большой список элементов (int, string), доступный только для чтения.
Какой самый быстрый способ получить элемент из этого списка?
Я знаю, что общий словарь работает быстро, но, насколько я знаю, он использует только 1 процессор, а современные компьютеры имеют как минимум 2 процессора.
В качестве дополнительного вопроса: какое было бы самым быстрым решением для поиска в этой коллекции нескольких элементов? Например, коллекция.GetItems(new int[]{1,2,3,4}), где 1,2,3,4 — это ключи.
Спасибо!
Ответ №1:
Словарь использует хэш-таблицы, которые должны быть уменьшены до O (1). Вычисление хэша для ключей должно быть очень быстрым, а поиск хэша — это прямое смещение памяти массива и, надеюсь, очень короткая цепочка столкновений.
Поэтому я бы не рекомендовал оптимизировать поиск, если словарь не удовлетворяет вашим потребностям, и он слишком медленный. Вы можете возразить, что там находится процессор, который тратится впустую, но попытка использовать этот процессор для оптимизации проблемы, которой может и не быть, усложнит ваш код.
Я бы рекомендовал поддерживать словарь поиска и для каждого поиска.
Единственное соображение — это память. Словарь добавит объем памяти, чтобы ускорить поиск — типичное соотношение пространства и времени.
Если вам нужно экономить память, и вам нужен более быстрый поиск, и у вас больше вычислительной мощности (многоядерный), тогда, возможно.
В этом случае я бы рекомендовал вам заглянуть в библиотеку параллельных задач. Вот статья: http://www.codeproject.com/KB/cs/TPL1.aspx
Комментарии:
1. Я согласен с вашим ответом. Кажется, я забыл, как работают хэш-таблицы. Вопрос по-прежнему актуален для всего, что не может сгенерировать хороший хэш-код. Использование методов параллельного расширения будет работать, но я ожидаю увидеть реализацию BCL.
2. Существует словарь BCL — Dictionary<T>
3. Если я правильно понял, хеш-таблица так же хороша, как и используемая функция хеширования. Для моего примера было бы достаточно словаря. Если не использовать хорошую функцию хеширования, поиск путем сравнения с использованием только 1 процессора может оказаться неэффективным.
4. Это может быть измерено, но только усложняет алгоритм и делает его параллельным, когда это не так. Я сомневаюсь в этом. Кроме того, время обычно не тратится на функцию хэширования, оно обычно тратится на большее количество столкновений, чем ожидалось, и на прохождение цепочки.