Оптимизация Поисков: поиски ключа Словаря по сравнению с поисками Индекса массива
Операция выбора используется для выбора поднабора кортежей из отношения, которое удовлетворяет условию выбора. Она отфильтровывает те кортежи, которые удовлетворяют условию. Операция выбора может быть визуализирована как горизонтальное разбиение на два набора кортежей - те кортежи, которые удовлетворяют условию выбрано, и эти кортежи не выбирают условие, отбрасываемое Сигма (R). Операция проецирования используется для выбора атрибута из отношения, которое удовлетворяет условию выбора. Он отфильтровывает только те кортежи, которые удовлетворяют условию. Операция проецирования может быть визуализирована как вертикальное разбиение на две части - если удовлетворены условия, выбраны другие отброшенные attribute (R) список атрибутов - это номер атрибута
7 ответов
Не забывайте, что нотация Big-O говорит только о том, как сложность возрастает по сравнению с размером (и т. д.) - это не дает никаких указаний на задействованные постоянные факторы. Поэтому иногда даже линейный поиск ключей быстрее, чем поиск по словарю, когда ключей достаточно. В этом случае вы даже не выполняете поиск по массиву - просто операция индексации.
Для прямого поиска по индексу массивы в основном идеальны - это просто случай
pointer_into_array = base_pointer + offset * size
(А затем разыменование указателя. )
Выполнение поиска по словарю относительно сложно - очень быстро по сравнению (скажем) с линейным поиском по ключу, когда ключей много, но намного сложнее, чем прямой поиск по массиву. Он должен вычислить хэш ключа, затем определить, в каком сегменте он должен находиться, возможно, иметь дело с повторяющимися хэшами (или повторяющимися сегментами), а затем проверить равенство.
Как всегда, выберите правильную структуру данных для задания - и если вы действительно можете обойтись простым индексированием в массив (или List ), тогда да, это будет невероятно быстро.
Ожидается ли такое поведение (снижение производительности в 8 раз)?
Почему нет? Каждый поиск в массиве почти незаметен / незначителен, тогда как для поиска по словарю может потребоваться как минимум дополнительный вызов подпрограммы.
Смысл того, что оба они имеют значение O (1), означает, что даже если у вас в 50 раз больше элементов в каждой коллекции, снижение производительности по-прежнему является лишь одним из факторов (8).
Что-то может занять тысячелетие, но по-прежнему быть O (1).
Если вы выполните пошаговое выполнение этого кода в окне дизассемблирования, вы быстро поймете, в чем разница .
Словарные структуры наиболее полезны, когда пространство ключей очень велико и не может быть отображено в стабильный, упорядоченный порядок. Если вы можете преобразовать свои ключи в простое целое число в относительно небольшом диапазоне, вам будет сложно найти структуру данных, которая будет работать лучше, чем массив.
Замечания по реализации; в .NET словари, по сути, являются хешируемыми. Вы можете несколько улучшить их эффективность поиска ключей, обеспечив хэширование ключей в большом пространстве уникальных значений. Похоже, что в вашем случае вы используете простое целое число в качестве ключа (который, я считаю, хеширует его собственное значение) - так что это лучшее, что вы можете сделать.
Поиск в массиве - это самое быстрое из того, что вы можете сделать - по сути, все, что вы можете сделать, это всего лишь один бит арифметики указателя, чтобы перейти от начала массива к элементу, который вы хотите найти. С другой стороны, поиск в словаре, вероятно, будет несколько медленнее, так как он должен выполнять хеширование и заботиться о поиске правильного сегмента. Хотя ожидаемое время выполнения также составляет O (1), алгоритмические константы больше, поэтому он будет медленнее.
Добро пожаловать в нотацию Big-O. Вы всегда должны учитывать, что здесь присутствует постоянный фактор.
Выполнение одного Dict-Lookup, конечно, намного дороже, чем поиск в массиве.
Big-O только говорит вам, как масштабируются алгоритмы. Удвойте количество поисков и посмотрите, как меняются числа: оба должны занять примерно в два раза больше времени.
Стоимость извлечения элемента из словаря составляет O (1) , но это потому, что словарь реализован как хэш-таблица, поэтому вам нужно сначала вычислить хеш значение, чтобы знать, какой элемент вернуть. Хеш-таблицы часто не так эффективны, но они хороши для больших наборов данных или наборов данных, которые имеют много уникальных хеш-значений.
Список (кроме того, что это бессмысленное слово, используемое для описания массива, а не связного списка! ) будет быстрее, поскольку он вернет значение путем прямого вычисления возвращаемого элемента.