Правильно ли я понимаю, что в обычной реализации форта, без

Question

FORTH и родственные ЯП

Defragmented Panda

Правильно ли я понимаю, что в обычной реализации форта, без

хэширования, поиск слова в словаре с 100 записями может потребовать 100 сравнений слов? (И в среднем около 50)

#forth #programming #russian

0

07.12.2021

3 ответов

13 просмотров

ruv

ruv
Без хэширования — да, перебираются все доствупные ...

Кстати, тут я не прав, что если нет хэширования, то перебирается все имена. Т.к. можно еще хранить имена (ссылки) в упорядоченном массиве и делать бинарный поиск. А можно использовать сбалансированное дерево, и тоже искать в нем, без перебора всех вариантов. Т.е., хэширование — далеко не единственная альтернатива простому списку.

0

07.12.2021

ruv

ruv
Кстати, тут я не прав, что если нет хэширования, т...

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

0

07.12.2021

ruv · Accepted Answer

Без хэширования — да, перебираются все доствупные имена, или пока не найдется совпадение. Но, это простое сравнение на совпадение (без определения больше/меньше). Т.е., если длина разная — то сравнивать содержимое не надо. Что касается "обычности" — полно реализаций, которые используют хэширование в большей или меньшей мере.

169 похожих чатов

Правильно ли я понимаю, что в обычной реализации форта, без

3 ответов

Похожие вопросы