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

Nouzui
Лучше использовать сравнение >= max
Хотя для вещественных чисел совпадение маловероятно, но все же так логичнее - при совпадении c max индекс maxi будет передвигаться дальше от начала окна

 

leo
угу

 

Nouzui
На коленке...

Размер maxindex'а можно подобрать по данным.
P.S. Добавлено чуть позже:
// (*(maxindex) == i - k) *(++maxindex) = *(maxindex); - сразу не подумал

 

t00x

Можно, но не нужно, т.к. ты упорно продолжаешь решать свою задачку поиска максимума на растущем интервале 1..i, а нужно на скользящем интервале фиксированного размера i-k..i, где k=10000

 

leo
Зачем каждый раз пересчитывать интервал? Одинаково придётся все данные перебирать.

 

Miller Rabin
мой алгос считает массивы выровненые по границе, а у Pavia именно идёт поиск макс./мин. в окне на каждом шаге - это совершенно разные вещи.

 

t00x

Потому, что задача так поставлена изначально - выдать Max и Min на скользящем интервале, т.е. показать динамику их изменения во времени. А у тебя что получается - если где-то в начале массива попадется самый большой максимум, то он так и останется до конца массива, хотя по условию задачи мы должны его выбросить когда он выйдет за пределы окна

 

запоздало пришло в голову, что я загнался с размерностями - там, где у меня в коде встречалось n-k нужно писать n-k+1

 

leo
Sorry. Добавил строчку

чуть позже.

Nouzui

Это понятно.

leo
P.S. Поторопился.

P.P.S. Или добавить ещё массив, в который записывать индексы если *p<*p[i+1]. Потом по нему считать 10000.

 

t00x
Ну и сколько раз ты будешь торопиться ?
А max = MININT как стоял колом, так и стоит ))

 

leo

Код (Text):

1. template<class T, int n, int k>
2. void func(/*IN*/ T (*p)[n], /*OUT T(*p1)[n-k]*/ OUT T(*maxindex)[n]) {
3.         int i, j, m;
4.         T max, gmax;
5.     max = MINDOUBLE;
6.     gmax = max;
7.     int* localindex[k];
8.  
9.         for(i= 0; i<n; i++) {
10.         if (*p[i]>max) {            // save max index
11.             *(maxindex++) = i;
12.             if (*p[i] > gmax) {
13.                 gmax = *p[i];   // globalMax
14.                 m = 0;          // index in table localindex
15.             } else {
16.                 *(localindex[m++]) = i;
17.             }
18.         }
19.         if (*(maxindex) == i - k)  {
20.             for (j = 0; j < m; j++) if (*p[localindex[j]] > max) *(maxindex) = localindex[j]; // k = 10000
21.             gmax = *p[*(maxindex)]; //globalmax = last max
22.             m = 0;
23.         }
24.         }
25. }

Это с массивом localindex и переменной gmax, m - индекс для localindex.
Если меньше gmax'а - индекс в localindex, в котором будем искать max(10000).

 

Вот он код, тот, что есть оптимизированный вариант.

Miller Rabin - а ты мужчина или женщина ? я просто перечитывал твои сообщения и никак немогу понять

Код (Text):

1. struct RatesInfo
2.        ctm     dd      ?
3.        open    dq      ?
4.        low     dq      ?
5.        hihg    dq      ?
6.        close   dq      ?
7.        vol     dq      ?
8. ends
9.  
10. ;Rates - массив с элементами, каждый элемент представляет собой структуру RatesInfo (из неё нужен только "close")
11. ;buffer_size - Количество элементов в массиве
12. ;Length - длинна окна
13. proc X Rates, buffer_size, Length
14.  
15.         local __Highest:QWORD, __Lowest:QWORD, \
16.               __IndexLast:DWORD, __IndexLowest:DWORD, \
17.               __IndexHighest:DWORD, __StartTicks:DWORD
18.  
19.         push ebx ecx edx esi edi
20.  
21.         ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
22.         invoke GetTickCount
23.  
24.         mov dword [__StartTicks], eax
25.         ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
26.  
27.         mov esi, [Rates]
28.         mov ecx, [buffer_size]
29.         cmp ecx, [Length]
30.         jb .ret
31.         cmp [Length], 0
32.         je .ret
33.  
34.         stdcall StepUp, sizeof.RatesInfo, [Length]
35.         add esi, eax
36.  
37.         sub eax, sizeof.RatesInfo
38.         mov dword [__IndexLast], eax
39.  
40.         stdcall StepUp, sizeof.RatesInfo.close, [Length]
41.         add edi, eax
42.  
43.         sub ecx, [Length]
44.  
45.         finit
46.  
47.         push ecx edi
48.  
49.         lea ebx, [__Highest]
50.         lea edx, [__Lowest]
51.         lea ecx, [__IndexHighest]
52.         lea edi, [__IndexLowest]
53.  
54.         stdcall GetHighestLowest, esi, [Length], ebx, edx, ecx, edi
55.  
56.         pop edi ecx
57.  
58. .lp:
59.         mov eax, esi
60.         sub eax, dword [__IndexLast]
61.  
62.         cmp dword [__IndexHighest], eax
63.         jb .recount
64.         cmp dword [__IndexLowest], eax
65.         jb .recount
66.  
67.         fld qword [esi + RatesInfo.close]
68.         fcom qword [__Highest]
69.         fstsw ax
70.         sahf
71.         jna .ch_low
72.  
73.         fst qword [__Highest]
74.  
75.         mov dword [__IndexHighest], esi
76.  
77. .ch_low:
78.         fcom qword [__Lowest]
79.         fstsw ax
80.         sahf
81.         jnb .fcompare
82.  
83.         fst qword [__Lowest]
84.  
85.         mov dword [__IndexLowest], esi
86.  
87. .fcompare:
88.  
89.         fstp st0
90.  
91.         jmp .ecompare
92.  
93. .recount:
94.  
95.         push ecx edi
96.  
97.         lea ecx, [__IndexHighest]
98.         lea edi, [__IndexLowest]
99.  
100.         stdcall GetHighestLowest, esi, [Length], ebx, edx, ecx, edi
101.  
102.         pop edi ecx
103.  
104.         ; в этом месте значения локальных переменных __Highest, _Lowest соответственно
105.         ; содержат пминимальное и максимальное значение (за окно Length) для текущего элемента массива
106.  
107.         add esi, sizeof.RatesInfo
108.  
109.         dec ecx
110.         jnz .lp
111. .ret:
112.  
113.         ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
114.         invoke GetTickCount
115.  
116.         sub eax, dword [__StartTicks]
117.         ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
118.  
119.         pop edi esi edx ecx ebx
120.  
121.         ret
122. endp
123.  
124. proc GetHighestLowest Rates, Length, lpHighest, lpLowest, lpIndexHighest, lpIndexLowest
125.  
126.         push ebx ecx edx esi
127.  
128.         mov ebx, dword [lpHighest]
129.         mov edx, dword [lpLowest]
130.         mov ecx, dword [Length]
131.  
132.         fld  qword [esi + RatesInfo.close]
133.         fst  qword [ebx]
134.         fstp qword [edx]
135.  
136.         mov eax, dword [lpIndexHighest]
137.         mov dword [eax], esi
138.  
139.         mov eax, dword [lpIndexLowest]
140.         mov dword [eax], esi
141.  
142.         sub esi, sizeof.RatesInfo
143.  
144.         dec ecx
145.         jz .ret
146.  
147. .lp:
148.         fld qword [esi + RatesInfo.close]
149.         fcom qword [ebx]
150.         fstsw ax
151.         sahf
152.         jna .ch_low
153.  
154.         fst qword [ebx]
155.  
156.         mov eax, dword [lpIndexHighest]
157.         mov dword [eax], esi
158.  
159. .ch_low:
160.         fcom qword [edx]
161.         fstsw ax
162.         sahf
163.         jnb .continue
164.  
165.         fst qword [edx]
166.  
167.         mov eax, dword [lpIndexLowest]
168.         mov dword [eax], esi
169.  
170. .continue:
171.  
172.         fstp st0
173.  
174.         sub esi, sizeof.RatesInfo
175.  
176.         dec ecx
177.         jnz .lp
178.  
179. .ret:
180.         pop esi edx ecx ebx
181.  
182.         ret
183. endp
184.  
185. proc StepUp __Size, __Steps
186.  
187.         push ebx ecx edx
188.  
189.         mov eax, dword [__Size]
190.         mov ebx, dword [__Steps]
191.         mul ebx
192.  
193.         pop edx ecx ebx
194.  
195.         ret
196. endp

 

Miller Rabin

Для того, что бы тебе понять мою квалификаию по поводу кода,
зайди на www.linuxassembly.org на этот сайт помещен мой проект Traffic Accounting (traffic accounting daemon),
это биллинговая система (учет интернет-трафика) написанная под Linux на nasm.
В ней заложены более 100 различных функций для учета, это самый мощный из свободных проектов по учету трафика, и написан на assembler от начала до конца.
Правда в последствии он был мною же переписан на С, для совместимости с другими процессорами т.к. вести проект для разных систем, одному человеку было черезчур затратно по времени.

Это один из 18 проектов выложенных на этот сайт за несколько лет.

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

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

Проводился такой эксперимент - были набраны люди из низкой социальной группы (бездомные, бомжи и т.п.),
каждому из них был выделен отдельный компьютер на котором запущен торговый терминал валютной биржи,
было обяснено каким образом кликая мышкой можно заработать деньги. И бомжи зарабатывали деньги! Как говорится не отходя от кассы, по простой торговой системе.
Далее эти отчеты по сделкам были показаны начальниками отделов по ценным бумагам нескольким Управляющим Компаниям, и какого же было их удивление когда их самые лучшие трейдеры торговали хуже и зарабатывали меньше, со своим хваленым образованием, чам бомжи и пьяницы!! Удивление одной было настолько сильное что встал даже вопрос об увольнении комманды трейдеров. Так же после этого была создана компания где управляющими были бомжи, но она не имела успеха так как люди не доверяли, и в этом ничео удивительного, ты доверишь свои 100 тыс. USD бомжу ?

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


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

Ты что то подобное сделал Miller Rabin, кроме окончания университета, как миллионы бомжей ? - сомневаюсь. Поэтому веди себя по человечески справедливо, и жизнь (природа/бог), тебя наградит поверь мне.

Ничто не ново под луной.

 

Yashin_Sergey
кстати, вопрос от тех кто давно не занимался асмом (тоесть от меня -)) ты мин. и макс. в одном цикле считаешь??

 

Да в одном.

 

/offtop
Бандиты отнимают деньги.
Убийцы отнимают жизни.
Медики отнимают и то и другое.

современный юмор

 

Yashin_Sergey
ты в этом цикле считаешь мин. и макс. одновременно??

 

Да, у меня в одном цикле считаются мин. и макс. одновременно.
Здесь странного ничего нет так как мин. ничем по СУТИ не отличается от макс,
поэтому зачем циклить два раза когда можно найти за один цикл,
т.к. минимум и максимум могут быть равны, например.

 

я б разделил бы эти циклы: мин. и макс. одновременно из окна вылетить не могут.

 

Это правда можно разделить, для больших окон от (100 элементов) вероятность очень маленькая, но на меньших окнах вероятность растет, смотря на данных какого периода использовать (это уже свойства самих данных для конкретной задачи).
Да и потом, так как цикл всё равно проходит один раз, то убрав одну "лишнюю" проверку на макс. или мин. заметного прироста в скорости не будет, поэтому я и не разделял.