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

t00x
Это время гарантируется для любых данных.

 

Atlantic
возможна потоковая обработка?

 

t00x
Да. Добавить/удалить элемент из кучи можно за логарифмическое время. Чтобы знать, где сейчас в куче находится конкретный элемент, нужно иметь дополнительный массив размера N с соответствующими данными. Когда, например, i-й элемент добавляется в кучу, его позиция в куче заносится в массив в элемент pos. Когда два элемента в куче меняются местами (i-й и j-й), соответственно обмениваются значениями pos и pos[j]. Если i-го элемента еще (или уже) нет в куче, в pos должно быть -1 или любое другое сигнальное значение.

 

leo
Сколько угодно, бери.
Если это в правилах форума - нет проблем, постарюсь соблюдать.

Ну а если это для тебя бестолковость, лень, неуважение и ты задолбался то это твои лично проблемы.
Я видишь тоже задолбался, жизнь вобще не простая штука а неуважение это как раз твое личное необоснованное и надуманное высказывание. Можно было короче:

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

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

Всего наилучшего.

 

Так отвечаю попорядку.
crypto
Я правда сначала не понял. Твоего вопроса. Смысл до меня дошел только к вечеру.

В моем посте пункте 5 я допустил ошибку. Мы не имеем никакого права вносить log2(K) под O, потому что К у нас переменная исходя из условия задачи - Размер группы. Поэтому оно все таки влияет на скорость решения задачи. Но при К=10000 высота дерева получается 14 - Это составляет меньше чем 0.2% от 10000.

Вторая ошибка связана со сравнением времени жизни элемента. Я написал что оно равно индексу.
Это верно только на первых K элементов. Как только мы добавляем элемент с индексом больше K - мы должны вычесть из индекса К, чтобы получить время жизни.

Теперь по вопросам время работы алгоритма будет именно O(n), а не (O(N*log(K)) на полном объеме данных.
Потому что нам не нужно работать с деревом на каждой итерации.
Сейчас объясню почему:

Min и Max в дереве мы считаем только после пункта 1 и 1 раз. За время O(Log2(K)).
Нам не нужно пересчитывать время жизни каждый раз для каждого элемента дерева.
К дереву мы обращаемся только в том случае, если:
1. Истекло время жизни Min или Max. Тогда берем следующий по велечине элемент Successor(Для Min) и Predecessor(Для Max). А старый удаляем.
2. Найден элемент, который больше Max и меньше Min тогда добавляем его в дерево.

Только в этих случаях появляется дополнительный O(Log2(K))

leo
1. Нет смысла работать с кучей. Дерево размещается в заранее выделенном массиве.
Так как количество элементов в дереве будет колебаться в пределах K элементов, то для
этого понадобится память в размере: Parent(4 байта) Left(4 Байта) Right(4 Байта) Value(4 байта) LifeTime(4 байта). Размер дерева иногда может быть больше K элементов но он никогда не станет больше, чем 2*K Элементов. Это связано с тем, что в дереве нет ни одного элемента у которого время жизни больше, чем K. Таким образом общий объем памяти под дерево составит 20*2*10000 = 40Кб. Это немного.

2. Если распределение чисел равновероятное, то нам нет нужды заботится о балансировке дерева. Но если это не устраивает можно воспользоваться красно-черным деревом. Оно само себя балансирует во время добавления элемента.

То есть если уж быть совсем точным то влияние K(Размера группы) все же есть, но при K=10000 оно составляет даже не 0.2%, а намного меньше. И поэтому подпадает под погрешность вычислений. Таким образо время работы алгоритма будет O(n).

Я ответил на ваши вопросы?

 

А что если этот Successor/Predecessor не будет новым Min/Max? Ведь ты работал с деревом не на каждой итерации и мог пропустить их... Твоя ошибка в том, что ты по умолчанию предполагаешь актуальность элементов в дереве. А это возможно только если добавлять/удалять элементы на каждой итерации.

 

Приведу пример:
... 5 ... 1 9 2 3 ....

Когда "1" выйдет из окна, "2" уже должно быть в дереве. А как оно там окажется, если:

 

Atlantic
Если элемент, который мы взяли не будет новым Min Max. То есть будет <Max и >Min, Время жизни для старых Min и Max неиcтекло, то мы ничего не делаем. Просто берем следующий элемент. Просто это значит, что текущие Min и Max будут верными и для данной группы.
Смотри вот массив.

1 36 81 7 8
5 14 13 2 1
63 17 43 29 7

Всего элементов 15, а размер группы равен 5.
1. Строим дерево для первых 5 элементов.
1.1 Находим Min и Max для дерева. Это будет 1 - время жизни 0 и 81 - время жизни 2

2. Берем элемент 5. Сравниваем его с 1 и 81. 5 больше 1 и меньше 81, но у 1 время жизни истекло. Поэтому берем Sucessor - 7. У него время жизни 3. 5 меньше 7 поэтому пять становится новым минимумом со временем жизни 4.
А 81 так и остается Максимумом для новой группы.

3. Сохраняем результаты.

Дальше берем элемент 36. 36>5 и 36<81. Таким образом мы ничего с ним не делаем. И не обращаемся к дереву.

Просто сохраняем 5 и 81 как Min и Max для очередной группы.

 

Miller Rabin
Для данной группы да. Но потом пойдут ошибки. Еще один пример:
4 4 .......... 4 1 2 3 3 ....
первая группа

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

Судя по всему, когда время жизни Min/Max истекло, нужно добавлять все пропущенные элементы в соответствующее дерево, в результате опять получается алгоритм за O(N*log(N)).

 

Atlantic
Рассмотрим группу
4 4 4 4 1
2 3 3 3 3

Min 1(4) Max 4(3)

Берем 2 2>1 2<4 И время жизни у Min и Max действительное поэтому с ней ничего не делаем.
Min для следующей группы 1 - max 4.
И никаких ошибок

 

Miller Rabin
Я наверно не совсем нормально отформатировал, группы такие:
4 4 4 4 4 1
2 3 3 3 3 3

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

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

 

Да ты прав. Для 3 с индексом 8 Minimum получается 3, а не 2 как должен быть.
Здесь ошибка. Видимо не будет мне нобелевской премии

 

Miller Rabin
Скорее всего, эта задача сродни задаче сортировки сравнениями - быстрее, чем за O(N*log(M)) не получится... :\

 

Miller Rabin

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

Я даже незнаю есть ли подобное решение но буду думать ещё, возможно решение существует.
Как говорится "невозможное - возможно".

 

Miller Rabin

Угу, всего лишь на порядок ошибся - не 40Кб, а 400Кб Кэш L1 однозначно отдыхает, а L2 >= 512К только у P4 Northwod и выше, а автор кстати даже fcomi для сравнения не использует в расчете на PMMX и ниже

Atlantic, Miller Rabin
Ладно, считаем что особых проблем с выделением\освобождением памяти нет (кроме приличного размера самого дерева или двоичной кучи). Вот только объясните мне темному (без шуток) - разве двоичная куча или красно-черные деревья не требуют доп.затрат времени на поддержание балансировки и на удаление старых элементов ?

 

При добавлении элемента в Красно-черное дерево для его балансировки происходят "Вращения".
Каждое вращение занимает O(1) Времени.
Независимо от количества элементов в Красно-черном дереве для его балансировки требуется не более трех вращений.

 

Эх, кончайте разговоры хочеться увидить реальные тесты)

 

leo
Двоичная куча - это такая структура данных, которая всегда идеально сбалансирована. Так что добавление и удаление всегда требуют логарифмического времени. Погугли по словам "Heap sort".

 

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

 

Atlantic
Насчет балансировки кучи понял
Остается вопрос как старые элементы из нее удалять. Есть идеи ?

PS: Как заметил UbIvItS, этот метод хорош для получения гарантированного устойчивого результата, но как ни крути реальное время будет ~x*N*log(K), где x заметно больше по сравнению с тупым линейным просмотром - как минимум > 2, т.к. нужно вставить в дерево новый элемент и удалить самый старый, плюс неизбежные притормаживания кэша L1 при непоследовательном доступе, плюс в среднем больше штрафов за непредсказанные переходы при вставке\удалении, плюс меньше возможностей для асм-оптимизации. Одним словом для данной конкретной задачи (с К=10000 и со специфическим распределением чисел) выигрыш может оказаться незначительным