Создание таблицы символов с использованием хеш-таблицы

Question

Я пытаюсь построить таблицу символов, используя хэш-таблицу. Общая идея

int alpha;
2 int beta;
3 alpha = 0; // the alpha declared in line 1
4 beta = 0; // the beta declared in line 2
5 gamma = 0; // Error! gamma hasn't been declared.
6 {
7 int beta; // This beta shadows the one declared in line 2.
8 int gamma;
9 alpha = 0; // the alpha declared in line 1
10 beta = 0; // the beta declared in line 7
11 gamma = 0; // the gamma declared in line 8
12 }

и так далее. Вы можете использовать только библиотеку vector, list, stack и queue и попытаться сделать это настолько быстро, насколько сможете. Моя идея была в каждой области, я объявляю хеш-таблицу в списке и сохраняю всю информацию в эту таблицу, и всякий раз, когда у меня появляется новая область, я помещаю новую хеш-таблицу в список. Но кажется, что этот подход очень медленный, когда программа ищет элемент, который находится вне области видимости далеко, так как вам нужно искать каждую область, чтобы найти элемент.

Ребята, у вас есть идея реализовать эту область, которая намного быстрее, чем эта? Это должно быть намного быстрее, потому что моя реализация медленнее, чем «медленная версия, которую они предоставили»

Большое спасибо!

Answer 1

Имеется только одна хеш-таблица для всего и стек объектов контекста.Вставляйте новый объект в стек всякий раз, когда вы видите «{».Когда вы скрываете переменную, запомните старый символ в вашем объекте контекста и просто перезапишите его в хеш-таблице.Когда вы увидите '}' и откроете контекст, восстановите символы, которые вы там запомнили.

Answer 2

Когда я это сделал, я использовал хеш-таблицу для символов, а не для сущностей. Для каждого символа у меня был список сущностей. Каждая сущность была в двух списки, один из символа, а второй из области видимости. Список из символа управлялся как стек: когда я получил доступ к символу, сущность по объему всегда была первой в списке. Когда я оставил прицел, Я прошел его список объектов и удалил их из списка символы.

Это было некоторое время назад, до STL (и даже до C ++); я реализовал все вручную, и использовал инвазивные цепочки для списки, с алгоритмом, разработанным так, чтобы я мог удалить элемент из списка, не зная, где сам список был. (Это относительно легко с рукописными двойными связанными списками.) Сегодня, с STL (и с учетом важности локального доступа), я бы, вероятно, просто поставить указатель на заголовок списка в каждой сущности. С STL и учитывая местность, я бы, вероятно, использовал std::vector для списка для каждого объекта (таблица символов, таким образом, представляет собой карту std::string в std::vector). Поиск таблицы символов, когда запись найдена, просто вызов back() для вектора (после проверки, что он не пустой, если Вы не удаляете запись, когда вектор становится пустым). Когда ты создать новую сущность, в новой области, вы вызываете push_back на вектор, и сохраните адрес вектора в записи для области ( std::stack из std::vector<std::vector<Entity>*>); при выходе область, вы перебираете вектор в верхней части этого стека, вызывая pop_back на всех его записях, затем вытолкните его из стека. (А также очевидно, при входе в новую область вы push новый пустой вектор на стек области действия.)

Ведение двойного списка означает, что для всех операций вы знаете, какой именно элемент для доступа, без необходимости перебирать что-нибудь; нет доступа к объекту, чтобы узнать, ты ищешь. В мои дни это было довольно просто, но много кода, требующего значительного ухода, и моя реализация, вероятно, не будет так быстро сегодня из-за плохой местности. Сегодня с STL, вам нужно гораздо меньше кода, и с помощью std::vector для всех списки, вы получаете немного лучшую местность; Вы все еще должны быть осторожны, чтобы вы не сохранили итераторы, которые будут признаны недействительными. (Но реализовано, как описано выше, вам не нужно; все обращения всегда до последнего элемента вектора, поэтому сохранение адреса самого вектора достаточно. При условии, конечно, что ваш хеш реализация не перемещает векторы.)

Answer 3

Это хорошая идея.В большинстве языков области редко вкладываются очень глубоко, возможно, в среднем 3 или 4 вложенных области.Так что я бы не беспокоился о вещах, которые «далеко-далеко», так как это будут патологические случаи.