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

Yashin_Sergey
Странноватый у тебя код в плане оптимизации
Вроде регистров предостаточно и целочисленных и FPU, а у тебя сплошые загрузки\выгрузки в память. И сравнения fpu-шные существенно быстрее работают на fcomi - или ты еще на древние процы ниже PIII расчитываешь ?

 

Спасибо большое, просто меня эти результаты устраивают, конечно можно и лучше кто спорит.
Про fcomi я знаю, неиспользую потому, что может быть такое что надо будет запустить на машине ниже PIII,
а в виду того что надо будет переписывать возникнут издержки, в общем только из-за рисков не использую.

 

Так. С чего бы начать

Yashin_Sergey
Ну дождался наконец-то выложил свой код. Значит работаем все-таки с плавающей точкой. ОК. Сегодня вечером я с ним подробно познакомлюсь. И подготовлю свое решение относительно ТВОИХ условий задачи.

Касательно твоего последнего поста я тебе вот что скажу.
Ты все никак не можешь обойтись без оскорблений.

Мне 23 года. Я закончил КГТУ примерно пол-года назад. Несмотря на это я уже являюсь руководителем группы информационной безопасности. Выполнил я не 18 проектов, а только 5. Последний из них посвящен применению метаморфного кода как средства защиты от взлома и, возможно, для оптимизации генерируемого кода компилятором. Он еще не закончен, но я планирую его закончить к зиме.Я знаю о чем я говорю, потому что являюсь одним из лучших специалистов в нашем крае по обеспечению информационной безопасности. О чем свидетельствует сертификат, который висит на стене у меня в рабочем кабинете. Относительно других 4 проектов они закончены и упешно работают на уровне корпорации. Первым моим проектом было создание механизма обеспечивающего поиск клонов в GSM сетях из более чем 5 миллионов абонентов. Поверь, по сложности это не уступает твоему биллингу. И они все реазлизованы на ассемблере. Про остальные три я ничего не буду писать так как это сильно раздует пост. Да ни к чему, пожалуй.

Сейчас мои усилия направлены на развития навыков работы в команде. А именно на том, чтобы ставить задачу таким образом, чтобу все в моей команде ее поняли и работали с максимальной отдачей.

К чему это я. Я рассказал об этом только в ответ на твой пост. И никогда не привожу эти доводы в качестве
аргументов своей правоты. Связано это с тем что в этом форуме ВСЕ РАВНЫ и бомжи и специалисты по информационной безопасности и такие как ты .

Высокомерие и тщеславие это признак скудности ума, а не профессионализма.

На этом форуме присутствует очень много сильных и умных людей с некоторыми из них я имею счастье даже быть знакомым лично. Поэтому ВЕДИ СЕБЯ КОРРЕКТНО.

По поводу твоей задачи. Я по прежнему уверен, что ее можно решить за время O(n). И я попробую это сделать. Результат я выложу в понедельник. Чего мне не хватало так это четкой постановки задачи, которую можно взять только из твоего кода. Так как сам ты не умеешь выражать свои мысли. Я даже уже знаю как я это сделаю. Но перед математическим обоснованием я все же хочу получить реальные цифры.

И тот аргумент, что все тебя поняли кроме меня. Неверен в корне. Об этом свидетельствуют последние посты Noizui, когда он привел свой код.

 

Nouzui
К моим вопросам относительно типов данных и переписывание чужого кода.
Переписал твой первый код на FASM получилось примерно вот что

Выполняется этот при параметрах ArrayLength = 200000 и GroupLength = 10000. Этот код выполняется на моей системе за 423ms, что никак не сочетается с 10585ms у топикстартера. Потому, что топик стартер работает с плавающей точкой. В любом случае это уже совсем другая программа нежели у тебя.

Код (Text):

1. proc MinMax InArray, ArrayLength, GroupLength, OutArray
2.     local Limit1: DWORD, Limit2: DWORD
3.    
4.     mov esi, [InArray]
5.     mov edi, [OutArray]
6.     mov eax, [ArrayLength]
7.     sub eax, [GroupLength]
8.     mov [Limit1], eax
9.     mov eax, [GroupLength]
10.     shl eax, 2
11.     mov [Limit2], eax
12.  
13.     xor ecx, ecx
14. .lbILoop:
15.         mov ebx, [esi+ecx]
16.         lea edx, [ecx+4]
17.  
18. .lbJLoop:
19.             cmp [esi+edx], ebx
20.             cmova ebx, [esi+edx]
21.             add edx, 4
22.             cmp edx, [Limit2]
23.             jc .lbJLoop
24.        
25.         add [Limit2], 4
26.         mov [edi+ecx], ebx
27.         add ecx, 4
28.         cmp ecx, [Limit1]
29.         jc .lbILoop
30.  
31. ret
32. endp

Касательно твоего второго кода я его выложу, если в этом будет хоть какой-нибудь смысл
Связано это вот с чем? А что в массиве 1,2,3,4,5 для цифры 3 - 1 и 2 не будут разве являться соседями? Если размер группы равен 5.

 

/offtop
теперь можно делать ставки на понедельник) - но то, что эта тема будет мне интересна как мин. до понедельника - это на все 100 пудов

 

Походу мы попали в разбору двух титанов.
Один крупный специалист по билинговым системам, другой один из лучших специалистов своего края по обеспечению информационной безопасности.
Что-то видать будет грандиозное. Видимо надо ожидать прорыва в одной из областей науки.
Только не подумайте что я прикалываюсь, возможно что так оно и есть.
Только маленький совет: любите искусство в себе, а не себя в искусстве.

 

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

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

То, что ты руководитель - прекрасно в 23 года. Мои должности и прошлые и текущая совсем не хуже, поверь мне да и лет мне 24. Этот факт комун-нибудь нужен ? Мне нет, а тебе ? тоже думаю нет, просто ты не один такой, опять же. Будь вежливее.

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

Далее я думаю не стоит тратить нервы друг другу а общаться, как ты выразился "КОРРЕКТНО", жду этого в первую очередь от тебя.

 

В массиве 1,2,3,4,5 для цифры 3 - 1 и 2 являются соседями, но для цыфры 3 просчитывать мин. макс. в моем случае здесь не нужно т.к. соседей меньше чем 4. Здесь нужно будет просчитывать мин. и макс. начиная с цыфры 5. Если брать размер группы равной 5.

 

Публикую решение задачи выполняющей алгоритм за O(n).

Пусть дан массив в котором 200000 элементов.
Задача: Найти минимумы и максимумы для всех групп элементов по 10000 в каждой.

1. Берем первую группу элементов в 10000. Строим двоичное дерево. В двоичном дереве сохраняем сами значения элементов и их время жизни(Индекс)
Почему время жизни? Просто если элемент имеет индекс 3, это значит что элемент будет находится в трех группах.

2. Берем следующий элемент L (Изначально 10001-ый)
2.1 Если время жизни элементов Min или Max из Дерева действительное(То есть они еще входят в состав новой группы), то в случае, если L будет меньше Min, или больше Max, оно добавляется в дерево и соответственно становится новым Min или Max.
2.2 Если время жизни элемента Min или Max из дерева уже не действительное, то удаляем этот элемент из дерева. А вместо него берем Successor(Predecessor) - Элемент следующий(предыдущий) по значению. Проверяем его время жизни, если недействительно, то берем еще один Successor(Predecessor). и т.д. И он соответственно становится новым Min или Max. Переходим к пункту 2.1

2.4 Сохраняем Min и Max для группы.
2.3 Переходим к пункту 2. Пока не перебрали все элементы в массиве

А теперь самое интересное
Оценка времени алгоритма.

1. Пункт выполнится 1 за O(k) Это грубовато, так как вообще-то время добавления зависит от высоты дерева. Поэтому здесь будет небольшой множитель x, но это не отразится на времени вычисления. Так как конечное время не выйдет за пределы погрешности. Тем более, что вычисления Min и Max можно вынести из цикла. И посчитать их уже после за O(log2(k)) - будет порядка 14

2. Вычисления Min и Max занимают в худщем случае O(log2(k)).

3. Вычисление Элемента следующего по значению занимает O(log2(k))

4. Log2(k) - Это высота дерева. Почему? Потому что в дереве будет всегда около 10000 элементов. Количество элементов в дереве зависит только от количества элементов в группе и времени жизни Min и Max и не зависит от общего количества элементов в массиве. Поэтому общее количество элементов не будет сильно отклонятся от 10000. А значит высота дерева будет постоянной.

5. Что такое O(n) это означает что перед n есть какая-то константа, которая опеределяется оптимальностью кода, возможностями процессора и прочей байдой(Но не зависит от n). Log2(k) тоже не зависит от n. А значит ее можно внести под O

Таким образом время выполнения алгоритма составляет O(n)

Касательно выполнения кода. Мой старый код выполняется за 480мс в среднем. Этот код выполняется за 2мс,
При использовании Красно-черных деревьев. И 2-10мс при использовании обычных деревьев. Такой разброс связан с равномерностью распределения чисел в массиве.

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

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

Я мог что-то недосказать в описании алгоритма или постановке задачи. Если что-то непонятно спрашивайте я отвечу.

Yashin_Sergey
Каким способом тебе удобно выплатить мне нобелевскую премию?

P.S.: Это не единственный алгоритм решения. Суть не в этом задача нахождения Min и Max какой бы извращенной она не была, может быть решена за O(n). Связано это с тем, что расположение элементов в исходном массиве в любой момент времени остается постоянным, в отличие от сортировки, например.

 

Miller Rabin
Простите бедного старого еврея, я еще не смог оценить красоту и мощь приведенного алгоритма -, но вот мне, простому среднеоплачиваемому специалисту в области математики, непонятно утверждение 5: параметр k на самом деле влияет на оценку сложности - для k = O(1) утверждение правильно, а вот для k=alpha*n (С1<=alpha<=C2) (что мы имеем в рассматриваемом случае - из соотношения 200000 к 10000) это уже не так. Видимо сложность алгоритма будет определяться двумя параметрами n и k.
ЗЫ
Кстати, Нобелевскую премию математикам не выдают из-за одного кобеля, испортившего настроение Нобелю. Кроме того, Сергей вряд-ли имеет отношение к выдаче премий.

 

crypto
Да я это вот к чему.
Yashin_Sergey

По поводу утверждения 5. В пункте 1 мы заполнили дерево 10000 элементов.
Когда мы последовательно сравниваем оставшиеся элементы в 2, с Min и Max то мы удаляем те Min, Max для которых время жизни недействительное. И добавляем новый элемент, если он стал новым Min или Max. Таким образом количество элементов в дереве всегда будет около 10000 элементов. Независимо от общего размера массива.

 

Miller Rabin
А что такое параметр k? Я из контекста вынес для себя, что этот параметр связан с размером группы (10000 в рассматриваемом примере). И у меня естественно сразу возник вопрос о соотношении между параметрами n и k. Если оценивать сложность алгоритма, то она должна зависеть от этих двух параметров.

 

Из описания не совсем ясно решение, но это не проблема.

С нетерпением жду кода.

 

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

 

A. сформировать дерево.
Б. на каждом шаге перестраивать дерево.
В. искать мин./макс.
------------------------------------------------------
ну, никак это не тянет на O(n).

 

Miller Rabin
UbIvItS правильно написал. В дерево нужно всегда добавлять новый элемент, независимо от текущего минимума/максимума (вдруг этот новый элемент потом станет минимумом/максимумом), так что время работы будет O(N*log(M)), где M - размер группы.

 

Правильно, и в связи с этим:
1) необходимость удаления старых элементов,
2) проблемы разбалансировки дерева,
3) проблемы реализации - если создавать\освобождать память под элементы через HeapХХХ, то это скушает страшно подумать сколько времени, значит нужно городить свой менеджер

PS:
Yashin_Sergey
Модераторы видать отдыхают, поэтому беру огонь на себя - сверхцитирование это не только нарушение правил форума, но и показатель лени, бестолковости и неуважения к участникам форума. В последем посте у тебя на 2 строчки ответа приходится х.з. сколько строк цитаты. Я лично уже задолбался прокручивать эти никчемные портянки, неужели нельзя выделить несколько основных строк для цитаты ?!!

 

leo
/offtop
давно хочу замастырить форум (на флэше, наверно, ваять буду)), чтобы избавляться от такого гнусного пожирания траффика)

 

leo
Все 3 проблемы легко решаются с помощью такой структуры данных, как двоичная куча: она всегда идеально сбалансирована, реализуется с помощью массива, и позволяет находить минимальный (максимальный элемент) за единичное время, время вставки/удаления в худшем случае - O(log(M)). Правда, придется поддерживать одновременно две кучи для минимума и максимума. Так что алгоритм за O(N*log(M)) вполне реален, и практическая его реализация может быть достаточно быстрой.

 

Atlantic
Подразумевается что время O(N*log(M)) будет на полном наборе данных?