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

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

 

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

 

Yashin_Sergey

Предлагаю супер метод: Берёшь рандомно некоторое кол-во значений массива, и в них ищешь. Скорость будет офигительна -).

Для твоего случая самым разумным будет считать по мере формирования массива. Или ты сразу указатель из памяти берёшь?

 

По мере формирования.

 

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

 

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

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

Ок. Дан массив.
3, 7, 5, 3, 1. Требуется найти в нем минимум и максимум за время меньшее O(5).
Длина окна 4.

Что такое здесь окно длиной 4? Это отрезок длиной в 4 цифры?
Если я правильно понял, то на первом шаге помещаем в окно цифры:
3,7,5,3. Находим в них макс и мин последовательным перебором за O(4) макс 7, мин 3

После этого смещаем границы окна. А до какого значения? До первого экстремума? т. е 7.?
Тогда следующее окно будет
7,5,3,1
А что тогда?
У нас вышло за пределы первого окна 1. Сравниваем его с полученными экстремумами за О(1) получаем макс 7 мин 1.
Алгоритм закончил свою работу. Результат верный.
Конечное время O(4)+O(1) = O(5).

И что? Те же яйца только в профиль.

Yashin_Sergey
Возможно я не понял твой алгоритм. Разъясни пожалуйста подробнее

 

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

 

Miller Rabin

Ты почитай внимательно его первый пост.

IMHO задача другая.

 

Yashin_Sergey

В результате 20 максимумов и минимумов?
Или 2*20 массивов по N<10 000 индексов изменения крайних значений?

И ещё вопрос: соседние элементы - это какие?

 

Yashin_Sergey
я предлагаю решить задачу в один цикл.
сорри, что код не на асме, надеюсь, вернусь к строканию на нём)

Код (Text):

1. double max4seg[20], min4seg[20], max=0, min=0, count_seg=0, into_seg=0;
2. double *mass=new double[200000];
3. for(int i=0; i<200000; i++){
4.       if (into_seg<10000) into_seg++;
5.       else
6.           {
7.           into_seg=0;
8.           count_seg++
9.           }
10.      if(max<mass[i]) max4seg[count_seg]=max=mass[i];
11.      if(min>mass[i]) min4seg[count_seg]=min=mass[i];
12.       }

вот примерно так.

 

Yashin_Sergey
Боже упаси тебе идти в университет и писать там методички.
Тебя там точно кто-нибудь пристрелит.

Это твоя задача?

А вот описание твоего алгоритма. "Понятнее некуда"

UbIvItS
А вот программа для решения задачи, которая последовательно перебирает все элементы от 0 до 200000 и записывает в переменную min максимальный элемент, а в max минимальный элемент. Плюс к этому она еще делит массив из 200000 элементов на отрезки по 10000 и для каждого сегмента хранит максимальный элемент и минимальный элемент.

И че? Программа находит min и max за время O(200000) в чем тут 100 кратное ускорение?

 

Miller Rabin

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

 

Ты слишком много учился.

 

Если это тот код который ты привел то он совершенно неправильный.

 

/offtop
куда делась часть топиков??

 

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

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

Тебе в посте#66 по описанию по твоему алгоритму были заданы конкретные вопросы. И ты не ответил ни на один из них.

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

 

Ты очень странный человек. Я описал свою проблему и попросил ответить знающих людей о возможном её решении.
Ты единственный за все эти дни высказавшийся, что тебе непонятен алгоритм, пожалуйста - не понимай дальше,
просто пропусти тему и не обрекай ни свое ни моё время на бесполезную трату. Понимаю, тебе тоже хочется знать, как же так у меня получилось, так напиши мне что бы я выслал тебе например исходник с алгоритмом, и сиди разбирайся. Для чего устраивать здесь разборки по причине своей сверх образованности ? не понимаю. Ты уже не подросток раз закончил аниверситет, а зачем то вежешь себя ребячески.
Хочешь покричать и орать ? или в блоги, в чаты. Но подальше отсюда.
Я тебе напомню (или открою) истину а то ты в ниж похоже закопался: НИКТО ЛИЧНО ПОД ТЕБЯ В ЖИЗНИ ПОДСТРАИВАТЬСЯ НЕ БУДЕТ. Поэтому в жизни и темболее работе и т.п. ценится КОММУНИКАБЕЛЬНОСТЬ а не твоя бравада. Тебе никто не скажет но дураком посчитает, со временем увидишь и сам, если глаза раскроешь.
Я например уже тебя таковым считаю. Вырасти.

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

Я думаю можно в некоторых форумах в заголовке напоминать "ПИШИТЕ ПО ДЕЛУ И ТЕМЕ".

 

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

 

Miller Rabin

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

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

 

Перечитай, я же ответил, что причина в том, что не на каждом элементе выполняется перебор 10 тыс. соседних.

Всё, мне уже становится забавно.

Кому надо пишите на почту я вышлю исходник на asm.

Эмоции оставьте при себе.