Re: Уточняю вопрос


Сайт о сжатии >> Форум #Компрессор# >> [Ответить] [Ответы]

Автор: Шелвин,
01 марта 2004 года в 14:27:52

В ответ на : Уточняю вопрос от Мимошёл в 29 февраля 2004 года в 19:30:48:


> 1) вычисление вероятности,
> соответствующей декодируемому
> символу (cum)
> 2) поиск символа, интервал
> вероятностей
> которого содержит cum
> 3) обновление интервала [low,high] и
> чтение битов.

> Так вот, я говорю о возможности
> оптимизации второй части заменой
> линейного поиска бинарным.

А я думаю, что разницы никакой нет.
Если вероятности хранятся в массиве,
то в худшем случае их все равно
придется прочитать все для расчета
нижней границы интервала. (Можно
разве что "ускорить" работу за счет
сканирования с двух сторон, но кэш
тебя не поймет). Значит, для
реального ускорения счетчики надо
_хранить_ в другом виде. Бинарное
дерево в этом смысле удобней всего.
А если предлагается хранить суммы
счетчиков (тогда можно использовать
бинарный поиск по линейному массиву),
то надо учесть еще и апдейт, который
это сильно усложнит.

> А какие ещё бывают процессорные такты,
> кроме шестнадцатиричных? ;)

Аэмдэшные и интеловские ;)

Ответы:



Ответить на это сообщение

Тема:

Имя (желательно полное):

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).

Пожалуйста, заполните все поля.
И не нажимайте по два раза на кнопку! Дождитесь ответа сервера.