Автор: Шелвин,
01 марта 2004 года в 14:27:52
В ответ на : Уточняю вопрос от Мимошёл
в 29 февраля 2004 года в 19:30:48:
> 1) вычисление вероятности,
> соответствующей декодируемому
> символу (cum)
> 2) поиск символа, интервал
> вероятностей
> которого содержит cum
> 3) обновление интервала [low,high] и
> чтение битов.> Так вот, я говорю о возможности
> оптимизации второй части заменой
> линейного поиска бинарным. А я думаю, что разницы никакой нет.
Если вероятности хранятся в массиве,
то в худшем случае их все равно
придется прочитать все для расчета
нижней границы интервала. (Можно
разве что "ускорить" работу за счет
сканирования с двух сторон, но кэш
тебя не поймет). Значит, для
реального ускорения счетчики надо
_хранить_ в другом виде. Бинарное
дерево в этом смысле удобней всего.
А если предлагается хранить суммы
счетчиков (тогда можно использовать
бинарный поиск по линейному массиву),
то надо учесть еще и апдейт, который
это сильно усложнит. > А какие ещё бывают процессорные такты,
> кроме шестнадцатиричных? ;) Аэмдэшные и интеловские ;)
|