C++ Карта STL по сравнению с Векторной скоростью

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

Примите совет Нила ; map обычно является хорошей структурой данных для таблицы символов, но вам нужно убедиться, что вы используете ее правильно (и не добавляете символы случайно).

a std :: map (O (log (n))) или хеш-таблица ("амортизированная" O (1)) будет первым выбором - используйте специальные механизмы, если вы определили, что это узкое место. Как правило, первой оптимизацией является использование хеша или токенизации ввода.

Прежде чем вы его профилируете, очень важно изолировать поиск, чтобы вы могли легко заменить и профилировать его.

std :: map , вероятно, немного медленнее для небольшого количества элементов (но тогда это не имеет особого значения).

Карта - это хорошая вещь для таблицы символов. но оператор [] для карт - нет. В общем, если вы не пишете какой-то тривиальный код, вам следует использовать функции-члены карты insert () и find () вместо operator [] . Семантика operator [] несколько сложна и почти наверняка не сделает то, что вы хотите, если искомого символа нет на карте.

Что касается выбора между map и unordered_map , разница в производительности вряд ли будет значительной при реализации простого интерпретируемого языка. Если вы используете карту, вам гарантировано, что она будет поддерживаться всеми текущими реализациями Standard C ++.

Обычно вы должны использовать таблицу символов для поиска переменной по ее имени, которое указано в источнике. В этом случае у вас есть только имя, с которым можно работать, поэтому хранить кэшированную позицию переменной в таблице символов негде. Так что я бы сказал, что карта - хороший выбор. Оператор [] занимает время, пропорциональное журналу количества элементов на карте - если он окажется медленным, вы можете использовать хэш-карту, например std :: tr1 :: unordered_map .

Карта имеет значение O (log N), поэтому не так быстро, как позиционный поиск в массиве. Но точные результаты будут зависеть от множества факторов, и поэтому лучший подход - это взаимодействие с контейнером таким образом, чтобы в дальнейшем можно было переключаться между реализациями. То есть напишите функцию «поиска», которая может быть эффективно реализована любым подходящим контейнером, чтобы позволить себе переключаться и сравнивать скорости различных реализаций.

Карта будет масштабироваться намного лучше, что будет важной особенностью. Однако не забывайте, что при использовании карты вы можете (в отличие от вектора) брать указатели и ссылки. В этом случае вы можете легко «кэшировать» переменные с картой так же правильно, как и вектор. Карта здесь почти наверняка будет правильным выбором.

std :: map operator [] занимает время O (log (n)). Это означает, что он достаточно эффективен, но вам все же следует избегать повторения поиска снова и снова. Возможно, вместо хранения индекса вы можете сохранить ссылку на значение или итератор на контейнер? Это избавляет от необходимости полностью выполнять поиск.

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

Реализации карты STL обычно реализуются с самобалансирующимися деревьями , такими как структура данных красно-черное дерево , и их операции занимают время O (logn).

Мой совет - обернуть код манипуляции таблицей в функции,
вроде table_has (name) , table_put (name) и table_get (имя) .

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

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

Например, Python (реализация C) преобразует локальные переменные в ссылки по индексу, но глобальные переменные и переменные класса получают ссылки по имени с использованием хеш-таблицы.

Предлагаю посмотреть вводный текст о компиляторах.

Оператором карты [] является O (log (n)), см. Википедию: http://en.wikipedia.org/wiki/Map_ (C% 2B% 2B)

Я думаю, как вы » Если вы часто ищете символы, конечно, правильно использовать карту. Возможно, хеш-карта ( std :: unordered_map ) может улучшить вашу производительность.

Вы говорите: "Если переменная, все еще использующая вектор, обнаруживается в первый раз , Я могу сохранить его точное целое число в векторе. ".

Вы можете сделать то же самое с картой: искать переменную, используя find , и сохранять итератор , указывающий на нее, вместо позиции.