Эврика! Дом творческих и вдумчивых людей
Добро пожаловать на первый в Латвии мультитематический и межвузовский научный портал!

Сделать стартовой
Добавить в избранное
Контакты
 
   Главная      Эврика      Библиотека      Досуг      Контакты     БДС  

Библиотека : Публикации латвийских ученых : Программирование





Павел Гуданец

Повышение быстродействия обработки массивов

 

 

1.       Введение

В настоящее время разработано множество методов поиска элементов в массиве и их сортировки [1]. В данной статье предложен ряд алгоритмов, которые повышают быстродействие поиска и сортировки:

1)       алгоритм поиска в произвольном массиве, использующий мультипликативный критерий

2)       алгоритм поиска в упорядоченном массиве методом аппроксимации

3)       техника избежания логических сравнений, которая позволяет увеличить скорость некоторых сортировок и находить экстремумы в массиве за минимальное время

4)       концепция сложной организации данных в многомерном массиве

Все эти идеи объединены общим принципом, который составляет их суть: мы добиваемся более быстрого и эффективного решения самых разных задач с помощью некоторых математических приемов. Эти хитроумные средства – своего рода толика волшебства в варево стандартных логических методов. Фактически речь идет о формировании особого стиля программирования, возможности которого далеко не исчерпываются настоящей статьей. Важно подчеркнуть, что эффективность предлагаемых методов во многом зависит от архитектуры используемой машины. И это совершенно естественно: техническая реализация ЭВМ должна приспосабливаться к логике программ и наиболее эффективным решениям, а не наоборот.

Работа происходит на одномерном массиве M[1..N], который состоит из N неповторяющихся элементов (ключей). Через x обозначен искомый ключ.

 

2. Алгоритм поиска в массиве, использующий мультипликативный критерий

Идея алгоритма. Поскольку в неотсортированном массиве у нас нет никаких критериев для определения порядкового номера элемента, совпадающего с ключом x, единственным способом поиска является последовательный перебор. Однако он может быть улучшен за счет того, что на каждом шаге цикла будет проверяться на равенство с x не один элемент, а сразу несколько. Для этого достаточно воспользоваться следующим правилом: выражение (M[1]-x)*(M[2]-x)*…*(M[d]-x) обращается в нуль тогда и только тогда, когда хотя бы один из элементов M[1], M[2], …, M[d] равен x.

В рассмотренном ниже примере алгоритма, записанном на языке Pascal, имеем: количество рассматриваемых за один шаг элементов d равно 4; для сокращения количества сравнений в операторе цикла используется барьер – дополнительный элемент M[n+1], в который записывается искомый ключ. Очевидно, что объем массива должен быть не меньше n+d, где n – количество зарезервированных ячеек, d – количество рассматриваемых за один шаг элементов, иначе возможна ошибка выхода за границы массива.

 

M[N+1]:=x;

i:=4;

While (M[i-3]-x) * (M[i-2]-x) * (M[i-1]-x) * (M[i]-x) <> 0 do i:=i+4;

if M[i-3]=x then i:=i-3

                 else if M[i-2]=x then i:=i-2

                                        else if M[i-1]=x then i:=i-1;

if i<N+1 then Writeln('Порядковый номер элемента: ',i)

              else Writeln('Элемента нет в массиве');

 

Данный алгоритм имеет ту же временную сложность, что и последовательный перебор. При этом эффективность предложенного алгоритма во многом зависит от того, будут ли в используемом компьютере операции вычитания и умножения осуществляться быстрее логического сравнения. Еще лучше, если язык программирования позволяет, использовать побитовое исключающее ИЛИ между x и M[i] вместо вычитания и вместо умножения непобитовое И.

 

3. Алгоритм поиска в упорядоченном массиве методом аппроксимации

Идея алгоритма. Алгоритм основан на том, что упорядоченный по возрастанию массив содержит элементы, расположенные в интервале [M[1]; M[N]]. Искомое число x также предположительно находится в нем. Припишем интервалу [M[1]; M[N]] своего рода процентную шкалу, разделив его на одинаковые участки. Если сопоставить x с числами M[1] и M[N], то можно приблизительно установить тот «процент», на который приходится x. Чем равномернее распределены элементы в массиве или эквивалентные им точки на отрезке, тем точнее приближение. Ниже представлен укрупненное описание метода:

1.        Если x меньше M[1] или больше M[N], поиск завершен.

2.        Помещаем в ячейку N+1 значение x+1 в качестве барьера.

3.        Вычисляем приблизительное положение x в диапазоне [M[1]; M[N]] по формуле

 

где модульные скобки означают округление результата до целой части и изменение знака на плюс, если результат отрицательный. Если индексация массива начинается с произвольного числа С, следует использовать формулу вида:

4.        Увеличиваем i, пока M[i]<x.

5.        Уменьшаем i, пока M[i]>x.

6.        Если M[i]=x, элемент найден, иначе элемента в массиве нет.

 

Реализация рассмотренного алгоритма на языке Pascal имеет вид:

 

if (x<M[1])or(x>M[N]) then Writeln ('Элемента нет в массиве')

else begin

M[N+1]:=x+1;

i:=Abs(Round( (N/(M[N]-M[1]+1))*(x-M[1])+1 ));

while M[i]<x do i:=i+1;

while M[i]>x do i:=i-1;

if M[i]=x then Writeln ('Индекс искомого элемента: ',i)

              else Writeln ('Элемента нет в массиве');

end;

 

Примечания:

1. Если N и x – большие числа, произведение N*(x-M[1]) может дать результат, выходящий за пределы разрядной сетки объявленного типа. Поэтому рекоммендуется сначала производить деление, как это показано в представленном алгоритме. В крайнем случае можно несколькими итерациями бинарного поиска сократить диапазон, в котором предположительно находится x. Это уменьшит входящие в формулу значения.

2. Быстродействие алгоритма «аппроксимацией» зависит только от степени равномерности распределения элементов в массиве. Так, поиск в массиве, имеющем достаточно равномерное распределение ключей1, выполняется в 2-3 раза быстрее бинарного поиска уже для n=100. В отличие от поиска хешированем рассмотренный алгоритм не требует выделения дополнительной памяти под хеш-массив.

 

4. Способ уменьшить количество логических сравнений

При решении многих задач встречается следующая необходимость: сравнить значения в i и j ячейках массива M; если при этом оказывается, что порядок возрастания элементов в массиве нарушен (например, при i>j M[i]<M[j]), требуется совершить перестановку элементов. При этом используется обычная конструкция логического сравнения. На этом основаны все обменные сортировки. Возникает желание придумать способ, который позволял бы совершать нужные перестановки, избегая сравнений.

Для решения задачи потребуется одна булева переменная R и массив C, который состоит всего из двух ячеек. Далее приведено описание этого алгоритма:

1.        Рассчитываем разность M[i]-M[j]. Если разность меньше нуля (элементы нарушают порядок), то переменная R принимает значение 1, если разность больше или равна нулю, R:=0. Если число хранится в знаковом формате (это зависит от используемого компилятора или интерпретатора), то можно сразу вычислить значение R - считав бит, хранящий знак числа. В противном случае потребуется использовать сложную математическую формулу - и эффективность алгоритма теряется.

2.        Записываем сравниваемые значения в массив C следующим образом:

C[1+R]:=M[j];

С[2-R]:=M[i];

3.        Считываем их обратно в ячейки исходного массива M:

M[j]:=C[1];

M[i]:=C[2];

 

Модель процесса представлена на рис. 1:

 


Рис. 1

Как видим, если R=0, то элементы считаются обратно в те же ячейки, из которых они были записаны; в противном случае они крест-накрест записываются в C и при обратном считывании меняются местами2.

Схожая конструкция логического сравнения с присваиванием используется также в сортировке выбором и некоторых других сортировках, а также при поиске экстремумов-значений в массиве, как это показано в следующем примере:

 

max:=M[1];

for i:= 2 to N do

 if M[i]>max then max:=M[i];

Writeln('Наибольшее значение: ',max);

           

Эти алгоритмы тоже могут быть улучшены описанным методом. Временная сложность поиска экстремума должна снизиться благодаря этому почти вдвое:

 

C[2]:=M[1];

for i:=2 to N do

 begin

   R:=znak(C[2]-M[i]);

   C[1+R]:=M[i];

 end;

Writeln('Наибольшее значение: ',C[2]);

 

Как видим, если C[2]<M[i], то R=1, и поэтому вычисляется новый максимум C[2]:=M[i], иначе неподходящее значение записывается в другую ячейку: C[1]:=M[i].

Для одновременного поиска максимума и минимума рекомендуется использовать массив C из трех ячеек. В C[1] отфильтровываются минимумы, в С[3] – максимумы; C[2] служит своего рода «мусорником», в который скидываются все неподходящие значения.

 

5. Применение многомерных массивов для организации данных

В неотсортированном массиве мощности n, чтобы найти n-ый элемент, необходимо n шагов, в отсортированном - log n; очевидно, что большая скорость достигается благодаря появлению внутренней логики в распределении элементов. Также очевидно, что чем сложнее эта внутренняя организация, тем быстрее должен осуществляться поиск, и - если мы правильно приступим к конструированию такого сложно организованного массива, то и сортировка тоже. Выигрывая в скорости, мы не теряем в других параметрах: количестве памяти и сложности кода. Такой эффект достигается благодаря тому, что у элемента появляется строго заданное место в универсуме массива.

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

Чтобы продемонстрировать идею, рассмотрим простой случай двух измерений организации. Для этого создадим массив вида:

 

M: array [0..t-1] of array of Integer;

 

Первое измерение массива делит его на t подмассивов (желательно объявить их динамическими), и принадлежность элемента x одному из них определяется остатком от деления x mod t. Таким образом распределяя элементы, мы получаем t групп, каждую из которых в свою очередь упорядочиваем по возрастанию - это образует второе измерение внутренней организации массива.

При создании массива в нулевую ячейку каждого подмассива запишем 0. Нулевая ячейка будет хранить значение длины данного подмассива - чтобы ее не надо было рассчитывать с помощью функции при каждой необходимости. Новый элемент x запишется в ячейку [x mod t, max+1], где max - значение в нулевой ячейке, после чего max увеличивается. Чтобы узнать количество элементов во всем массиве, достаточно просуммировать значения в нулевых ячейках.

Поиск элемента x осуществляется очевидным образом:

1.        Определяем x mod t

2.        Методом аппроксимации или бинарным поиском ищем x в нужном подмассиве

Таким образом, поиск происходит в среднем в t раз (!) быстрее, чем при обычной организации массива, а после каждого добавления элемента нет надобности сортировать весь массив от начала до конца, а только t-ую его часть.

 

6. Выводы

Первые два алгоритма, разработанные автором, внедрены в учебный процесс при прохождении курса "Структуры данных и алгоритмы их обработки" [2].

Дальнейшее направление работы заключается в исследовании такой характеристики массивов как степень равномерности распределения элементов. Учет этой степени полезен при решении различных задач, например, в алгоритме поиска методом аппроксимации, при поиске барьера в алгоритме сортировки Хоора (чем равномернее распределение, тем ближе к идеальному значению барьера будет среднее арифметическое выборки из массива), и т.д. Следует разработать методы оценки и корректировки неравномерностей в распределении элементов. Эта необходимость сравнима с необходимостью балансировки деревьев для ускорения поиска.

 

7.Примечания

1.        Тестирование алгоритма проходило на массивах, созданных генератором псевдо-случайных чисел. Он создает последовательности как раз с подходящей равномерностью распределения.

2.        Есть другой способ, вот его описание на языке Pascal:

R:=znak(M[i]-M[j]);

C[1]:=M[j];

C[2-R]:=M[i];

M[i]:=M[i-R];

M[j]:=C[1];

Очевидно, этот способ годится только для случая j=i-1, то есть только для сортировки пузырьком, кроме того, он сложнее для восприятия. Поэтому рекомендуется использовать первый способ.

 

8. Литература

1.        Вирт Н. Алгоритмы + структуры данных = программы. - Москва: Мир, 1985. - 406 с.

2.        Копытов Е., Иванова С., Птицына И. Структуры данных и их обработка на компьютере. - Рига: Институт Транспорта и Связи, 2003. - 128 с.


2003.

Источник: Творческий инСайт Павла Гуданца



Добавлено: 2005-05-25
Посещений текста: 5073

[ Назад ]





© Павел Гуданец 2004-2017 гг.
 инСайт

При информационной поддержке:
Институт Транспорта и Связи