STL :: Map - пройтись по списку или использовать поиск?

Question

Скажем, у меня есть метод, который должен извлечь 8 значений из карты со 100 элементами в ней. Как вы думаете, было бы предпочтительнее:

Пройдите цикл for от начала до конца, вытащив элементы, включив ключ?

Или 8 раз использовать find для получения этих значений?

Answer 1

Прогулка по списку займет у вас (n) время, чтобы найти случайный элемент.

Карта - это сбалансированное двоичное дерево, поэтому поиск - это O (log n).

Таким образом, выполнение 8 находит результаты в 8 * log2 (n), а ход списка - (n). Чем больше список, тем больше выигрыш, но во всех случайных случаях поиск будет быстрее, чем выполнение итераций.

В неслучайных случаях, если есть причина, по которой предметы, которые вы хотите, находятся рядом друг с другом в дереве или рядом с «началом» (слева), тогда ходьба / повторение будет быстрее. Но это кажется неприятным.

Answer 2

Хотя я бы выбрал вариант find, люди слишком много внимания уделяют асимптотике.

Дело в том, что асимптотическая производительность является удобным руководством для алгоритмов, которые могут получать достаточно большие входные данные, но даже в этом случае они не являются надежными. Алгоритм с более низкой асимптотической производительностью вполне может быть быстрее для любого разумного ввода.

А иногда бывают случаи, когда размер вашего ввода довольно мал (или даже фиксирован). В таких случаях асимптотическое поведение практически бессмысленно.

Answer 3

Я бы использовал find 8 раз. Это будет менее (и более очевидный) код.

Вы должны стараться не оценивать производительность на основе небольших чисел, поскольку (а) маловероятно, что в любом случае это будет узким местом производительности, и (б) цифры могут измениться в будущем - выберите алгоритм с лучшая асимптотика.

Примечание: вы упоминаете «переключение» на ключе ... что может применяться в вашем случае, но в целом вы не можете включить значение ключа на карте. Это позволило бы сделать код для поиска M элементов на карте итерацией еще более сложным.

Answer 4

Как уже отмечали другие, я, вероятно, просто использовал бы find () на карте восемь раз и покончил бы с этим. Но есть альтернатива для рассмотрения в зависимости от ваших потребностей. Если элементы на карте не будут сильно меняться после того, как карта построена, или вам не нужно чередовать вставки с поисками, вы можете просто попытаться сохранить пары ключ / значение в отсортированном векторе. Если вы сделаете это, то можете использовать функцию lower_bound (), чтобы выполнить бинарный поиск за логарифмическое время. Преимущество этого заключается в том, что, если ключи, которые вы ищете, можно заказать (и вы знаете, что они всегда будут присутствовать), вы можете использовать итератор, возвращенный из предыдущего поиска, в качестве нижней границы для следующего. например.,

vector::iterator a = my_map.lower_bound( my_map.begin(), my_map.end(), "a" );
vector::iterator b = my_map.lower_bound( a + 1, my_map.end(), "b" );
vector::iterator c = my_map.lower_bound( b + 1, my_map.end(), "c" );
// ...

Оба подхода имеют логарифмический поиск, но это может помочь несколько уменьшить константу.

Answer 5

8 находит лучше, потому что код проще и понятнее.

Впрочем, думать о производительности веселее, поэтому я тоже так сделаю.

Как сказал Артелий, когда я писал этот ответ, не обращайте внимания на сложность. Это не актуально, потому что вы знаете, что n = 100. Например, сортировка вставки имеет более сложную алгоритмическую сложность, чем быстрая сортировка (по крайней мере, в среднем случае), но почти во всех реализациях сортировка вставки выполняется быстрее, чем быстрая сортировка для малых n, и поэтому быстрые сортировки разбиваются на сортировку вставок в конце. Ваш n также мал, так что ограничение как n -> бесконечность не имеет значения.

Поскольку код для обоих вариантов прост в написании, я бы предложил его профилировать. Это (а) скажет вам, что быстрее, и (б) докажет, что оба они настолько быстры, что не имеет значения, что вы делаете (если только это не единственная вещь, которую делает ваша программа, и она делает это много). Тем более, что вы говорите о включении ключа - если ключ является целочисленным типом, то ограничивающим фактором, скорее всего, будут проблемы с кэшем памяти, чем при любой фактической обработке.

Однако, если это не удается, обычно способ сравнения алгоритмов поиска заключается в подсчете сравнений, исходя из предположения, что они намного медленнее, чем обход структур. Если ничто иное, каждое сравнение обращается к памяти и представляет собой непредсказуемую ветвь, из-за которой ЦП зачастую хуже всего.

Если вы сортируете свои 8 элементов перед началом (что требует 24 сравнений или около того) вместо предлагаемого вами переключателя, то, поскольку карта также отсортирована, вам нужно сделать только одно сравнение на каждом узле, который вы проходите, плюс один сравнение по элементу, который вы ищете (сравните один узел с каждой "стороны". Если они совпадают, увеличивайте обе стороны. Если они не совпадают, увеличивайте сторону с меньшим элементом). Так что в худшем случае это 8 + 100 или меньше, если вы найдете все 8 до того, как доберетесь до конца. Но среднее положение последних 8, если они случайно расположены на карте, все равно примерно 8/9 пути. Поэтому назовите это 8 + 88 + 24 = 120 сравнений, при этом 132 - наихудший случай. В лучшем случае это 8 (если все, что вы ищете, все в начале) +24 (для начальной сортировки) = 32 сравнения, или даже лучше, если вам повезло и с сортировкой, или ваши 8 элементов поиска по какой-то причине готовый.

Средняя глубина узла в красно-черном дереве (обычно это карта) немного больше log2 (n). В этом случае назовите его 7, поскольку 2 ^ 7 равно 128. Таким образом, для поиска 8 элементов потребуется примерно 56 сравнений. IIRC характеристика баланса красно-черного дерева состоит в том, что самый глубокий узел не более чем в два раза глубже самого мелкого. Таким образом, наихудшая глубина - это floor (2 * log2 (n)), назовите его 15, что в сумме составляет 120, а лучшим является ceil (1/2 log2 (n)), что равно 4. Это снова 32 сравнения.

Если предположить, что сравнения - это единственное, что влияет на скорость, 8 находок будут где-то в 4 раза быстрее и в 4 раза медленнее, чем линейный обход, с в 2 раза лучшим средним.

Линейный обход, вероятно, затронет больше памяти, поэтому может быть медленнее в этом отношении. Но, в конечном счете, для n = 100 вы говорите миллисекунды, так что просто делайте любой самый простой код (вероятно, 8 находок). И я упоминал, что если вы действительно хотите знать скорость, которую вы не можете предсказать, вы просто должны профилировать ее?

Answer 6

Давайте предположим, что "находят" залоги, когда он находит ключ.

Давайте далее предположим, что вы кодируете «ключ» разумно, и он прекращает проверку после того, как находит совпадение. Мы также предполагаем, что вы не пытаетесь закодировать его, чтобы выполнить весь процесс, как только все 8 были найдены (это, вероятно, было бы неудобно для кодирования).

Подход "8 находок" может ожидать (iow: в среднем) выполнения 50 * 8 = 400 сравнений.

Подход «переключения» может ожидать (iow: в среднем) выполнения (8 * 100) - 28 = 772 сравнения.

Таким образом, с точки зрения сравнений, подход 8 находок лучше. Тем не менее, количество сравнений достаточно мало, так что вам будет лучше, если вы просто выберете вариант, который легче понять. Это, вероятно, тоже будет подходом 8 к поиску.

Answer 7

Если это так важно, я бы реализовал оба и оценил производительность.

Теоретически это

8 * lg (100)>? <100 </p>

Другие соображения: если любое из этих чисел когда-либо изменится, будет ли оно когда-либо более 100 элементов; Вы когда-нибудь будете делать более 8 поисков?

Answer 8

Вы должны использовать find 8 раз.

Думайте о подходе коммутатора как о том, чтобы взять каждый узел и сравнить его 8 раз. Это 800 сравнений, и вы теряете все преимущества, связанные с тем, что карта вообще указана, это может быть и список.

При подходе поиска вы просматриваете список, используя преимущества карты. Я считаю, что std :: maps реализованы в виде бинарных деревьев, то есть для поиска ключа потребуется только сравнение вашего ключа до глубины дерева, которая будет равна 8 ~ для двоичного дерева из 100 элементов. Теперь вы можете найти все 8 элементов только с 8 * 8 сравнениями или 64 сравнениями.

Answer 9

Вот анализ их временной сложности (n - количество элементов на карте), который гарантированно сделает поиск для поиска с логарифмической или лучшей временной сложностью:

8 * log2 n  for 8 times find
n for the iterate through all

Первый больше для меньших чисел (например, 8 для n = 2), но около 43 первый станет лучше второго и останется таковым. Итак, вы захотите использовать первый метод, учитывая, что он также более удобен для кодирования.