VPF::Основы анализа из книги Дж. Макконнела

fclmfan

Дата 19.11.2011, 18:56 (ссылка)

(нет голосов)

Загрузка ...

Werdum face

Профиль
Группа: Awaiting Authorisation
Сообщений: 64
Регистрация: 21.10.2008

Репутация: нет
Всего: нет

Здравствуйте! Начал читать книгу "Основы современных алгоритмов" и наткнулся на такой отрывок вначале первой главы.
Вобщем есть псевдокод какого-то алгоритма

Код


Рассмотрим, например, алгоритм подсчета числа вхождений различных символов в файл.
Алгоритм для решения такой задачи мог бы выглядеть примерно так:
for all 256 символов do
    обнулить счетчик
end for
while в файле еще остались символы do
    ввести очередной символ
    увеличить счетчик вхождений прочитанного символа на единицу
end while

и есть разбор этого алгоритма, с которым я в принципе согласен

Код


Посмотрим на этот алгоритм. Он делает 256 проходов в цикле инициализации. Если во
входном файле N символов, то втором цикле N проходов. Возникает вопрос «Что же считать?».
В цикле for сначала инициализируется переменная цикла, затем в каждом проходе проверяется,
что переменная не выходит за границы выполнения цикла, и переменная получает приращение.
Это означает, что цикл инициализации делает 257 присваиваний (одно для переменной цикла
и 256 для счетчика), 256 приращений переменной цикла, и 257 проверок того,
что эта переменная находится в пределах границ цикла (одна дополнительная для остановки цикла).
Во втором цикле нужно сделать N + 1 раз проверку условия (+1 для последней проверки, когда файл пуст),
и N приращений счетчика.
Всего операций:
Приращения N + 256
Присваивания 257
Проверки условий N + 258
Таким образом, при размере входного файла в 500 символов в алгоритме делается 1771 операция,
из которых 770 приходится на инициализацию (43%). Теперь посмотрим, что происходит при
 увеличении величины N. Если файл содержит 50 000 символов,
то алгоритм сделает 100 771 операцию, из которых только 770 связаны с инициализацией
(что составляет менее 1% общего числа операций).
Число операций инициализации не изменилось, но в процентном отношении
при увеличении N их становится значительно меньше.

Далее идёт такой текст:

Код


Теперь взглянем с другой стороны. 
Данные в компьютере организованы таким образом,
что копирование больших блоков данных происходит с той же скоростью,
что и присваивание. Мы могли бы сначала присвоить 16 счетчикам начальное значение,
равное 0, а затем скопировать этот блок 15 раз, чтобы заполнить остальные счетчики.
Это приведет к тому, что в циклах инициализации число проверок уменьшится до 33,
присваиваний до 33 и приращений до 31. Количество операций инициализации
уменьшается с 770 до 97, то есть на 87%. Если же мы сравним полученный выигрыш
с числом операций по обработке файла в 50 000 символов, экономия составит менее 0.7%
(вместо 100 771 операций мы затратим 100 098). Заметим, что экономия по времени
могла бы быть даже больше, если бы мы сделали все эти инициализации без циклов,
поскольку понадобилось бы только 31 простое присваивание, но этот дополнительный
выигрыш дает лишь 0.07% экономии. Овчинка не стоит выделки.

В строках 2-5 написано то, что я собственно не понял. А именно: допустим мы
присвоили 16-ти счётчикам (16 разных переменных) начальное значение 0. Если я правильно понял,
это происходит перед циклом с 15-тью итерациями (который "копирует блок, чтобы заполнить остальные счётчики").
Не пойму, как это может происходить? Какой блок? Как этот блок копировать, да ещё и в цикле?

Pavia

Дата 20.11.2011, 10:44 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 418
Регистрация: 6.12.2008

Репутация: 11
Всего: 12

Речь идёт про цикл

Код


for all 256 символов do
    обнулить счетчик

Как устроен этот цикл.

Он преобразуется в

Код


for (i=0; i<256;i++) 
 a[i]=0;

Ясно что тут будет 256 сравнений переменной i.

Можно сделать так, 16 я не буду делать возьму 8.

Код


a[0]=0;
a[1]=0;
a[2]=0;
a[3]=0;
a[4]=0;
a[5]=0;
a[6]=0;
a[7]=0;
 a=(a+8);  //- переместим указатель на 8 символов
for (i=1; i<32;i++) 
 {
//Копируем предыдущие 8 символов
 a[0]=a[0-8];
 a[1]=a[1-8];
 a[2]=a[2-8];
 a[3]=a[3-8];
 a[4]=a[4-8];
 a[5]=a[5-8];
 a[6]=a[6-8];
 a[7]=a[7-8];
 a=(a+8);  //- переместим указатель на 8 символов
 }

Как видно тут сравнений i требуется уже всего 31 раз.

Про присвоения, тут я использовал по символьное присвоения. Но в компьютере байты(char) располагаются близко и могу использовать word, DWord, QWord, и тд.

Код


 a[0]=a[0-8];
 a[1]=a[1-8];
 a[2]=a[2-8];
 a[3]=a[3-8];
 a[4]=a[4-8];
 a[5]=a[5-8];
 a[6]=a[6-8];
 a[7]=a[7-8];
 a=(a+8);  //- переместим указатель на 8 символов

Можно заменить

Код


QWord* B;
B=а; // Присваиваем B указатель на массив a(на нулевой элемент массива a).
B=B+1;  //- переместим указатель на 8 символов или один QWord 
for (i=1; i<32;i++) 
 {
//Копируем предыдущие 8 символов
B[0]=B[-1];
B=B+1;  //- переместим указатель на 8 символов или один QWord 
}

Это сообщение отредактировал(а) Pavia - 20.11.2011, 12:21

volatile

Дата 20.11.2011, 11:59 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 2
Всего: 85

Цитата(Pavia @ 20.11.2011, 10:44

)

a[7]=0;
for (i=1; i<32;i++)
{
//Копируем предыдущие 8 символов
a[0]=a[0-8];

Pavia, я конечно понимаю что это псевдокод, и все такое, но поосторожней с индексами.
У вас везде выход за пределы в отрицательную сторону.

Цитата(Pavia @ 20.11.2011, 10:44

)

B=а; // Присваиваем B указатель на массив a(на нулевой элемент массива a).
for (i=1; i<32;i++)
{
//Копируем предыдущие 8 символов
B[0]=B[-1];

Ужос!

Pavia

Дата 20.11.2011, 12:18 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 418
Регистрация: 6.12.2008

Репутация: 11
Всего: 12

volatile,
Исправил

fclmfan

Дата 21.11.2011, 17:56 (ссылка)

(нет голосов)

Загрузка ...

Werdum face

Профиль
Группа: Awaiting Authorisation
Сообщений: 64
Регистрация: 21.10.2008

Репутация: нет
Всего: нет

Спасибо за ответы! Теперь понятно.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »