С++ STL Map vs Vector speed

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

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

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

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

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

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

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

Теперь мой (довольно жесткий?) вопрос:

Должен ли я использовать вектор для таблицы символов вместе с кэшированием положения переменной в векторе?
Должен ли я использовать карту? Зачем? Насколько оперативен оператор []?
Должен ли я использовать что-то совершенно другое?

Ответ 1

У вас есть несколько альтернатив.

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

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

Критики

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

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

Ответ 5

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

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

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

Ответ 6

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

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

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

Ответ 7

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

Ответ 8

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

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

Ответ 9

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

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

Ответ 10

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

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

Ответ 11

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

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

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

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

Ответ 12

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