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

Фактически у вас есть несколько альтернатив.

Существуют библиотеки:

• Loki::AssocVector: интерфейс карты, реализованный на основе vector пар, быстрее, чем карта для небольших или замороженных наборов из-за локальности кеша.
• Boost.MultiIndex: предоставляет как Список с быстрым поиском и пример внедрение списка MRU (последние Используется), который кэширует последние использованные элементы.

Критики

• Поиск и извлечение карты занимает O(log N), но элементы могут быть разбросаны по всей памяти, что плохо сочетается со стратегиями кэширования.
• Вектор более удобен для кеша, однако, если вы не отсортируете его, у вас будет O(N) производительность на find, приемлемо ли это?
• Почему бы не использовать unordered_map ? Они обеспечивают O(1) поиск и извлечение (хотя константа может быть высокой) и, безусловно, подходят для этой задачи. Если вы посмотрите статью Википедии о хеш-таблицах, вы поймете, что существует множество доступных стратегий. и вы, безусловно, можете выбрать тот, который будет соответствовать вашему конкретному шаблону использования.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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