Альтернатива хэш-карте для малого набора данных в C

Question

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

[команда] [аргумент] * (- - [флаг] [аргумент флага] )

В настоящее время команда являетсяотправляется через условный блок, по сравнению с различными известными командами, и соответствующий пакет данных отправляется в функцию сопоставления.Это, однако, кажется неуклюжим, неэффективным и не элегантным.

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

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

Спасибо за помощь.

Answer 1

Возможно, вы захотите рассмотреть Дерево троичного поиска . Хорошее исполнение, эффективное использование хранилища; и вам не нужна хеш-функция или стратегия столкновений.

Связанная статья Bentley / Sedgwick - очень подробное, но читаемое объяснение сопроводительного источника С.

Я использовал TST для поиска имени в последних 3 версиях моего интерпретатора postscript. Единственные изменения, которые были необходимы, были связаны с изменениями в управлении памятью. Вот версия Я изменил (слегка), чтобы использовать явные указатели. Я использую еще одну версию в моем интерпретаторе postscript , любую из версий xpost2 * .zip, в файле core.c, который использует смещения байтов для указателей (должен быть добавлен в байт пользовательской памяти). указатель для получения реального указателя).

Answer 2

Полученная скорость, вероятно, будет минимальной, но вы можете хешировать команду, чтобы преобразовать ее в число, а затем использовать оператор switch. Быстрее, чем хэш-карта.