Анализ структур данных. Часть 1. Введение в структуры данных
Страница 2. Анализ эффективности структур данных
Страница 2 из 4

Анализ эффективности структур данных

В процессе размышления над конкретным приложением или программистской задачей многие программисты (включая меня) находят более интересным процесс написания алгоритма для решения некоторой проблемы или добавление новой "навороченной" функциональности в приложение с тем, чтобы сделать его более удобным для пользователей. При этом редко, если вообще когда-либо, вы услышите восхищенные возгласы о том, какая структура данных используется в приложении. Хотя, правильный выбор структур данных для конкретного алгоритма может очень значительно повлиять на его производительность. Типичный пример – это поиск элемента в структуре данных. В случае использования обычного массива, этот процесс занимает время пропорциональное числу элементов массива. Двоичные деревья поиска или скип-списки, требуют сублинейного времени. При осуществлении большого количества поисков выбор структуры данных имеет решающее значение для скорости работы приложения, которое может быть измерено секундами, а иногда и минутами.

А раз структура данных, используемая в алгоритме может значительно повлиять на скорость его работы, важно иметь строгую процедуру сравнения эффективности различных структур данных. Нас, как разработчиков, использующих структуры данных, главным образом интересует то, как изменяется эффективность структуры данных с ростом объема хранимой информации. А именно, как влияет добавление каждого нового элемента, на скорость выполнения операций над данными.

Рассмотрим пример, в котором наша программа использует метод System.IO.Directory.GetFiles(path) для получения списка всех файлов в заданнном каталоге в виде строкового массива. Теперь, представьте, что вам захотелось узнать, есть ли среди полученных файлов XML-файл (т.е. файл с расширением .xml). Возможное решение – это просмотреть последовательно весь массив и при нахождении xml-файла изменить значение некоторого флага. Код будет выглядеть, например, так:

using System;
using System.Collections;
using System.IO;
public class MyClass
{
 public static void Main()
 {
 string [] fs = Directory.GetFiles(@"C:\Inetpub\wwwroot");
 bool foundXML = false;
 int i = 0;
 for (i = 0; i < fs.Length; i++)
 if (String.Compare(Path.GetExtension(fs[i]), ".xml", true) == 0)
 {
 foundXML = true;
 break;
 }
 
 if (foundXML)
 Console.WriteLine("XML file found - " + fs[i]);
 else
 Console.WriteLine("No XML files found.");
 
 }
}

Нетрудно заметить, что в наихудшем случае, когда XML-файл является последним элементом или когда он вообще отсутствует, нам придется ровно 1 раз просмотреть каждый элемент массива. Для анализа эффективности массива при сортировке мы должны задать себе следующий вопрос: "Допустим, у нас есть массив из n элементов. Если мы добавим один элемент в массив, так что их количество станет равным n + 1, каково будет при этом новое время исполнения алгоритма?". (Термин время исполнения, вопреки своему названию, не означает абсолютное время исполнения программы в секундах, а скорее, он означает число шагов, которое должна совершить программа для выполнения данной конкретной задачи. При работе с массивами количеством таких шагов будет количество раз, которое программа считывает элементы массива). Для нахождения конкретного значения элемента массива нам потенциально придется посетить все его элементы. Таким образом, если у нас есть n + 1 элемент, нам потребуется выполнить n + 1 проверок. Это означает, что время поиска в массиве линейно зависит от числа его элементов.

Тип оценок, рассматриваемых нами называется асимптотическими оценками, поскольку мы анализируем, как эффективность структуры данных изменяется при объме хранящихся данных, стремящемся к бесконечности. В асимптотическом анализе обычно используют обозначение "О-большое". С помощью данного обозначения сложность поиска в массиве можно записать, как O(n). Здесь n – размер массива, а фраза "сложность поиска в массиве зависит от числа его элементов как O(n)означает, что число шагов, которые требуются для нахождения элемента массива линейно зависит от его размера. Т.е. с ростом числа элементов массива количество шагов, необходимых для осуществления поиска будет пропорционально размеру массива. Более систематическим методом вычисления асимптотического времени исполнения блока кода будет следующая несложная процедура:

  1. Определите действия, составляющие время исполнения алгоритма. Как уже было упомянуто, в случае массива, рассматриваемыми действиями будут чтение и запись элементов массива. Эти действия могут быть другими для других структур данных. Обычно нам хочется рассматривать действия, которые несут смысл на уровне структуры данных, а не простейшие атомарные операции, выполняемые компьютером. Например, в фрагменте кода, приведенном выше, я вычислял время исполнения, подсчитывая лишь то, сколько раз необходимо получать доступ к элементам массива, не принимая во внимание время, необходимое для создания и инициализации переменных или проверки на равенство двух строк.
  2. Найдите в коде строчки, в которых выполняются действия, которые вы подсчитываете. Напишите 1 напротив каждой такой строчки.
  3. Для каждой строчки, рядом с которой вы написали 1, проверьте, не входит ли она в цикл. Если да, то умножьте эту единичку на максимальное число итераций, которое может быть выполнено в цикле. Если у вас есть несколько вложенных циклов, умножайте последовательно на максимальное число итераций для каждого цикла.
  4. Среди чисел, записанных вами отыщите максимальное. Это и будет время исполнения.

Давайте попробуем применить этот метод к фрагменту кода, приведенному выше. Мы уже выяснили, что действия, которые нас интересуют и которые мы будем подсчитывать – это доступ к элементам массива. Переходя к пункту 2, замечаем что у нас присутствуют 2 строчки в которых мы получаем доступ к элементам массива fs — как параметр метода String.Compare() и в методе Console.WriteLine(). Итак, ставим пометку 1 напротив каждой из этих строк. После этого переходим к пункту 3 и замечаем, что доступ к fs в методе String.Compare()происходит внутри цикла, которsq исполняется максимум n раз (где n – размер массива). Итак, зачеркиваем единичку в цикле и заменяем ее на n. В конце мы видим, что максимальное значение - это n, а значит время исполнения блока кода можно записать как O(n).

O(n) или линейное время – это лишь один из бесконечного числа возможных вариантов асимптотического времени исполнения программы. Среди других вариантов, например, O(log2 n), O(n log2 n), O(n2), O(2n) и так далее. Даже не углубляясь в математические дебри асимптотического анализа, понятно, что чем меньше порядок члена в скобках O(*), тем больше эффективность рассматриваемой структуры данных. Например, программа, выполняющаяся за логарифмическое время O(log n) более эффективна, чем программа, выполняющаяся за линейное время O(n), поскольку при больших n справедливо неравенство log n < n.

Примечание. В случае если вам необходимо краткое напоминание из области математики, равенство loga b = y эквивалентно ay = b. Таким образом, log2 4 = 2, т.к. 22 = 4. Аналогично, log2 8 = 3, т.к. 23 = 8. Очевидно, что log2 n возрастает гораздо медленнее, чем само n. Например, когда n = 8, log2 n = 3. В Части 3 мы рассмотрим двоичные деревья, поиск в которых осуществляется за время O(log2 n).

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