Для тестирования и определения времени выполнения алгоритмов поиска была написана специальная программа. Фактически она определяет системное время вначале перед, а затем и после выполнения кода. По результатам определения времени вычисляется время выполнения. Принимая во внимание, что в настоящее время компьютеры стали достаточно мощными, а часы системного времени характеризуются сравнительно низкой точностью, как правило, для более точной оценки быстродействия код выполняется несколько сот раз, а затем определяется среднее значение. (Кстати, эта программа была написана в среде 32-разрядной Delphi и не будет компилироваться под Delphi1, поскольку она выделяет память для массивов из кучи, которая превышает граничное для Delphi1 значение 64 Кб.)
Эксперименты по оценке быстродействия алгоритмов проводились различными способами. Сначала для обоих алгоритмов было определено время, необходимое для поиска фамилии "Smith" в массивах из 100, 1000, 10000 и 100000 элементов, которые содержали искомый элемент. В следующей серии экспериментов осуществлялся поиск того же элемента в массивах того же размера, но при отсутствии в них искомого элемента. Результаты экспериментов приведены в таблице 1.1.
Таблица 1.1. Времена выполнения последовательного и бинарного поиска
Как видно из таблицы, эксперименты показали очень интересные результаты. Время выполнения последовательного поиска пропорционально количеству элементов в массиве. Таким образом, можно сказать, что характеристики выполнения последовательного поиска линейны.
Результаты выполнения бинарного поиска проанализировать сложнее. Может даже показаться, что из-за очень быстрого выполнения алгоритма при определении времени мы столкнулись с проблемой потери точности. Очевидно, что зависимость между количеством элементов в массиве и временем выполнения алгоритма не является линейной. Но по приведенным данным трудно определить тип зависимости.
Эксперименты были проведены повторно. При этом времена выполнения умножались на коэффициент 100.
Таблица 1.2. Повторное тестирование бинарного поиска
Эти данные более достоверны. Из них видно, что десятикратное увеличение количества элементов в массиве приводит к увеличению времени выполнения на определенную постоянную величину (примерно на 0.5). Это логарифмическая зависимость, т.е. время бинарного поиска пропорционально логарифму количества элементов в массиве.
(Если вы не математик, то вам будет не так легко это понять. Вспомните из своих школьных дней, что для вычисления произведения двух чисел можно вычислить их логарифмы, сложить их, а затем определить антилогарифм суммы. Поскольку в рассматриваемых экспериментах количество элементов умножается на 10, то в логарифмической зависимости это будет эквивалентно прибавлению константы. Как раз это мы и видим в результатах экспериментов: для каждого последующего массива время увеличивается на 0.5.)
Что мы узнали из результатов проведенных экспериментов? Во-первых, теперь мы знаем, что единственным методом определения быстродействия алгоритма является оценка времени его выполнения.
----
В общем случае, единственным методом определения быстродействия отдельной части кода является оценка времени ее выполнения. Это справедливо как в отношении широко известных алгоритмов, так и в отношении алгоритмов, разработанных лично вами. Не нужно предполагать, просто измерьте время выполнения.
----
Во-вторых, мы определили, что по своей природе последовательный поиск является линейным, а бинарный поиск - логарифмическим. Если быть поближе к математике, то можно взять эти статистические результаты и теоретически доказать их справедливость. Тем не менее, в этой книге мы не будет перегружать текст математическими выкладками. Можно найти немало книг, в которых приведены эти выкладки (см., например, тома "Фундаментальные алгоритмы на С++" и "Фундаментальные алгоритмы на С" Роберта Седжвика, вышедшие в свет в издательстве "Диасофт").
Для выражения характеристик быстродействия удобно иметь более компактное определение, нежели "быстродействие алгоритма X пропорционально количеству элементов в третьей степени" или что-нибудь в этом роде. В вычислительной технике уже есть короткая и более удобная схема - О-нотация (big-Oh notation).
В этой нотации используется специальная математическая функция от n, т.е. количества элементов, которой пропорционально быстродействие алгоритма. Таким образом, мы говорим, что алгоритм принадлежит к классу O(f(n)), где f(n) - некоторая функция от n. Приведенное обозначение читается как "О большое от f(n)" или, менее строго, "пропорционально f(n)".
Например, наши эксперименты показали, что последовательный поиск принадлежит к классу O(n), а бинарный - к классу O(log(n)). Поскольку для положительных чисел n log(n) < n, можно сделать вывод о том, что бинарный поиск всегда быстрее, чем последовательный. Тем не менее, немного ниже будут приведены несколько замечаний, касающихся выводов, сделанных из О-нотации.
О-нотация проста и удобна. Предположим, что экспериментальным путем было определено, что алгоритм X принадлежит к классу O(n(^2^) + n). Другими словами, его быстродействие пропорционально n(^2^) + n. Под словом "пропорционально" понимается, что можно найти такую константу к, для которой
Быстродействие = к * (n(^2^) + n)
Из приведенного уравнения видно, что умножение математической функции внутри скобок в О-нотации на константу не оказывает никакого влияния на смысл нотации. Так, например, O(3*f(n)) эквивалентно O(f(n)), поскольку 3 можно без последствий вынести как коэффициент пропорциональности, который мы игнорируем.
Если величина n при тестировании алгоритма X достаточно велика, можно сказать, что влияние члена поглощается членом "n(^2^). Другими словами, при больших значениях n алгоритм O(n(^2^)+n) эквивалентен алгоритму O(n(^2^)). То же можно сказать и для n более высоких степеней. Так, для достаточно больших n влияние члена n(^2^) будет поглощено влиянием члена n(^3^). В свою очередь, влияние члена log(n) будет поглощаться влиянием члена n и т.д.
Из приведенного примера видно, что О-нотация подчиняется очень простым арифметическим правилам. Давайте предположим, что есть алгоритм, который выполняет несколько различных задач. Первая задача сама по себе принадлежит к классу О(n), вторая - к классу O(n(^2^)), а третья - к классу O(log(n)). Необходимо определить быстродействие алгоритма в целом. Ответом будет O(n(^2^)), поскольку к этому классу принадлежит доминантная часть алгоритма.
В этом и заключается первое замечание, касающееся выводов, следующих из О-нотации. Значения О большого являются репрезентативными для больших значений n. Для маленьких значений О-нотация не имеет смысла, а на общий результат оказывают влияние другие члены нотации. Например, предположим, что проводилось тестирование двух алгоритмов. На основе статистических данных были выведены следующие зависимости:
Быстродействие первого алгоритма = k1 * (n + 100000)
Быстродействие второго алгоритма = k2* n(^2^)
Пусть константы kl и k2 сравнимы по величине. Какой алгоритм лучше использовать? Если следовать О-нотации, то предпочтительнее будет первый алгоритм, поскольку он принадлежит к классу О(n). Тем не менее, если известно, что значение n в реальных условиях не будет превышать 100, более эффективным окажется второй алгоритм.
Таким образом, алгоритм нужно выбирать и с учетом его назначения - не только на основании О-нотации, но принимая во внимание время выполнения при средних значениях количества элементов (или, если угодно, условий использования), на которых алгоритм будет применяться. Следовательно, выбор алгоритма должен осуществляться только на основе измерения профилировщиком времени выполнения вашего приложения для ваших данных. Не полагайтесь ни на какие книги (в том числе и на эту), верьте только измеренному времени.
Помимо всего прочего, необходимо рассмотреть еще один вопрос. О-нотация относится к среднему случаю. Вернемся к нашим экспериментам, связанным с поиском элемента в массиве. Если бы фамилия "Smith" всегда была первым элементом в массиве, последовательный поиск был бы быстрее бинарного, - искомый элемент был бы обнаружен при первом же выполнении цикла. Такая ситуация известна под названием лучший случай. Для нашего примера в О-нотации ее можно представить как O(1) (т.е. выполнение алгоритма занимает одно и то же время независимо от количества элементов в массиве).
Если бы фамилия "Smith" всегда была последним элементом в массиве, последовательный поиск был бы очень медленным. Такая ситуация известна под названием худший случай. В нашем примере ее можно представить как О(n), точно так же, как и для среднего случая.
Несмотря на то что для бинарного поиска быстродействие в лучшем случае (искомый элемент всегда находится в средине массива) равно быстродействию в лучшем случае для последовательного поиска, тем не менее, его быстродействие в худшем случае намного выше. Собранные нами статистические данные при поиске элемента, которого нет в массиве, являются значениями для худшего случая.
В общем, при выборе алгоритма следует учитывать значения в О-нотации для среднего и худшего случаев. Лучшие случаи, как правило, не интересны, поскольку программисты всегда более обеспокоены "граничными" условиями, по которым и будут судить о быстродействии приложения.
Таким образом, мы увидели, что О-нотация - очень ценное средство оценки быстродействия различных алгоритмов. Кроме того, следует помнить, что О-нотация в общем случае имеет смысл только для больших n. Для небольших n выбор алгоритма лучше осуществлять на основе статистических данных о времени его выполнения. Единственным достоверным методом оценки эффективности алгоритма является определение времени его работы. Поэтому не гадайте, а интенсивно используйте профилировщик.
В обсуждении быстродействия алгоритмов мы до сих пор не затрагивали вопросов, касающихся операционной системы и оборудования компьютера, на котором выполняется реализация алгоритма. О-нотация справедлива только для какой-то виртуальной вычислительной машины, в которой, например, нет никаких узких мест в операционной системе или оборудовании. К сожалению, мы живем и работаем в реальном мире, и наши приложения и алгоритмы будут выполняться на реальных физических компьютерах. Поэтому при анализе алгоритмов следует учитывать и данный фактор.
Первым узким местом быстродействия приложения является страничная организация виртуальной памяти. Его легче понять на примере 32-разрядных приложений. 16-разрядные приложения тоже страдают от тех же проблем, но сама механика их возникновения разная. Обратите внимание, что в этом разделе мы будем говорить языком непрофессионалов, - целью раздела является обсуждение концептуальной информации, достаточной для понимания принципов происходящего, а не детальное рассмотрение системы страничной памяти.
При запуске приложения под управлением современной 32-разрядной операционной системы ему для кода и данных предоставляется блок виртуальной памяти, размером 4 Гб. Очевидно, что операционная система не дает физически эти 4 Гб из оперативной памяти (ОЗУ); понятно, что далеко не каждый может себе позволить выделить лишние 4 Гб ОЗУ под каждое приложение. Фактически предоставляется пространство логических адресов, по которым, теоретически, может храниться до 4 Гб данных. Это и есть виртуальная память. На самом деле ее нет, но если мы все делаем правильно, операционная система может предоставить нам физические участки памяти, если возникнет такая необходимость.
Виртуальная память разбита на страницы. В системах Win32 с процессорами Pentium размер одной страницы составляет 4 Кб. Следовательно, Win32 разбивает блок памяти объемом 4 Гб на страницы по 4 Кб. При этом в каждой странице содержится небольшой объем служебной информации о самой странице. (память в операционной системе Linux работает примерно таким же образом.) Здесь содержатся данные о том, занята страница или нет. Занятая страница - это страница, в которой приложение хранит данные, будь то код или реальные данные. Если страница не занята, ее нет вообще. Любая попытка сослаться на нее вызовет ошибку доступа.
Далее, в служебную информацию входит ссылка на таблицу перевода страниц. В типовой системе с 256 Мб памяти (через несколько лет эта фраза, наверное, будет вызывать смех) доступно только 65536 физических страниц. Таблица трансляции страниц связывает отдельную виртуальную страницу памяти приложения с реальной страницей, доступной в ОЗУ. Таким образом, при попытке доступа приложения к определенному адресу операционная система выполняет трансляцию виртуального адреса в физический адрес ОЗУ.
Если в системе Win32 запущено несколько приложений, неизбежно будут возникать моменты, когда все физические страницы ОЗУ заняты, а одному из приложений требуется занять новую страницу. Но это невозможно, поскольку свободных страниц нет. В таком случае операционная система записывает физическую страницу на жесткий диск (этот процесс называется подкачкой или свопингом (swapping)) и отмечает в таблице трансляции, что страница была записана на диск, после чего физическая страница помечается как занятая приложением.
Все это хорошо до тех пор, пока приложение, которому принадлежит страница на диске, не пытается обратиться к ней. Процессор определяет, что физическая страница уже недоступна и возникает ошибка отсутствия страницы (page fault). Операционная система принимает управление на себя, записывает другую страницу на диск, освобождает физическую страницу, записывает на освободившееся место запрашиваемую страницу и продолжает выполнение приложения. Само приложение ничего не знает о происходящем внутри операционной системы процессе. Оно, например, считывает первый байт страницы памяти, и именно это (в конечном счете) происходит.
Все описанное выше в 32-разрядной операционной системе происходит постоянно. Физические страницы записываются на диск и считываются с диска. При этом изменяются таблицы трансляции страниц. В большинстве случаев простой пользователь ничего не замечает, за исключением одной ситуация. И эта ситуация называется пробуксовка (thrashing).
Пробуксовка может негативно сказаться на вашем приложении, превращая его из высокоэффективной оптимизированной программы в медленную и ленивую. Предположим, что существует приложение, которое требует большого объема памяти, скажем, например, половину всей имеющейся в компьютере физической памяти. Оно создает большие массивы крупных блоков, выделяя память из кучи. Такое выделение приведет к тому, что будут заниматься новые страницы, а старые, скорее всего, будут записываться на диск. Затем приложение считывает эти большие блоки, начиная с начала массива и в направлении его конца. Операционная система при необходимости будет считывать запрашиваемые страницы из ОЗУ. При этом никаких проблем возникать не будет.
А теперь представим себе, что приложение считывает блоки в произвольном порядке. Скажем, сначала оно считывает данные из блока 56, затем из блоков 123, 12, 234 и т.д. В таком случае вероятность возникновения ошибки отсутствия страницы увеличивается. При этом все большее и большее количество страниц будет записываться на диск и считываться с диска. Индикатор работы диска будет гореть почти постоянно, а скорость работы приложения упадет. Это и есть пробуксовка - непрерывный обмен страницами между диском и памятью, вызванный запросами приложения страниц в произвольном порядке.
В общем случае лекарства от пробуксовки нет. Большую часть времени блоки памяти выделяются из программы динамического распределения памяти Delphi. Кроме того, программист не может управлять конкретным расположением блоков памяти. Может случиться, например, что связанные блоки данных хранятся в разных страницах. (Здесь под словом "связанные" понимается блоки памяти, данные из которых, вероятно, будут считываться одновременно, поскольку сами данные связаны.) Одним из методов снижения риска возникновения пробуксовки является использование отдельных куч для выделения памяти для структур и данных разных приложений. Но алгоритм такого выделения в настоящей книге не приводится.
Рассмотрим пример. Предположим, что мы выделили память под элементы объекта TList. Каждый из элементов содержит, по крайней мере, одну строку, память для которой выделяется из кучи (например, мы пользуемся 32-разрядным Delphi и элемент использует длинные строки). А теперь представим себе, что приложение уже проработало некоторое время, и элементы в объекте TList неоднократно добавлялись и удалялись. Вполне возможно, что экземпляр TList, его элементы и строки элементов распределены по разным страницам памяти. Теперь при последовательном считывании элементов объекта TList от начала до конца приложение будет обращаться ко многим страницам, что приведет к активному обмену страницами между диском и памятью. Если количество элементов достаточно мало, все страницы, относящиеся к данному приложению, могут находиться в памяти. Но если в объекте TList элементов насчитывается несколько миллионов, при их считывании приложение может породить состояние пробуксовки.
Самое время обсудить еще одну концепцию - локальность ссылок. Этот принцип представляет собой метод представления приложений, который помогает свести вероятность возникновения пробуксовки к минимуму. Это понятие предполагает, что связанные данные должны находиться в виртуальной памяти как можно ближе друг к другу. Если принцип локальности ссылок соблюдается, при считывании части данных другую их часть можно будет найти на соседних страницах памяти.
Например, массив записей имеет высокий уровень локальности ссылок. Так, элемент с индексом 1 в памяти находится рядом с элементом с индексом 2 и т.д. Если приложение последовательно считывает все записи массива, локальность ссылок будет очень высокой. Обмен страницами между диском и памятью будет минимальным. Экземпляр объекта TList, содержащий указатели на тот же тип записей, несмотря на то, что это тоже массив, фактически содержащий те же данные, будет иметь низкий уровень локальности ссылок. Как было показано ранее, каждый элемент такого массива может находиться на отдельной странице. Таким образом, последовательное считывание элементов вызовет обмен данными между диском и памятью. Связанные списки (см. главу 3) также обладают низким уровнем локальности ссылок.
Существуют специальные методы повышения уровня локальности ссылок для различных структур данных и алгоритмов, и некоторые из них будут рассмотрены в настоящей книге. К нашему сожалению, диспетчер динамического распределения памяти Delphi является слишком общим. Программист не может вынудить Delphi выделить память под серию элементов из одной страницы. Еще хуже тот факт, что все объекты представляют собой экземпляры, память для которых выделяется из кучи. Возможность выделения памяти для отдельных объектов из определенных страниц позволила бы избежать многих неприятностей. (В действительности это возможно за счет подмены метода класса Newlnstance, но подмену приходится делать для всех классов, для которых нужна такая возможность.)
До сих пор мы говорили о локальности ссылок в смысле расстояния ("один объект находится в памяти рядом с другим объектом"), но локальность ссылок можно трактовать и по отношению ко времени. Это означает, что если элемент недавно использовался, он скоро будет использоваться снова, или, скажем, элемент X всегда используется вместе с элементом Y. Воплощением локальности ссылок во времени является кэш-память. Кэш-память (cache) представляет собой небольшой блок памяти для некоторого процесса, содержащий элементы, которые использовались недавно. При каждом использовании элемента он копируется в кэш-память. Если кэш заполнен, при удалении элементов применяется алгоритм с удалением наиболее давно использованных элементов (least recently used, LRU), по которому элемент, который давно не использовался, замещается недавно использованным элементом. Таким образом, кэш-память содержит несколько близких в пространственном смысле элементов, которые, помимо всего прочего, близки и в смысле времени их использования.
Обычно кэш-память применяется для элементов, которые хранятся на медленных устройствах. В качестве классического примера можно привести дисковый кэш. Тем не менее, теоретически кэш виртуальной памяти мог бы работать точно таким же образом, особенно с приложениями, которые требуют большого объема памяти и используются на вычислительных машинах с небольшими объемами ОЗУ.