Алгоритмы. Основные понятия.

Начинаю потихоньку выкладывать статьи, которые всё-таки были написаны в рамках проекта IT-Stage. Думаю, тебе понравится.

Первый вопрос, на который нам с вами необходимо ответить, вообще, что же такое алгоритм. Я не удивлюсь, что читатель это знает, но, поскольку статья рассчитана на широкую аудиторию,  я начну с самого начала.

Алгоритм (algorithm) представляет собой пошаговую инструкцию выполнения процесса, действия или вычисления. Это достаточно вольное определение, но, на мой взгляд, более понятное и простое. Как ясно из определения, алгоритмы используются везде. Начиная от такого, на первый взгляд, банального сложения столбиком, и заканчивая более сложными, тяжелыми для понимания (по началу) и реализации. В программировании алгоритмы представляются как сложные методы выполнения различных вычислений. В этой статье я не буду приводить сами алгоритмы или код, это будет в следующих выпусках.
Особую роль выполняют прикладные алгоритмы, предназначенные для решения определённых прикладных задач. Алгоритм считается правильным, если он отвечает требованиям задачи (например, даёт физически правдоподобный результат), но если для некоторых исходных данных программа выдает ошибку, или вообще ничего не выдает (например, зацикливается), то в алгоритме есть ошибка и её надо исправлять.
Важную роль играют рекурсивные алгоритмы (алгоритмы, вызывающие сами себя до тех пор, пока не будет достигнуто некоторое условие возвращения). Начиная с конца XX — начала XXI века активно разрабатываются параллельные алгоритмы, предназначенные для вычислительных машин, способных выполнять несколько операций одновременно. Я не буду их никак по другому классифицировать, как это делают, допустим, учителя информатики — считаю, что этого читателю будет достаточно. Из определения итак все ясно.
Алгоритмы можно оценивать с разных позиций и разных точек зрения, но, наверное, самым основным критерием оценки будет быстродействие алгоритма (под быстродействием я понимаю время работы программы). Быстродействие нельзя определить только по одному виду кода, код должен работать, и, причем, работать с различными объёмами данных. Для оценки времени традиционно пользуются профилировщиком(profiler). Он загружает программу и достаточно точно измеряет время работы каждой подпрограммы.
Как правило, время работы программы (алгоритма) пропорционально объему обрабатываемых данных. Но при анализе алгоритма неудобно выражаться такими словесными конструкциями как: «Быстродействие алгоритма прямо пропорционально количеству элементов в третьей степени».  Для это есть более короткая и более удобная схема – О-нотация (bigOh notation). Эта нотация позволяет учитывать в функции f(n) лишь наиболее значимые элементы, отбрасывая второстепенные.
Например, в функции  f(n) = 2n2+ n – 5 при достаточно больших  n  компонента  n2  будет значительно превосходить остальные слагаемые, и поэтому характерное поведение этой функции определяется именно этой компонентой. Остальные компоненты можно отбросить и условно записать, что данная функция имеет оценку поведения (в смысле скорости роста ее значений) вида  О(n2). О-оценка позволяет разбить все основные функции на ряд групп в зависимости от скорости их роста:
1)       Постоянные функции типа О(1), которые с ростом n НЕ растут (в оценивании алгоритмов этот случай встречается крайне редко, но все-таки встречается!);
2)       Функции с логарифмической скоростью роста О(log(2n));
3)       Функции с линейной скоростью роста О(n);
4)       Функции с линейно–логарифмической скоростью роста О(n*log(2n));
5)       Функции с квадратичной скоростью роста О(n2);
6)       Функции со степенной скоростью роста  О(na) при а>2;
7)       Функции с показательной или экспоненциальной скоростью роста  О(2n);
8)       Функции с факториальной степенью роста  О(n!).
В этом списке функции упорядочены именно по критерию скорости роста: сначала идут медленнорастущие функции, потом – все более быстрорастущие.
Отсюда можно сделать несколько выводов:
· При выборе однотипных алгоритмов предпочтение (при прочих равных условиях) следует отдавать алгоритмам с наименьшей скоростью роста трудоемкости, поскольку они позволят за одно и то же время решить задачи с большей размерностью;
·   Если заранее известно, что размерность решаемых задач невелика, но зато число их повторений очень большое, имеет смысл рассмотреть возможность использования алгоритмов не с самой лучшей оценкой, поскольку при малых n “лучшие” алгоритмы могут вести себя хуже, чем “плохие” (это можно заметить по графику в области начала координат);
Как быть с оценкой трудоемкости программы в целом, если в программе используется несколько алгоритмов, решающих свои конкретные задачи? Есть два основных способа взаимодействия алгоритмов – последовательное и вложенное. При последовательном выполнении алгоритмов с оценками O(f1), O(f2), …, O(fk) общая трудоемкость определяется трудоемкостью алгоритма с максимальным значением:
O (программы) = Max (O(f1), O(f2), . . ., O(fk))

При вложенном выполнении общая трудоемкость есть произведение оценок вложенных друг в друга алгоритмов: O(программы) = O(f1)*O(f2)*O(f3).
При выборе алгоритма следует также учитывать, что при выполнении определенной задачи программа встретиться с тремя возможными случаями выполнения. Назовем их лучший, средний и худший случай.

При тестировании программы нельзя опираться на лучший случай, проверять необходимо средний, а в особенности худший случай, когда программе понадобится максимум времени и максимум ресурсов железа для выполнения поставленной задачи. Кстати о ресурсах, при проектировании приложения, всегда учитывайте, что программа будет выполняться на «древних» машинах, которые не располагают огромным пространством памяти.

Мой вам совет, если вы пишите небольшой софт для рядовых пользователей и распространяете его в интернете, а уж тем более если приложение сложное, многофункциональное и «прожорливое», то тестировать его необходимо на старых машинах, не надейтесь что у каждого потребителя стоят мощные вычислительные монстры. Также некоторые «прожорливые» алгоритмы, на некоторых компьютерах, будут вызывать, так называемую, пробуксовку (thrashing), о методах борьбы с которой я расскажу в следующих выпусках, а пока только базовые понятия.

Пробуксовка приложения вызванна, в первую очередь, самой операционной сиситемой, а в частносте страничной организацией памяти. Виртуальная память в 32-разрядной (Win32) системе с процессорами Pentium разделена на страницы по 4 Кб. При запуске приложения Win32 выделяет ему память, размер которой не много не мало 4ГБ. Весь этот огромный блок делится на более мелкие блоки, размерами по 4Кб, это и есть те самые страницы.

Очевидно, что физически ни одна операционная система не может выделить 4Гб память, поэтому когда физически память заканчивается ОС записывает физическую страницу на жесткий диск, этот процесс называется подкачкой или свопингом (swapping).

После этого, при обращании приложения к записанной на жесткий диск странице, на жесткий диск записывается другая, не нужная в данный момент страница, а необходимаяя записывается на место только что отправленной на жесткий деск. Вся эта операция занимает достаточно много времени и заставляет приложение пробуксовывать при обработке больших обьемов данных. Здесь я не буду рассказывать о структуре работы виртуальной памяти в отдельно взятых ОС, но если читателя заинтересовал данный вопрос, то информацию о структуре работы этого устройства он слегкостью найдет в Интернете. К нашему великому сожалению, универсального лекарства от пробуксовки не существует. Программист не может управлять конкретным расположением блоков памяти.

Так же о чем следует помнить при создании приложения, так это о выравнивании данных. Термин связан с работой процессора.  Я не буду освещать суть данного термина, лишь скажу, что необходимо убедиться, что переменные типа longint и указатели выровнены по четырехбайтовой или 32-битной границе. Иначе процессору потребуется достаточно большое количество времени для их чтения из кэша. Это может показаться трудным, непонятным, «страшным и лохматым». И, конечно, же вы спросите: «И как же это делается?», а я вам отвечу: «В наш век информационных технологий, это уже не важно». Дело в том, что в современных версиях Delphi компилятор это делает автоматически со всеми типами данных.
На этом я намереваюсь закончить статью. Я постарался дать вам все базовые знания, которые понадобятся вам в дальнейшем при конструировании приложений. Уже в следующей статье я начну знакомить вас с алгоритмами. 
Увы, продолжения никогда не будет.
Автор — Nikol05

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *