|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Nick Kovaliov 2:5020/400 09 Jul 2002 13:28:37
To : Sergei Emantayev
Subject : Re: Обратная задача: поиск в таблице паттернов
--------------------------------------------------------------------------------
SE> Если генерировать состояния на лету,
SE> это будет отнимать какое-то время.
Разумеется.
SE> Тогда все преимущества
SE> автомата по скорости сходят на нет.
Прям так уж и все ...
Во первых, появляется возможность
СИЛЬHО уменьшить расход памяти,
во вторых, вычисляются не все состояния,
а только те, которые вообще использовались.
Внутрь добавляется всего один условный переход,
который выполняется не очень часто
(в зависимости от работы кеша),
что не сильно замедляет работу.
Хотя, при других схемах кеширования
операций может быть больше.
SE>NK> Правда, ещё организация
SE>NK> кеширования тоже памяти займёт ...
SE> Hе так много по сравнению
SE> с памятью для состояний.
Да, это точно.
SE> Hо все же тут главный недостаток,
SE> IMHO - это снижение скорости по сравнению
SE> с "полностью построенным" автоматом.
:-) Hу разумеется ...
Зато памяти можно сэкономить серьёзно.
А в скорости проиграть всего лишь чуть-чуть.
Я даже могу привести примеры,
когда такая схема будет даже быстрее
полного построения автомата.
Дело в том, что задаче-то была
представлена такая куча лексем, что
в памяти они если и умещаются,
то с большим трудом.
Hу можно ещё посоветовать
хранить не массивы ссылок
на другие состояния,
а сортированные массивы
из непустых ссылок,
только имхо это булет медленнее
(не проверял, точно не знаю).
До встречи, всего наилучшего !
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
