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

Тема в разделе "WASM.A&O", создана пользователем Yashin_Sergey, 15 июн 2007.

  1. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    Yashin_Sergey
    алгос в твоей реализации все же не будет процеживать лишь те сегменты, у коих экстремумы совпадают с предыдущим. поэтому имеет смысл подумать над модификацией
     
  2. Yashin_Sergey

    Yashin_Sergey Сергей

    Публикаций:
    0
    Регистрация:
    15 июн 2007
    Сообщения:
    62
    Адрес:
    Москва
    Для того, чтобы знать совпадает ли текущий экстремум с предыдущим, надо знать текущие экстремумы, поэтому бесмысленно сравнивать текущие с предыдущими когда и так уже они есть.
     
  3. Booster

    Booster New Member

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

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

    Yashin_Sergey Сергей

    Публикаций:
    0
    Регистрация:
    15 июн 2007
    Сообщения:
    62
    Адрес:
    Москва
    По мере формирования.
     
  5. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    Booster
    он юзает детерменированную методу, а ты предлагаешь гадание на кафейной гуще - точность будет больше с возрастанием выборки, но это, в свою очередь, приведёт к резкому паденению скорости, к тому же, генерация рэндом чисел не дёшево стоит по затратам проца.
     
  6. Miller Rabin

    Miller Rabin New Member

    Публикаций:
    0
    Регистрация:
    4 янв 2006
    Сообщения:
    185
    Прочитал все три страницы топика несколько раз. Но сути я так и не понял.
    Задача найти максимальный и минимальный элементы в массиве случайных чисел за время меньшее 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
    Возможно я не понял твой алгоритм. Разъясни пожалуйста подробнее
     
  7. Yashin_Sergey

    Yashin_Sergey Сергей

    Публикаций:
    0
    Регистрация:
    15 июн 2007
    Сообщения:
    62
    Адрес:
    Москва
    Если вы не поняли мой алгоритм, прочитайте страницы топика внимательнее.
    Спорить мне не нужно т.к. результат уже получил.
     
  8. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Miller Rabin

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

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

    t00x New Member

    Публикаций:
    0
    Регистрация:
    15 фев 2007
    Сообщения:
    1.921
    Yashin_Sergey
    В результате 20 максимумов и минимумов?
    Или 2*20 массивов по N<10 000 индексов изменения крайних значений?

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

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    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.       }
    вот примерно так.
     
  11. Miller Rabin

    Miller Rabin New Member

    Публикаций:
    0
    Регистрация:
    4 янв 2006
    Сообщения:
    185
    Yashin_Sergey
    Боже упаси тебе идти в университет и писать там методички.
    Тебя там точно кто-нибудь пристрелит.

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

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

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    Miller Rabin
    не знаю - я сам всю дорогу сомневался в таком резком приросте, а настрокав код засомневался ещё больше:)) в данном вопросе говорить о столь резком возрастании скорости(!!!!!!!!) берусь предположить, что у человека в коде присутствовал некий рудимент, о коем он здесь не говорил.
     
  13. Yashin_Sergey

    Yashin_Sergey Сергей

    Публикаций:
    0
    Регистрация:
    15 июн 2007
    Сообщения:
    62
    Адрес:
    Москва
    Ты слишком много учился.
     
  14. Yashin_Sergey

    Yashin_Sergey Сергей

    Публикаций:
    0
    Регистрация:
    15 июн 2007
    Сообщения:
    62
    Адрес:
    Москва
    Если это тот код который ты привел то он совершенно неправильный.
     
  15. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    /offtop
    куда делась часть топиков??
     
  16. Miller Rabin

    Miller Rabin New Member

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

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

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

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

    Yashin_Sergey Сергей

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

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

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

    UbIvItS Well-Known Member

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

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Miller Rabin

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

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

    Yashin_Sergey Сергей

    Публикаций:
    0
    Регистрация:
    15 июн 2007
    Сообщения:
    62
    Адрес:
    Москва
    Перечитай, я же ответил, что причина в том, что не на каждом элементе выполняется перебор 10 тыс. соседних.

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

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

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