HashSet по сравнению с производительностью Списка
Существует определенно способ сделать это - используйте макросы X () . Эти макросы используют препроцессор C для создания перечислений, массивов и кодовых блоков из списка исходных данных. Вам нужно только добавить новые элементы в #define, содержащий макрос X (). Оператор switch будет автоматически расширяться.
Ваш пример можно записать следующим образом:
// Source data -- Enum, String
#define X_NUMBERS \
X(ONE, "one") \
X(TWO, "two") \
X(THREE, "three")
...
// Use preprocessor to create the Enum
typedef enum {
#define X(Enum, String) Enum,
X_NUMBERS
#undef X
} Numbers;
...
// Use Preprocessor to expand data into switch statement cases
switch(num)
{
#define X(Enum, String) \
case Enum: strcpy(num_str, String); break;
X_NUMBERS
#undef X
default: return 0; break;
}
return 1;
Существуют более эффективные способы (например, использование X Макросов для создания строкового массива и индекса перечисления ), но это самая простая демонстрация.
8 ответов
Зависит от большого количества факторов... Реализация списка, архитектура ЦП, JVM, семантика цикла, сложность равняются методу, и т.д. К тому времени, когда список становится достаточно большим для эффективного сравнительного тестирования (1000 + элементы), Основанные на хеше двоичные поиски побеждают линейные поиски без всяких усилий, и различие только увеличивается оттуда.
Hope это помогает!
Одним фактором Ваш не принятие во внимание является устойчивость GetHashcode () функция. С идеальной хеш-функцией HashSet будет ясно иметь лучшее выполнение поиска. Но поскольку хеш-функция уменьшается так будет время поиска HashSet.
Зависит от того, что Вы хешируете. Если Ваши ключи являются целыми числами, Вам, вероятно, не нужны очень много объектов, прежде чем HashSet будет быстрее. При манипулировании его на строке тогда, это будет медленнее, и зависит от входной строки.
, Конечно, Вы могли сделать на скорую руку сравнительный тест довольно легко?
Ответ, как всегда", Он зависит ". Я принимаю от тегов, Вы говорите о C#.
Ваш лучший выбор состоит в том, чтобы определить
- Ряд данных
- требования Использования
и записать некоторые тестовые сценарии.
Это также зависит от того, как Вы сортируете список (если это отсортировано вообще), какие сравнения должны быть сделаны, сколько времени "Сравнить" операция берет для конкретного объекта в списке, или даже как Вы намереваетесь использовать набор.
Обычно лучший для выбора так не основан на размере данных, Вы работаете с, а скорее как Вы намереваетесь получить доступ к нему. У Вас есть каждая часть данных связанной с конкретной строкой или другими данными? Основанный на хеше набор, вероятно, был бы лучшим. Порядок данных, Вы храните важный, или Вы собираетесь должны получить доступ ко всем данным одновременно? Обычный список может быть лучше тогда.
Дополнительный:
, Конечно, мой выше комментариев предполагает, что 'производительность' означает доступ к данным. Что-то еще для рассмотрения: что Вы ищете при высказывании "производительности"? Значение человека производительности, ищут? Это - управление большими (10000, 100000 или больше) наборы значений? Действительно ли это - выполнение заполнения структуры данных с данными? Удаление данных? Доступ к отдельным битам данных? Замена значений? Итерация по значениям? Использование памяти? Скорость при копировании данных? Например, Если Вы получаете доступ к данным строковым значением, но Ваше основное требование к производительности является минимальным использованием памяти, у Вас могли бы быть конфликтующие вопросы проектирования.
Это зависит. Если точный ответ действительно имеет значение, сделайте некоторое профилирование и узнайте. Если Вы уверены, что у Вас никогда не будет больше, чем определенное число элементов в наборе, пойдите со Списком. Если число неограниченно, используйте HashSet.
Использовать ли HashSet<> или List<> сводится , как необходимо получить доступ набору . Если необходимо гарантировать порядок пунктов, используйте Список. Если Вы не делаете, используйте HashSet. Позвольте Microsoft волноваться о реализации их алгоритмов хеширования и объектов.
А HashSet получит доступ к объектам, не имея необходимость перечислять набор (сложность O (1) или около него), и потому что Список гарантирует порядок, в отличие от HashSet, некоторые объекты должны будут быть перечислены (сложность O (n)).
Безызбыточность будет зависеть от стоимости вычисления хеша. Вычисления хеша могут быть тривиальными, или не...:-) всегда существует Система. Наборы. Специализированный. Класс HybridDictionary для помощи Вам не должен волноваться о точке безубыточности.
Вы неправильно смотрите. Да, линейный поиск по списку превзойдет HashSet для небольшого количества элементов. Но для таких небольших коллекций разница в производительности обычно не имеет значения. Обычно вам приходится беспокоиться о больших коллекциях, и именно здесь вы думаете в терминах Big-O . Однако, если вы измерили реальное узкое место в производительности HashSet, вы можете попытаться создать гибридный List / HashSet, но вы сделаете это, проведя множество эмпирических тестов производительности, не задавая вопросов по SO.