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

старый способ длится ~10585ms.
новый способ длится ~83ms.

 

я не совсем понял вопроса, но время обсчета по сравнению со "старым" способом приведено выше.

 

pmax*, pmin* для байтов и вордов.
maxp*, minp* для флотов и даблов.

 

Yashin_Sergey

Ну вот массив: 1,2,3,...
Ну просчитал он первые 10000 чисел, получил min=1. Передвинулся вправо на 1 - получили, что "потерянный" элемент = min, значит, нужно пересчитать всё заново - 10000 сравнений. И т.д. на каждом шаге, т.е. получилось не лучше обычного перебора.
Или я не так понял алгоритм?

 

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

 

maxdiver

UbIvItS

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

 

leo
Да, я понимаю, что на среднестатистических данных этот алгоритм будет хорош. Но вот в вырожденном случае - он будет очень сильно тормозить (правда, я не знаю, насколько приемлемо такое торможение - может, в данном конкретном случае и 10 секунд на одном тесте - нормально). Тем более что этот тест совсем нетрудно сделать - тривиальная арифметическая прогрессия, да и вообще любые почти отсортированные данные.

Так вот, как насчёт дерева (тем более, что в C++ это уже готовый map)?

 

? Что значит - соседних?
10 000 в какую сторону от текущего?
Ели первый текущий то следующие 9 999 соседи?
Ну а если последний то предидущие 9 999 соседи?
Или брать половину до и половину после текущего элемента?

 

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

 

Если уж речь зашла о статистике, то первоначальная задача должна ставиться "найти... с вероятностью...". Иначе на случайном наборе только перебор.

 

asmfan
Не, ну перебор за O(n*m) не обязателен. Я говорю, можно деревом - за O(n*ln(m)).
Просто ещё не факт, что последнее окажется быстрее первого
Вот мне и интересно - будет ли дерево с O(ln(m)) быстрее перебора с O(m)?

 

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

 

maxdiver

Ну и пусть тормозит Если по условию задачи такой случай невозможен или маловероятен, то и париться с ним незачем Мы же не знаем, что из себя представляет этот массив и автор на эту тему молчит, но судя по выигрышу в скорости это достаточно (квази)случайный набор чисел

UbIvItS

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

asmfan

Сама задача ставится детерминированно, но время ее решения может зависеть от статистики распределения чисел в массиве. Классический пример - алгоритмы быстрого поиска строк а-ля Бойер-Мур, котрые при неудачных сочетаниях окончания искомой строки и статистики распределения символов в тексте могут работать заметно хуже. Например, если потребовать, чтобы искомая строка заканчивалась на несколько пробелов, то на файлах типа m32lib\windows.inc с огромным числом серий пробелов, результаты некоторых алгоритмов получаются заметно хуже, чем для других "благоприятных" сочетаний (см.цифры)

 

leo
не знаю - изложенный метод не тянет на статистический: для вероятностных оценок нужно делать случайную выборку: либо сегментов (с их полной обработкой), либо в каждом сегменте элементов (20% эл. к примеру). Но как я понял, речь изначально шла о детерменированном алгосе.

 

Yashin_Sergey
Можно хранить вместе со значением элемента хранить заранее вычесленные для него мин и макс.
Хотя это приведет к увеличению объема.

 

UbIvItS

Да что ты уперся в "заумные" статистические методы
Пример: выборочное среднее - статистическое понятие ? Да. А алгоритм расчета - детерминированный ? Для стационарного процесса с неизменным средним - да. Т.е. для получения оценки среднего значения никакого распределения вероятностей процесса знать не нужно, достаточно знать что он стационарный. А вот если не стационарный и среднее значение изменяется во времени, тогда приходится использовать скользящее среднее в окне и нужно из каких-то соображений задавать размер окна усреднения.
ВОЗМОЖНО, в рассматриваемой задаче аналогичная ситуация, только вместо среднего значения нужно определять размах значений (Min,Max) на интервалах корреляции 10тыс. отсчетов и смотреть как эта величина изменяется во времени. И при чем тут вероятностные характеристики сегментов - не понятно

 

leo

вот и вопрос как это узнать не перебрав элементы??..?? впрочем, мне не ответели: сошлись ли результаты второго и первого метода.

 

Сошлелся естественно.

 

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

 

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