|
| Посл.отвђт | Сообщенiе |
|
|
Дата: Янв 16, 2004 13:42:55 В книге Касперски "Оптимизация программ" описывается очень "соблазнительный" алгоритм линейной сортировки. Приведен также пример сортировки чисел типа float(правда для меня непонятный ). Может у кого есть идеи как реализовать подобное,но по другому, с сохранением скорости линейной сортировки (очень надо)? P.S. В догонку: может у кого валяется исходник быстрой сортировки на асме? |
|
|
Дата: Янв 16, 2004 13:56:38 HeDiN Для чисел Float? Так он же отличается только функцией сравнения. |
|
|
Дата: Янв 16, 2004 14:01:02;tasm
;qsort(array,nitems,itemsize,cmpproc([edx],[edi])) pascal
;cmpproc must save ebp,esi,edi,edx
proc qsort nolanguage; pascal decl
arg @@arr:dword,@@len:dword,@@size:dword,@@cmpp:dword=argsize
push ebp
mov ebp,esp
mov esi,[@@arr]
mov eax,[@@len]
dec eax
mul [@@size]
lea edi,[esi+eax]
call @@qs
mov esp,ebp
pop ebp
ret argsize
@@rt:
ret
@@2:
pop esi
call @@qs
mov esi,edi
add esi,[@@size]
pop edi
@@qs:
cmp esi,edi
jae @@rt
push edi
push esi
mov edx,esi
sub esi,[@@size]
add edi,[@@size]
@@0:
sub edi,[@@size]
call [@@cmpp]
test eax,eax
jl @@0
xchg esi,edi
@@1:
add edi,[@@size]
call [@@cmpp]
test eax,eax
jg @@1
xchg esi,edi
cmp esi,edi
jae @@2
mov ecx,[@@size]
jmp @@5
@@4:
dec ecx
mov al,[esi+ecx]
xchg [edi+ecx],al
mov [esi+ecx],al
jz @@0
@@5:
test cl,3
jnz @@4
@@3:
sub ecx,4
mov eax,[esi+ecx]
xchg [edi+ecx],eax
mov [esi+ecx],eax
jnz @@3
jmp @@0
endp qsort |
|
|
Дата: Янв 16, 2004 14:10:20 А это в качестве бонуса: (defun qsort(list meth % Local: % l0 l1 l2 key)
((null list) NIL)
((null (cdr list)) list)
(setq key (car list))
(loop
((null list))
(if (eval (list meth (car list) key))
(setq l0 (cons (car list) l0))
(if (eval (list meth key (car list)))
(setq l2 (cons (car list) l2))
(setq l1 (cons (car list) l1))
)
)
(setq list (cdr list))
)
(append (qsort l0 meth) l1 (qsort l2 meth))
)
(qsort '(1 6 23 8 12 5 12 0 4 41 14 6 22 7 9 0) <)
(qsort '(1 6 23 8 12 5 12 0 4 41 14 6 22 7 9 0) >)
(return) |
|
|
Дата: Янв 16, 2004 14:27:58 · Поправил: HeDiN Edmond Непонятна функция PrepareMem()( из книги). Дальше по тексту:" Во-первых, не плохо было бы проверить, чем закончилось выделение 16 Гбайт памяти". Почему 16, а не 4, (float ведь 32 бита). Где под Windows мы возьмем пускай 4 гига, без извращений с разделением на процессы(как у Касперски)? Black_mirror Thx. Только мне бы хотелось обойтись без вызова функции сравнения,т.е. встроить ее код в основной. И объясни,пожалуйста, бонус :) |
|
|
Дата: Янв 16, 2004 16:40:38 HeDiN Я посмотрю её дома. Что насчёт касперски, АWE позваляет использовать свыше 2 Гб |
|
|
Дата: Янв 16, 2004 17:08:44@@2:
pop esi
call @@qs
lea esi,[edi+4]
pop edi
@@qs:;(esi - pfirst, edi - plast)
cmp esi,edi
jae @@rt
push edi
push esi
mov edx,esi
sub esi,4
add edi,4
@@0:
sub edi,4
fld dword [edx]
fcomp dword [edi]
fstsw ax
sahf
jc @@0
xchg esi,edi
@@1:
add edi,4
fld dword [edx]
fcomp dword [edi]
fstsw ax
sahf
ja @@0
xchg esi,edi
cmp esi,edi
jae @@2
mov eax,[esi]
xchg [edi],eax
mov [esi],eax
jmp @@0
@@rt:
ret
А что касается бонуса то это тот же quick-sort только на языке lisp. list это список который нужно отсортировать, meth это та же функция сравнения. Если в списке 0 элементов то функция возвращает пустой список. Если в списке 1 элемент то возвращается сам список. Далее первый элемент выбирается в качестве ключа, а затем все элементы распределябтся по трем спискам: в l0 - '<key', в l1 - '=key', а в l2 - '>key' (в предположении, что в качестве meth используется '<'). После чего, в качестве результата, возвращается объединение отсортированного l0 ,l1 и отсортированного l2. |
|
|
Дата: Янв 16, 2004 17:31:08 Edmond Извиняюсь, за темноту, но что такое AWE? Black_mirror Я листинг на Лиспе буду вместо мантры при медитации использовать:))) |
|
|
Дата: Янв 16, 2004 18:50:53 HeDiN Addres Window Extention (прошу прощения за плохой Английский) :() |
|
|
Дата: Янв 17, 2004 14:32:01 · Поправил: HeDiN Вот еще непонятное место: "Причем, этот результат можно существенно улучшить, если прибегнуть к услугам разряженных массивов, а не тупо сканировать массив vurtual_array целиком!" 1. Массив vurtual_array упоминается только в этом месте и о его назначении можно только догадываться. 2. Кто-нибудь может сказать в чем идея, наверное все таки разреженных, а не разряженных массивов?? |
|
|
Дата: Янв 17, 2004 18:28:50 · Поправил: Black_mirror HeDiN Смысл алгоритма линейной сортироваки в подсчете сколько раз встречается какое значение элемента, после чего идет сканирование всех значений, и запись в исходный массив каждого из них столько раз, сколько оно встретилось в исходном массиве: lsort(type *a,int n)
{
int count[type];//в качестве индекса могут
//использоваться все значения type
for(type j=type_min;j<=type_max;j++)
count[i]=0;
for(i=0;i<n;i++)
count[a[i]]++;
i=0;
for(j=type_min;j<=type_max;j++)
while(count[j]--)
a[i++]=j;
}
Что касается разреженных массивов то здесь Крис наверное имел ввиду следующее: Разбиваем массив count на несколько частей. Для кажной части при заполнении будем подсчитывать сумму. При сканировании если сумма равна нулю, значит данную часть можно не сканировать. Рекомендую посчитать на сколько это улучшит производительность. 8) |
|
|
Дата: Янв 17, 2004 20:30:28 · Поправил: volodya Black_mirror Криса, как алгоритмизатора я уважаю не слишком... Слушай, объясни мне тупому:
for(int i=0;i<p;i++)
count=0;
for(i=0;i<p;i++)
count[a[p]]++;
т.е., в худшем случае это O(n*2)? Где применяется линейная сортировка? Смысл? [i]Рекомендую посчитать на сколько это улучшит производительность И опять я не догоняю :( Если массив разбивать на части - то, так или иначе, через него придется(!) пройти раз - т.е. это уже O(n)... Потом считать сумму - это еще раз. При сканировании если сумма равна нулю А это с какой радости? Хотя, к сожалению, я эту книгу не читал. Чего-то внятного сказать не могу. Вы же оперируете терминами текста :((( Надо будет взять... |
|
|
Дата: Янв 17, 2004 21:26:13 volodya Прошу прощения меня малость(или не малость) переглючило. Код исправлен. Линейной сортировка называется потому, что время ее работы линейно зависит от числа элементов исходного массива.(Время выполнения первого цикла от размера сортируемого массива не зависит.) |
|
|
Дата: Янв 17, 2004 21:40:57 volodya count[100];
sum[10];
for(int i=0;i<n;i++)
{
count[a[i]]++;
sum[a[i]/10]++;
}
i=0;
for(j=0;j<100;j+=10)
{
if(sum[j/10]>0)
for(int k=j;j<k+10;j++)
while(count[k]--)
a[i++]=k;
}
А книгу эту я тоже не читал. |
|
|
Дата: Янв 17, 2004 22:28:43 Теперь более-менее понятно. Спасибо большое. Вопрос - область применения? Ведь быстрая сортировка тоже достаточно стабильна! |