Поиск максимума и минимума

Atlantic

поиск требует лог. времени, а вставка, удаление и добавление делаются в одну итерацию

 

Вот, написал тестовую программу:

Здесь N=200000, M=10000.

Random data - случайные числа
Increasing data - числа упорядочены по возрастанию
Decreasing data - числа упорядочены по убыванию
Alternating data - последовательность вида 1,10,3,8,5,6,7,4,9,2

Heap - алгоритм, использующий кучу.
Stupid - эталонный алгоритм, на каждом шаге переситывает Min/Max.
Less stupid 1 - пересчитывает Min/Max, только если он вышел за пределы окна, причем Min и Max пересчитываются независимо.
Less stupid 2 - пересчитывает Min/Max, только если он вышел за пределы окна, причем Min и Max пересчитываются вместе.

Теперь по результатам тестов:
- на случайных данных рулят LS1 и LS2 (так как Min/Max редко выходят за пределы окна), Heap немного отстает (немного - по сравнению со Stupid).
- на остальных данных LS1 лучше LS2, так как пересчитывает на каждом шаге, в основном, только одно число.
- аномальное различие в скорости Stupid на убывающих и возрастающих данных пока не объяснено...

По итогам тестов рекомендуется LS1, если данные случайные, и Heap, если в них есть хотя бы небольшая доля упорядоченности.

Эээ... Хотел прикрепить тестовую прогу, но не нашел кнопки

 

Есть исходник, в котором все реализовано, но пока не смог прикрепить...

Вот исходник: http://acmtest.ru/Heap.rar

 

после прохода 10000 ищет макс и мин на каждом шаге

 

t00x
Не совсем понял, что ты имел в виду. ИМХО, на убывающей последовательности первый условник кода выполняется все время, а второй - один раз на 10000. А на возрастающей - наоборот. Отсюда и разница в скорости.

 

Atlantic
#184 не так понял.

это имел в виду?
сразу не понял что аномальное

 

У меня поинтересней

Код (Text):

1. Random data:
2.  
3. Heap: 29.85 ms
4. Stupid: 3225.30 ms
5. Less stupid 1: 2.64 ms
6. Less stupid 2: 2.59 ms
7.  
8. Decreasing data:
9.  
10. Heap: 93.14 ms
11. Stupid: 3246.31 ms
12. Less stupid 1: 3031.35 ms
13. Less stupid 2: 6130.00 ms
14.  
15. Increasing data:
16.  
17. Heap: 91.40 ms
18. Stupid: 3444.03 ms
19. Less stupid 1: 3182.29 ms
20. Less stupid 2: 5874.55 ms
21.  
22. Alternating data:
23.  
24. Heap: 56.36 ms
25. Stupid: 3525.17 ms
26. Less stupid 1: 1628.59 ms
27. Less stupid 2: 2353.25 ms

так же стабильно LS на случайных числах и ничего аномального

 

leo

что такое x?
код не смотрел - с асмом туго), но насчет удаления элементов могу предложить вот что:
можно содержать массив, где каждый элемент является ссылкой на конкретный узел дерева.

 

Код (Text):

1. #include <stdio.h>
2. #include <stdlib.h>
3.  
4. #define N 25
5. #define M 4
6.  
7. int a[N]; //исходный массив
8. int b[M]; //b[j]=min(A[j+M*k],...,A[M-1+M*k])
9.  
10. int main()
11. {
12.     int i,j,m;
13.     for(i=0;i<N;i++)
14.     {
15.         a[i]=rand()%100;
16.         printf("%2d ",a[i]);
17.     }
18.     printf("\n%*s",3*M/2,"");
19.  
20.     for(i=M;i<N;i++)    //O(N*M)
21.     {
22.         m=a[i];
23.         for(j=1;j<=M;j++)
24.             if(a[i-j]<m)
25.                 m=a[i-j];
26.         printf("%2d ",m);
27.     }
28.     printf("\n%*s",3*M/2,"");
29.  
30.     for(i=M;i<N;i++)    //O(N)
31.     {
32.         if(i%M==0)
33.         {
34.             m=a[i-1];
35.             for(j=1;j<=M;j++)
36.             {
37.                 if(a[i-j]<m)
38.                     m=a[i-j];
39.                 b[M-j]=m;
40.             }
41.             m=a[i];
42.         }
43.         if(a[i]<m)
44.             m=a[i];
45.         printf("%2d ",b[i%M]<m?b[i%M]:m);
46.     }
47.     printf("\n");
48.     return 0;
49. }

Медитируйте

 

Black_mirror
Мммм... работает. Похоже на кумулятивный массив, но для минимума. В общем, зачёт!!!

Работает вроде так: на первой итерации b[0]=min(A[0], ..., A[M-1]). На второй итерации мы выводим min(b[1], A[M])=min(A[1], ..., A[M]) - сравнивая текущий минимум с A[M]. На третьей итерации мы выводим min(b[2], A[M], A[M+1])=min(A[2], ..., A[M+1]) - опять же, нужно обновить только текущий минимум за одно сравнение. И так далее, пока массив не исчерпается, а потом нужно снова его заполнить. Цикл внутри условника выполнится (N-M) div M раз, так что общее время выполнения будет O(N).

 

В общем, потестил я этот алгоритм (чуть оптимизированный) в своей проге - на всех наборах данных работает примерно за 2.5 мс. Он даже делает LS1 на случайных данных! Обновленную версию проги выложил туда же.

 

Atlantic
было б не плохо расписать чем занимаеться каждый цикл:
M - ширина окна??
N - колво элементов в массиве??

 

Да. Тебя интересуют циклы в функции FindHeap?

 

Black_mirror
Алгоритм - загляденье. Продолжаю медитировать

 

Black_mirror

Стабильно.

 

Atlantic
меня интересуют циклы в алгосе Black_mirror

 

UbIvItS
Алгоритм начинается с цикла с комментарием // O(N)

Сначала в условнике проверяется, не опустошен ли кумулятивный массив b. Если опустошен - то он заполняется так, как написано в комментарии к его объявлению. Ну а остальное я вроде раньше расписал.

 

Atlantic
угу уже понял)) - теперь просекаю алгос)

 

поправте, коли я не прав: алгос за M проходов выстраивает отсортированный массив b???

Код (Text):

1.    m=a[i-1];
2.             for(j=1;j<=M;j++)
3.             {
4.                 if(a[i-j]<m)
5.                     m=a[i-j];
6.                 b[M-j]=m;
7.             }
8.             m=a[i];

 

этот алгос или чудо )) или багггггггг)
единственный алгос, позволяющий сортировать за время O(n) - индексная сортировка: здесь её и в помине нет, к тому же, она прожорлива по памяти, так что применять её на дюбелях нереально.