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

Добрый день.

Сталкивался ли кто-нибудь с поиском максимума и минимума в массиве данных ?
Есть массив из числовых (double) данных в нем нужно найти максимальное число
и минимальное.

Вопрос в том, как этот процесс возможно оптимизировать ?

У меня массив из 200 тыс. элементов, и на каждом элементе
нужно знать максимальное и минимальное число из 10 тыс. соседних эелементов.
Я реализовал поиск мин. и макс. через цикл по 10 тыс. соседним элементам,
но таких циклов получается 200 тыс., это огромное кол-во ресурсов процессора.
Может быть есть более продуктивные способы поиска ?

Пишу на fasm.

 

Yashin_Sergey
Токмо какой-нибудь сортировкой

 

мне кажется быстрее будет обычный проход через loop. Она как таковая тут бессмысленна.
Может быть я ошибаюсь.

 

Yashin_Sergey

наверное будет медленнее, чем сортировка. Почитай Кнута, посмотри на оценку времени работы алгоритма сортировки в зависимости от кол-ва элементов в массиве.

 

Yashin_Sergey
М-да, еще раз прочитал постановку задачи, кажется мне, надо ее осмыслить математически, а потом думать об алгоритме... и о сортировке...
Кстати, а почему такие хитрые минимумы и максимумы (для каждого элемента, да еще по конечному числу соседних)?

Предположим, что ты вычислил для первого элемента максимум M1 и минимум m1 по первым N (=10000) элементам. Тогда, если второй элемент не равен найденному максимум (минимуму), то при получении максимума M2 (минимума m2) для второго элемента достаточно сравнить M1 (m1) с N+1-м элементом. Попробуй развить идею...

 

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

 

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

 

Правильно, оно так и есть. Но линейный поиск отнимает кучу ресурсов.
И возможно есть более быстрые подобные алгоритмы.

 

Yashin_Sergey
Посмотри похожий топик
http://forum.sources.ru/index.php?showtopic=145541
И обрати внимание на посты leo

 

Спасибо.

 

Yashin_Sergey

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

 

OffTop
Ну вот, как обычно в последние несколько лет, номер топика (145541) ... делится на 11, да еще симметричный... :-?

 

/оффтоп
это ты про какой ещё топик)

 

UbIvItS
В моем топике #9:
http://forum.sources.ru/index.php?showtopic=145541

 

Но ведь, то, что описывает leo - это всего лишь уменьшение затрат на каждом сравнении. Но ведь всё равно таких сравнений будет 2*10^5 * 10^4 = 2 * 10^9 ! ИМХО сначала нужно улучшить алгоритм.

Я предлагаю варианта с помощью дерева, тогда будет k * 2*10^5 * ln(10^4).
А дальше уже, если надо, можно будет и ускорить сравнение двух float'ов.

 

Yashin_Sergey

Понятно, что лучшее возможное время будет порядка O(n), так как надо проверить каждый элемент. Значит речь идет только об уменьшении константы. В наивном алгоритме она будет примерно 10000, так как каждый элемент будет сравниваться со всем его "скользящим окном". Можно организовать это окно в форме priority queue (например на основе Fibonacci heap) и тогда количество сравнений сократится, причем выигрыш зависит от природы данных - чем случайней, тем лучше. Правда добавится еще overhead самой структуры, который практически не поддается оптимизации.

В общем сделай обе реализации и сравни скорость. А результаты выложи, интересно Или смотри, как можно переформулировать задачу.

 

Yashin_Sergey
Когда сделал первый цикл. Смотришь что у тебя с левого конца, если элемент равен минимуму/максимуму
, то тогда пересчитывать массив. Если не равен, то просто сравниваешь минимуму/максимуму со следующий элемент за элементом с правого конца диапазона. Это и будет новыйе минимуму/максимуму для следующей точки.
Ускорение будет, так как циклов будет гораздо меньше 200 тыс. Дальше все зависит от данных.
Идею можно развить дальше.

 

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

скорость изменилась в лучшую сторону.

при первом подходе, когда реализованно всё с помощью цикла весь расчет длится ~10585ms.
а с вышеуказанной оптимизацией длится ~83ms.

 

Yashin_Sergey
Но разве тогда на элементарном тесте 1,2,3,... не будет тормозить? По-моему будут те же несколько секунд.

 

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