Ф.Брукс
В настоящее время задача поиска встречаются во многих приложениях. Программа проверки правописания ищет слово в словаре, сервер ищет имя узла в свой базе данных, чтобы определить его IP-адрес, поиск абонента в телефонном справочнике и т. д. Можно привести множество примеров, где используется поиск в наборе данных для получения необходимой информации. Рассмотрим задачу поиска в наборе данных, а точнее ее постановку, выбор подходящей структуры данных для ее решения, и оценки эффективности работы каждого из способов решения.
Задача.
Секретная корпорация, занимающаяся поиском инопланетных жизненных форм обнаружила на одной из планет созвездия Альфа живые организмы. Она приняла решение вести наблюдение за развитием и изменением численности организмов, с этой целью на орбиту планеты был послан спутник - наблюдатель , который мог следить за изменениями численности организмов. Недостаток этого "наблюдателя" в том, что он может отслеживать изменения только на той территории планеты, которая находиться непосредственно под ним.
С этой целью его траектория была разбита на равные сегменты. Они пронумерованы от 1 до N. По запросу с Земли о количестве живых форм в сегментах с L по R (L R) - спутник должен, пролетая над ними (L, L+1, …,R-1, R сегментами) произвести подсчет и затем, в ответ на запрос, отправить полученные данные. Но количество организмов постоянно изменяется: в некоторое время в X сегменте на Y единиц.
Помогите написать программу для спутника, которая будет отвечать на запросы и отслеживать количество единиц жизни в каждом сегменте.
Формат входных данных
Во входном файле первым записано число N (1 N 213 = 8192). Затем записана последовательность событий:
Событие Параметры Описание
1 X, Y Изменение количества организмов в сегменте с номером X на Y единиц.( 215 Y 215-1 = 32767)
2 L, R Запрос суммарного количества организмов с L по R сегмент.
0 Завершение работы.
Количество событий не превосходит 100000.
Формат выходных данных
В выходной файл записывать только ответы на запросы.
Как мы видим, формулировка задачи достаточно большая, но выделим из этого описания только нужные нам моменты для решения задачи: дан одномерный массив, элементами массива могут быть только неотрицательные целые числа, элементы массива могут менять сове значение в процессе работы, требуется нахождение суммы элементов некоторого непрерывного отрезка массива. Попробуем решить поставленную перед нами задачу (и попутно ослабим ограничение на количество событий).
Решение.
Простые алгоритмы.
Первый вариант решения (A), который приходит в голову, достаточно прост. Назовем событие изменения значения элемента массива UpDate(I, J), где I – индекс изменяемого элемента массива, а J – значение изменения. Аналогично для события запроса суммы элементов отрезка массива – Report(I, J), где [I, J] отрезок массива. Приведем листинг этих процедур:
Procedure UpDate(Const I, J: Integer);
Begin
Inc(X[I], J);
End;
Procedure Report(Const I, J: Integer);
Var K: Integer; Sum: LongInt;
Begin
Sum := 0; For K := I To J Do Inc(Sum, X[K]);
WriteLn(Sum);
End;
В зависимости от события вызывается соответствующая ему процедура. Программа получается короткой и ее легко понять. К сожалению, она никуда не годиться – она медленно работает при больших размерностях задачи (в частности при увеличении числа запросов, а тем более числа событий).
Есть очевидный способ сделать быстрее вычисление суммы отрезка. На этот раз будем хранить в X[I] сумму отрезка [0, I]. А вычисление суммы отрезка [I, J] сведем к вычислению разности [0, J] – [0, I-1]. Наше нововведение заметно ускорило вычисление суммы отрезка, но так же и замедлило изменение массива, теперь, в случае изменения I-го элемента, кроме X[I] потребуется изменить еще и все X[J], (I
Inc(Sum, X[J]);
Dec(J, Dispose(J));
End;
Dec(I);
While I >= 1 Do Begin
Dec(Sum, X[I]);
Dec(I, Dispose(I));
End;
WriteLn(Sum);
End;
Здесь использована процедура Dispose(I), которая возвращает значение 2k для заданного числа I. Ее листинг я думаю приводить не надо, вы сами без труда сможете ее воспроизвести. Следует также указать, что для работы с этой структурой данных нам нужен размер массива X такой, чтобы это было число степень 2, превосходящее, либо равное размеру исходного массива. Подобрать его можно простым циклом.
While N > Nm Do Nm := Nm Shl 1;
N := Nm;
N – размер исходного массива, Nm - переменная для подбора подходящего размера массива X. Затем заменяем значение N на найденное Nm (в алгоритмах использовано единое представление длинны массива X переменной N). Приведенный алгоритм (D) работает на больших размерностях, чем все ранее использованные алгоритмы.
Оценки.
Для простых алгоритмов, особенно для (A). и (B), оценка времени работы пропорциональна O(N) для блока обновления или запроса. Это нас не устраивает т.к. для достаточно больших N мы просто не дождемся, когда алгоритм возвратит конечный результат. Чего не скажешь об алгоритме (D). Оценка его времени работы O(log2N), что более приемлемо для нашей задачи.
Алгоритм Время работы (сек.).
A 6~7
B 7~8
C (для Long = 5, 25, 50, 100) 3~4, 1~2, 1, менее 1
D Менее 1
Тестирование выполнено для N = 8192, количество событий 100000, 55055 запросов. Однако, этими алгоритмами еще не заканчивается решение данной задачи. Существует множество решений, но решений с меньшей верхней оценкой я не нашел.
В заключение скажем, что приведенным здесь примером мы подтвердили, что сложные алгоритмы зачастую дают огромное увеличение производительности.
Надежно и удобно: туры в Египет по доступным ценам.
Обсудить новейшие рылобовные снасти, похвастаться уловом - все это на портале о рыбалке
Прикольный форум Вилинбурга - стоит почитать
