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

Так чем вам мой алгоритм за O(n\log(10000)) не понравился?

 

halyavin
классный алг, я бы так не догадался
но сомневаюсь, что он будет быстрее, и к тому же требует кучу памяти

насчет той оптимизации, которую так долго обсуждали: можно запоминать не один, а несколько максимумов/минимумов. когда настоящий экстремум выпадает из окна, можно не проводить поиск повторно, а брать следующий из запаса, однако при этом придется сравнивать входящие в окно элементы со всем набором этих максимумов/минимумов, чтобы поддерживать набор в актуальном состоянии, а вот это уже замедлит время обработки.
какое отношение размеров "запаса" к размеру окна будет оптимальным, сказать сложно - мне не хватает математики. логично предположить, то оптимальным будет либо единственный максимум и минимум, как это и было сделано. либо набор, равный по размеру самому окну.
поясняю:
1. на первом шаге все элементы окна отсортировываются и заносятся в двусвязный список из 10000 элементов. также создается кольцевая очередь из 10000 элементов, связывающая элементы списка и соответствующие им номера позиций в исходной последовательности чисел: в первом элементе очереди хранится ссылка на элемент списка, соответствующий первому элементу окна, во втором - на второй итд. минимум и максимум известны - это крайние элементы списка
2. окно сдвигается: из очереди берется выталкиваемый элемент, этот элемент удаляется из списка. новый элемент окна включается в список, на него создается новая ссылка в очереди. поскольку список отсортированный, включение элемента потребует не 10000 сравнений, а log(10000)/log(2) ~ 13 сравнений
3. экстремумами для нового окна будут опять же крайние элементы списка. шаг два повторяется до завершения последовательности

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

что в среднем более оптимально, сказать трудно. могу предложить такую оценку:
первый алгоритм: если в окне из 10000 элементов два экстремума, то выход экстремума из окна будет наблюдаться в среднем раз в 3333 итерации (10000/3). с чего я так решил? попытался разместить элементы наиболее равномерно: в 1/3 и 2/3 расстояния от начала окна, не учитывая при этом вероятность замены экстремумов новыми значениями до выхода экстремума из окна.
итак, на одну из 3333 итераций будет приходиться 10000 сравнений, на остальные - по 2
считаем: (190000/3333)*10000 + 190000*(1-1/3333)*2 = ~950000 операций

второй алгоритм: на каждое окно приходится по log(10000)/log(2) - то есть логарифм 10000 по основанию 2 сравнений: 190000*log(10000)/log(2)= ~2524665
к тому же здесь следует учесть время, необходимое на создание списка, то есть, на сортировку первого окна

по-видимому, способ, котрый написал Yashin_Sergey, будет все же оптимальным

ps: ошибка, я имел в виду не список, а отсортированное дерево. тогда тем более: включение элемента в такое дерево займет еще больше времени

 

Nouzui

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

 

leo
все дело в том, что я думал сначала, что разбивка идёт на сегменты выровненые по границе 10000 эл. ) - отсюда и не понимание алгоса.
Yashin_Sergey
так что - извиняюсь, но в спорах.............

 

Nouzui

За какое время ты собираешься отсортировать массив и построить двусвязный список?
У тебя только на этот первый шаг уже уйдет минимум 10000 сравнений + затраты на построение двусвязного списка при размере массива в 10000 элементов. О каких менее чем 10000 сравнений может идти речь?

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

 

Miller Rabin
неужели ты не понял алгоса(?????) - бери за основу: "10000 соседних элементов", мы имеем дело с пересекающимися массивами а не выровнеными по границе.

 

UbIvItS
Да я уж давно понял алгос.
Только я так и не увидел никакой его реализации ни в каком виде.

Не стоит путать быстродействие кода с быстродействием алгоритма.
Это две разные вещи.

По поводу быстродействия алгоритма все предельно ясно. Вы его не сделаете за время меньшее, чем O(n), где n общее количество элементов. Есть даже теорема по этому поводу "О предельном времени сортировки". Только я не помню, к сожалению, кто ее доказал. Надо будет поискать на досуге.

А вообще задача поиска минимума и максимума за линейное время находится на первых страницах книги "C++: Справочник для полного идиота" (C++ For complete idiots). У нас на первом курсе препод по ней лекции читал. Просто он по жизни знал Паскаль, а тут его заставили С++ преподавать.

Касательно прироста ускорения за счет предсказанных переходов это уже быстродействие кода. И оценка времени работы вида O(n) к нему совершенно неподходит. Так как 1) Процессор может выполнить несколько команд за один такт. 2)Разные команды требует разное число микроопераций 3)... и так далее вы это и сами все знаете.

Быстродействие кода удобно оценивать в тиках. Так как процессоры у всех разные. И те милисекунды, которые привел Yashin_Sergey можно засунуть куда подальше. Никакой информации они не несут. Я к сожалению не смог найти информацию какими компьютерами оснащают психбольницы. Посему даже не знаю о какой конфигурации в данном случае идет речь.

Касательно, анализа быстродействия кода за эталон можно взять программу, которую предложил UbIvItS. Если, конечно, он даст добро на ее использование.

 

Miller Rabin

Сами миллисекунды не несут, поэтому можешь засунуть их куда угодно А вот отношение миллисекунд для разных алгоритмов часто несет больше информации, чем голые тики, тем более полученные на разных компах, и тем более на тех, которыми "оснащают из психбольницы" ))

 

leo
лано, не стоит так.

Miller Rabin
расскажи задачу своими словами, плзззз

 

UbIvItS
Задача состоит в том, чтобы для каждого элемента в массиве найти минимальный и максимальный элемент на отрезке из 10000 соседних. Так???

Задача эта решается за время O(n). Причем это будет минимально возможное время

Изначально Yashin_Sergey решил ее за время О(n*k), где n = 200000 элементов, а к = 10000 элементов массива.
Даже не рассматриваю как вариант решения.

А вот затем .....

Блин даже руки опускаются.

Приведите хотя бы ОДНУ программу с которой можно СРАВНИТЬ.
Я пишу это уже в четвертый раз и каждый раз получаю поток ругани в свой адрес

 

Miller Rabin

ИМХО Изменение всех мин. и макс. надо занести в массив индексов.
И считать локальные мин., макс. (10 тыс.) по массиву индексов.

 

Ты так любишь поспорить что аж смешно.

Задача решается за O(n) только в том случае если массив данных не представлен в виде случайного набора чисел, потому что на кажом шаге можно знать и минимум и максимум.

Здесь же я говорил о детерминированном случайном потоке чисел, и тут ка ты хочешь но против природы не уйдешь и не решишь задачу за O(n).

И кричать что ты решишь эту задачу за О(n) можешь сколько угодно. Напиши код программы для случайного набора чисел, где задача решается за O(n). Напиши хотя бы на "С".

Если не хочешь/ не можешь написать, то привиди логическое описание алгоритма решающего задачу за O(n) для детерминированного случайного набора чисел. Тогда все мы поймем что ты не просто пустослов а действительно знаешь о чем ОРЁШ. ) И получишь нобелевскую премию т.к. опровегнешь законы природы.

 

Miller Rabin
ссмотри:
возьмем 10 эл. и окошко шириной в 5 эл. и начнём его двигать - и посмотрим индексы элементов, кои в окно влазеют на каждом шаге:
1. 0, 1, 2, 3, 4
2. 1, 2, 3, 4, 5
3. 2, 3, 4, 5, 6
4. 3, 4, 5, 6, 7
5. 4, 5, 6, 7, 8
6. 5, 6, 7, 8, 9
------------------------
алгос, предложенный Pavia, позволяет сократить кол-во вызовов нижнего цикла - отсюда и столь резкий прирост скорости.

 

UbIvItS
По алгоритму Pavia походу выполнена твоя первая программа, которую ты приводил. И которая топикстартером была торжественно объявлена как абсолютно неправильная.
Изначально вопрос о столь резком приросте ускорения стоял всвязи с приведенными временами оценки старого и нового алгоритма топикстартера.

А именно:

Я тогда не понял откуда столь резкое ускорение потому что подумал будто топикстартер решил задачу за О(n), где n - общее количество элементов в массиве 200000. Я и не предположил что он решил ее абсолютно бездарно за время O(n*k),где к-размер диапазона 10000.

Yashin_Sergey
Судя по всему ты не только не дружишь с логикой - она твой злейший враг.
В ответ на вопросы про время выполнения твоего алгоритма ты закатил истерику, и стал писать оскорбления в мой адрес пост #77. После чего ты попросил оставить свои эмоции при себе и писать по делу пост#80.
Когда я предложил тебе выложить свой свой код. Для всеобщего обозрения. ты заявил, что не хочешь иметь со мной никаких дел.

Вот видишь. Орёшь здесь только ты.
И это тоже понятно почему. Потому, что судя по твоим постам программируешь ты с большим трудом. И ты прекрасно понимаешь, что как только ты выложишь свой код, все твои понты которые ты так старательно напускаешь вот уже 5 страниц лопнут как мыльный пузырь.
Именно поэтому свой код ты и не выкладываешь.

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

 

Miller Rabin
решение за O(n*k)
p - исходный массив
p1 заполняется функцией func

Код (Text):

1. template<class T, int n, int k>
2. void func(/*IN*/ T (*p)[n], /*OUT*/ T(*p1)[n-k])
3. {
4.     int i, j;
5.     T max;
6.     for(i= 0; i<n-k; i++)
7.     {
8.         max= *p[i];
9.         for(j= 1; j<k; j++)
10.         {
11.             if(*p[i+j]>max)
12.                 max= *p[i+j];
13.         }
14.  
15.         *p1[i]= max;
16.     }
17. }

гони идентичный алгоритм с гарантированным O(n)

 

Miller Rabin
оптимизированный вариант. наихудшая оценка - те же O(n*k), но в среднем дает прирост, о котором писал Yashin_Sergey:

Код (Text):

1. template<class T, int n, int k>
2. void func(/*IN*/ T (*p)[n], /*OUT*/ T(*p1)[n-k])
3. {
4.     int i, j;
5.     T max;
6.     int maxi= -1;
7.  
8.     for(i= 0; i<n-k; i++)
9.     {
10.         if(maxi<i)
11.         {
12.             max= *p[i];
13.             maxi= i;
14.             for(j= 1; j<k; j++)
15.             {
16.                 if(*p[i+j]>max)
17.                 {
18.                     maxi= i+j;
19.                     max= *p[maxi];
20.                 }
21.             }
22.         }
23.         else if(*p[i+k-1]>max)
24.         {
25.             maxi= i+k-1;
26.             max= *p[maxi];
27.         }
28.  
29.         *p1[i]= max;
30.     }
31. }

не проверял. поправьте, если в чем-то ошибся

 

//offtop ты уже отредактировал свой пост. Вопрос снят

 

кто "ты", какой пост?

 

Nouzui
Насчет прироста

1) Я пишу на Fasm. Таким образом для того, чтобы оценить прирост не на пальцах, а получить реальные результаты
мне придется переписать твой код. Это, конечно, несложно, но тогда получится что я модифицирую чужой код, а это не еcть хорошо. Тем более что, еще в пером посте было сказано что реализация будет проводится на Fasm.

2) Изначально тип данных был Double. Я конечно могу тоже начать работать с целыми числами, но время тогда тоже изменится

 

"получится что я модифицирую чужой код, а это не еcть хорошо"
я тебе разрешаю. в эксклюзивном порядке

"Изначально тип данных был Double.. время тогда тоже изменится"
порядок отношения все равно сохранится