Как убежать от hardcoded строк?

Скажем, мне очень часто попадаются подобные фрагменты в программах:

Код (Text):

1.  
2. if(!strcmp(str, "vasya")) vasya_was_here = 1;
3. else if (!strcmp(str, "petya")) petya_was_here = 1;
4. else if (!strcmp(str, "serega")) serega_was_here = 1;
5.  

Пример немножко надуманный, но суть, думаю, ясна. Можно ли что-то с этим сделать?

Вариант: не строки, а хеши строк + массив

У кого-то есть еще какие-нибудь предложения?

Что, если действие будет более сложным, чем vasya_was_here = 1;

Скажем, выполнение какой-нибудь функции или что-то пододбное? И все функции разные...

 

а почему бы не попробовать построить какой-нибудь КА для строк(как вариант). на вход подоем строку. ждем пока он не попадет в одно из "конечных" состаяний. а их уже (путь они будут int простым switch - case.

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

минусы: слишком громоздко и сложно, требует больше памяти.



P.S. я бы постарался особо не замарачиватся этим методом

 

О боже... Опять КА... Только недавно закончил один КА - см. тут:



http://www.wasm.ru/forum/index.php?action=vthread&forum=17&topic=7757



тут еще другой тут же надо...

Надо подумать...

 

Тут, кстати, не только вопрос производительности. Тут еще и вопрос архитектуры. Положим, имя petya из примера выше, поменялось на имя dasha. Что тогда? Менять код? А если таких мест много? Хорошо бы все имена положить в какую-то одну структуру...

 

я видел просто несколько напрашиваемоеся решение... хотя может и не очень приятное в плане разработки и реализации(особенно первое)

хеши классно конечно....

вот кстати еще можно с хешами, когда действие более сложное: иметь массив неких номеров - а по ним уже делать switch-case

или вот еще: если подобрать хеш ф-цию на данное множество(если оно заранее определенно) без коллизей то тогда можно делать switch-case сразу по хеш-значению. плюс - памяти надо мало. минус: нужно заранее определенное мн-во+офигенно сложно подорать ф-цию без коллизей.

 

volodya

почему менять код? для первого "случая" все гораздо хуже. там надо заново строить КА...



P.S. сорри. пока писал пред. пост ты уже накатал новый, который делает частично недействительным мой второй

 

volodya

А что в C нет понятия константа, которую можно определить один раз и естно она легко меняется..

в masm бы это выглядело так

Код (Text):

1. SomeName1  TEXTEQU  <"Vasya]

или я не понял что ты хочешь %)

 

Asterix



Разумеется есть. В С. В тупорылой жабе нет.

НО.

Какая разница? Что пнем об сову, что сову об пень. Что константу, что хардкод... И то, и то фигня



tasman

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

 

volodya

В жабе тоже есть:

final String vasya = "Vasya";

Эт точно. Без хешей не обойтись.

 

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

 

volodya

STRINGTABLE в ресурсе, а ID как hash value?

 

Никаких виндузных примочек. Только чистые кросс-платформенные идеи

 

Хотя, придумал неплохо

 

volodya >

Я делал массив из таких структур: хэш + обработчик + аргумент для обработчика (если нужен)

Ищем хэш, при совпадении вызываем обработчик (прям как switch у tasman

Для скорости хэш считается каким-нибудь примитивным xor + ror.

Недостаток - хэши должены быть уникальными.

Здесь 2 варианта решения: - если строки длинные, дополнительно сравнивать сами строки;

- если строки короткие - реализовать эффективный "strcmp" (возможно, для каждой возможной длины отдельно) и отказаться от хэшей.

На асме это всё просто, быстро и красиво, как на жабе - не знаю :-(

И вообще, не уверен, что в тему =)

 

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

Конечно, можно заделать б-дерево, но не уверен что задача того стоит..

 

Пока будешь сортировать, простым перебором 5 раз найдёшь

Хотя, если строки не добовляются во время выполнения, то конечно лучше так.

 

volodya

Есть следующий остроумный гибрид trie и patricia:



-- посмотреть на первую букву слова

-- используя эту букву в качестве индекса выбрать из двух заранее построенных таблиц указатель на вторичную таблицу и номер буквы

-- посмотреть на букву с только что найденным номером буквы

-- использовать её в качестве индекса во вторичной таблице, получить указатель в таблице слов

-- сравнить (с помощью strcmp) и убедиться, что найденное слово является искомым.

_____________________________



Таблицы все естественно нужно строить заранее по списку слов.

Лучше всего сделать программу их автоматического построения.

В таблицах будет много дырок, поэтому их следует сжимать в одну большую таблицу.

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

_____________________________



Картинка:

862789793__vasya.png

 

сравнить (с помощью strcmp) и убедиться, что найденное слово является искомым.



э-э-э...

а эффективность такого метода?

 

сравнить (с помощью strcmp) и убедиться, что найденное слово является искомым.



э-э-э...

а эффективность такого метода?

volodya

Сильного влияния на эффективность это оказать не должно - ведь мы сравниваем полностью строки только один раз.

 

volodya> а эффективность такого метода?



В одной из моих конкретных задач это был самый эффективный по скорости метод (на втором месте - лексер на таблицах переходов КА).

Действительно: просматриваются только две буквы слова, а потом проверяется что найденное слово правильное. При любом хэшировании strcmp() также понадобится. Другое дело что метод работает только на сравнительно маленьких словарях. Иначе придётся рассматривать аналогичным образом три буквы (что тоже весьма быстро).



tasman> ведь мы сравниваем полностью строки только один раз.



Угу.