Требования: Необходимо определить тип коллекции только для чтения, который не будет добавлять, удалять и не изменять коллекцию, а только делать запросы к коллекции. Мы надеемсяЧем быстрее запрос, тем лучше。
Распространённые сравнения множеств
При описании сложности алгоритма обычно используются o(1), o(n), o(logn), o(logn), o(logn), o(nlogn) для выражения временной сложности соответствующего алгоритма, который является выражением пространственно-временной сложности алгоритма. Он используется не только для представления временной сложности, но и для представления пространственной сложности.
За O следует функция в скобках, указывающая связь между временем/пространством, используемым алгоритмом, и объёмом обработанных данных. где n — объём входных данных.
Например, если временная сложность равна O(n), это означает, что объём данных увеличивается несколько раз, а расход времени также увеличивается несколько раз. Например, распространённые алгоритмы обхода. Другой пример — временная сложность O(n^2), которая означает, что при увеличении объёма данных в n раз требуется время, чтобы увеличиться в n квадрата, что является более высокой временной сложностью, чем линейность. Например, сортировка пузырьков — это типичный алгоритм O(n^2), который необходимо сканировать n × n раз для сортировки n чисел.
Другой пример — O(logn), когда данные увеличиваются в n раз, требуется время, чтобы увеличить количество времени логна (журнал здесь основан на 2, например, при увеличении данных в 256 раз время увеличивается только в 8 раз, что меньше, чем линейно). Бинарный поиск — это алгоритм O (logn), который исключает половину возможностей каждый раз при обнаружении, а поиск в 256 данных достаточно найти 8 раз, чтобы найти цель.
O(nlogn) — это то же самое, то есть n умножение на logn, при увеличении данных в 256 раз расход времени увеличивается на 256 * 8 = 2048 раз. Эта сложность выше, чем линейность ниже квадрата. Слияние и сортировка — это временная сложность O(nlogn).
O(1) — это наименьшая пространственно-временная сложность, то есть время/пространство не зависит от размера входных данных; сколько бы раз ни увеличивали входные данные, время/пространство остаётся неизменным. Алгоритм хеширования — это типичная временная сложность O(1), которая может найти цель после одного вычисления (независимо от конфликтов), независимо от размера данных.
В этой статье используется пара BenchmarkDotNetList、HashSet、SortedSet、DictionaryЗапрос для бенчмаркинга см. следующее:
Код таков:
Результат теста: найти ключ в словаре или хэш-наборе гораздо быстрее, чем искать в списке и SortedSet. Временная сложность алгоритмов Dictionary и HashSet составляет O(1), и для экономии памяти значение словаря нам не пригодится, поэтому я всё равно выбрал хранилище HashSet.
|
Опубликовано 07.03.2022 16:47:50
|
|
|
|
Опубликовано 07.03.2022 23:09:48
|
Хозяин|
Опубликовано 09.03.2022 9:55:12
|
