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

Question

В интерпретаторе моего экспериментального языка программирования у меня есть таблица символов. Каждый символ состоит из имени и значения (значение может быть, например: типа string, int, function и т. Д.).

Сначала я представлял таблицу с вектором и повторял символы, проверяя, подходит ли данное имя символа.

Тогда я, хотя и использовал бы карту, в моем случае map<string,symbol>, было бы лучше, чем постоянно перебирать вектор , но :

Немного сложно объяснить эту часть, но я попробую.

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

Так что я мог бы использовать карту для получения переменной: SymbolTable[ myVar.Name ]

Но подумайте о следующем: если переменная, все еще использующая вектор, найдена в первый раз, я могу сохранить ее точное целочисленное положение в векторе вместе с ней. Это означает: в следующий раз, когда это понадобится, мой интерпретатор знает, что он был «кэширован», и не ищет его в таблице символов, а выполняет что-то вроде SymbolTable.at( myVar.CachedPosition ).

Теперь мой (довольно сложный?) Вопрос:

• Должен ли я использовать вектор для таблицы символов вместе с кэшированием позиции переменной в векторе?

• Мне лучше использовать карту? Зачем? Как быстро работает оператор []?

• Должен ли я использовать что-то совершенно другое?

Answer 1

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

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

Answer 2

У вас есть ряд альтернатив.

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

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

Критики

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

Answer 3

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

Answer 4

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

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

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

Answer 5

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

Answer 6

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

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

---

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

Answer 7

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

Answer 8

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

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

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

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

Answer 9

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

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

Answer 10

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

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