Поразрядная сортировка....

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

persicum

Не путай дерево с многосвязным списком (который тоже можно организовать деревом, но это частный случай .
Здесь построение дерева заключается в запоминании ссылок на узлы. Корневой узел это указатель на первое число с 1 в старшем бите (или последнее с 0 в старшем бите если так больше нравится) после упорядочивания по старшему биту. Сортировка по следующему биту ведётся раздельно до и после корневого узла, после чего аналогично находится узел-развилка, коих будет уже 2 (слева и справа от корневого) и т.д. Этим уменьшается количество сравнений и появляется возможность отсекать ветви которые достаточно упорядочить по n старших бит, а до конца пробегаются только те ветви, в которых это действительно нужно. Максимальные накладные расходы на это по одному указателю на бит, т.е. для сортировки 32 разрядных чисел достаточно всего 32 dword под указатели.

ЗЫ: безбранчевость или уменьшение количества ветвлений далеко не всегда компенсируют алгоритмические недостатки.

 

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

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

Вечером время будет, врублюсь в написаное. В принципе для чего тема создана. Если есть идеи, то в бой (и время не забудьте померить). Только случайно не сделайте мутанта, кот. с Radix ничего общего не имеет....=)

 

Прошу прощения за то, что людям не лень писать, а мне лень въезжать в написанное...
Только я на взгляд не вижу экономии от развилок, допустим, второй бит создает две развилки, третий бит - четыре развилки, но две половинные развилки - это опять целое, четыре четверые развилки - опять целая нота, как в музыке. Каждый бит нужно хотя бы единожды просмотреть, имхо.
Так что предложенный алгос - самый быстрый из битовых. Сброс в m=n это и есть развилка

 

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

 

Помедитировал тщательнее - убедился что действительно всё классно 32 полных пробега по массиву - меньше можно только если сделать досрочный выход, но это не так просто и накладные расходы от проверки условий досрочного выхода большие будут. В асм варианте (#7) есть мелкие баги (rw вместо rd, old не инициализировано и выход по переполнению lay а не mask из-за которого один лишний пробег), но в Сшном (#19) они пофиксены.

Код (Text):

1.   xor ebx,ebx       ; old
2.   xor ecx,ecx       ; lay
3.   mov edx,80000000h ; mask
4.   .0: mov esi,array
5.       mov edi,esi
6.       .1: mov    eax,[esi]
7.           xor    eax,ebx
8.           test   eax,ecx
9.           cmovnz edi,esi
10.           mov    eax,[esi]
11.           cmovnz ebx,eax
12.           test   eax,edx
13.           jnz .2
14.               xchg eax,[edi]
15.               mov  [esi],eax
16.               add  edi,4
17.           .2: add  esi,4
18.       cmp esi, array+size*4
19.       jc .1
20.       or  ecx,edx
21.       shr edx,1
22.   jnz .0

 

Не оно?
http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%80%D0%B0%D0%B7%D1%80%D1%8F%D0%B4%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0

 

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

 

Folk Acid
Ты предлагаешь вместо "(здесь был неработающий алгоритм сортировки; просьба к авторам, поправить или убрать)", записать этот?

 

Он для учебных целей помойму плохо подходит))

 

Это правда, old инициализируется сама по мере надобности. Но компилятор ругается. Поэтому old можно приравнять нулю, по смыслу не перед первым циклом, а перед внутренним, типа n=m=old=0

Y_Mur, мне твой код понравился, более того, попробовал сам написать, и невольно повторил, ну правда у меня там loop был. Но что удивительно, не знаю почему, этот код (твой и мой) работает в 2 раза медленнее чем компилятор сгенерил. А кампилятор обычную туфту сгенерил, жестокие and вместо test, постоянные обмены с памятью типа mov eax,[ebp+ecx*4]; mov [esp-4],eax короче обычна туфта.
сидел час разбирался где зарыты тормоза, так ничего и не придумал...

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

 

persicum
Разворот цикла и разбивка медленной xchg на отдельные команды, это понятно и тоже стоит применить (при развороте size должно быть кратно кратности разворота или нужен дополнительный выпендрёж, чтобы не выскочить за границы массива). Ещё можно добавить предвыборку, частично разбивающую цепочку зависимых команд mov -> xor -> test -> cmovnz.

Код (Text):

1.   xor ebx, ebx      ; old
2.   mov [lay], 0
3.   mov edx, 80000000h    ; mask
4.   align 16
5.   .0: mov esi, array
6.       mov edi, esi
7.       mov ecx, [esi]
8.  
9.       macro body_loop
10.       {
11.           mov    eax, ecx
12.           xor    ecx, ebx
13.           test   ecx, [lay]
14.           mov    ecx, [esi+4]
15.           cmovnz edi, esi
16.           cmovnz ebx, eax
17.           test   eax, edx
18.           jnz @F
19.               mov  ebp, [edi]
20.               mov  [edi], eax
21.               mov  [esi], ebp
22.               add  edi, 4
23.           @@: add  esi, 4
24.       }
25.      
26.       align 16
27.       .1: body_loop
28.           body_loop
29.           body_loop
30.           body_loop
31.       cmp esi, array+size*4
32.       jc .1
33.       or  [lay], edx
34.       shr edx,1
35.   jnz .0

Но компилятор vs2005 противопоставляет этому: 5х разворот вместо достаточных 4х, je вместо cmovnz, даже не пытается разделять цепочку mov -> xor -> test -> je чем-то полезным, адресацию вида [eax*4+403378] вместо [esi], плюс кучу явно нелогичных команд...

Код (Text):

1. 00401035  |.  33DB          XOR EBX,EBX
2. 00401037  |.  33D2          XOR EDX,EDX
3. 00401039  |.  C74424 14 000 MOV DWORD PTR SS:[ESP+14],80000000
4. 00401041  |>  33C0          /XOR EAX,EAX
5. 00401043  |.  33C9          |XOR ECX,ECX
6. 00401045  |.  8D78 02       |LEA EDI,[EAX+2]
7. 00401048  |.  EB 06         |JMP SHORT 00401050
8. 0040104A  |   8D9B 00000000 |LEA EBX,[EBX]
9. 00401050  |>  8BB1 78334000 |/MOV ESI,DWORD PTR DS:[ECX+403378]
10. 00401056  |.  8BEE          ||MOV EBP,ESI
11. 00401058  |.  33EA          ||XOR EBP,EDX
12. 0040105A  |.  85EB          ||TEST EBX,EBP
13. 0040105C  |.  74 05         ||JE SHORT 00401063
14. 0040105E  |.  8D47 FE       ||LEA EAX,[EDI-2]
15. 00401061  |.  8BD6          ||MOV EDX,ESI
16. 00401063  |>  8B6C24 14     ||MOV EBP,DWORD PTR SS:[ESP+14]
17. 00401067  |.  85F5          ||TEST EBP,ESI
18. 00401069  |.  75 17         ||JNE SHORT 00401082
19. 0040106B  |.  8B2C85 783340 ||MOV EBP,DWORD PTR DS:[EAX*4+403378]
20. 00401072  |.  89A9 78334000 ||MOV DWORD PTR DS:[ECX+403378],EBP
21. 00401078  |.  893485 783340 ||MOV DWORD PTR DS:[EAX*4+403378],ESI
22. 0040107F  |.  83C0 01       ||ADD EAX,1
23. 00401082  |>  8BB1 7C334000 ||MOV ESI,DWORD PTR DS:[ECX+40337C]      ; ASCII "#H"
24. 00401088  |.  8BEE          ||MOV EBP,ESI
25. 0040108A  |.  33EA          ||XOR EBP,EDX
26. 0040108C  |.  85EB          ||TEST EBX,EBP
27. 0040108E  |.  74 05         ||JE SHORT 00401095
28. 00401090  |.  8D47 FF       ||LEA EAX,[EDI-1]
29. 00401093  |.  8BD6          ||MOV EDX,ESI
30. 00401095  |>  8B6C24 14     ||MOV EBP,DWORD PTR SS:[ESP+14]
31. 00401099  |.  85F5          ||TEST EBP,ESI
32. 0040109B  |.  75 17         ||JNE SHORT 004010B4
33. 0040109D  |.  8B2C85 783340 ||MOV EBP,DWORD PTR DS:[EAX*4+403378]
34. 004010A4  |.  89A9 7C334000 ||MOV DWORD PTR DS:[ECX+40337C],EBP      ; ASCII "#H"
35. 004010AA  |.  893485 783340 ||MOV DWORD PTR DS:[EAX*4+403378],ESI
36. 004010B1  |.  83C0 01       ||ADD EAX,1
37. 004010B4  |>  8BB1 80334000 ||MOV ESI,DWORD PTR DS:[ECX+403380]
38. 004010BA  |.  8BEE          ||MOV EBP,ESI
39. 004010BC  |.  33EA          ||XOR EBP,EDX
40. 004010BE  |.  85EB          ||TEST EBX,EBP
41. 004010C0  |.  74 04         ||JE SHORT 004010C6
42. 004010C2  |.  8BC7          ||MOV EAX,EDI
43. 004010C4  |.  8BD6          ||MOV EDX,ESI
44. 004010C6  |>  8B6C24 14     ||MOV EBP,DWORD PTR SS:[ESP+14]
45. 004010CA  |.  85F5          ||TEST EBP,ESI
46. 004010CC  |.  75 17         ||JNE SHORT 004010E5
47. 004010CE  |.  8B2C85 783340 ||MOV EBP,DWORD PTR DS:[EAX*4+403378]
48. 004010D5  |.  89A9 80334000 ||MOV DWORD PTR DS:[ECX+403380],EBP
49. 004010DB  |.  893485 783340 ||MOV DWORD PTR DS:[EAX*4+403378],ESI
50. 004010E2  |.  83C0 01       ||ADD EAX,1
51. 004010E5  |>  8BB1 84334000 ||MOV ESI,DWORD PTR DS:[ECX+403384]
52. 004010EB  |.  8BEE          ||MOV EBP,ESI
53. 004010ED  |.  33EA          ||XOR EBP,EDX
54. 004010EF  |.  85EB          ||TEST EBX,EBP
55. 004010F1  |.  74 05         ||JE SHORT 004010F8
56. 004010F3  |.  8D47 01       ||LEA EAX,[EDI+1]
57. 004010F6  |.  8BD6          ||MOV EDX,ESI
58. 004010F8  |>  8B6C24 14     ||MOV EBP,DWORD PTR SS:[ESP+14]
59. 004010FC  |.  85F5          ||TEST EBP,ESI
60. 004010FE  |.  75 17         ||JNE SHORT 00401117
61. 00401100  |.  8B2C85 783340 ||MOV EBP,DWORD PTR DS:[EAX*4+403378]
62. 00401107  |.  89A9 84334000 ||MOV DWORD PTR DS:[ECX+403384],EBP
63. 0040110D  |.  893485 783340 ||MOV DWORD PTR DS:[EAX*4+403378],ESI
64. 00401114  |.  83C0 01       ||ADD EAX,1
65. 00401117  |>  8BB1 88334000 ||MOV ESI,DWORD PTR DS:[ECX+403388]
66. 0040111D  |.  8BEE          ||MOV EBP,ESI
67. 0040111F  |.  33EA          ||XOR EBP,EDX
68. 00401121  |.  85EB          ||TEST EBX,EBP
69. 00401123  |.  74 05         ||JE SHORT 0040112A
70. 00401125  |.  8D47 02       ||LEA EAX,[EDI+2]
71. 00401128  |.  8BD6          ||MOV EDX,ESI
72. 0040112A  |>  857424 14     ||TEST DWORD PTR SS:[ESP+14],ESI
73. 0040112E  |.  75 17         ||JNE SHORT 00401147
74. 00401130  |.  8B2C85 783340 ||MOV EBP,DWORD PTR DS:[EAX*4+403378]
75. 00401137  |.  89A9 88334000 ||MOV DWORD PTR DS:[ECX+403388],EBP
76. 0040113D  |.  893485 783340 ||MOV DWORD PTR DS:[EAX*4+403378],ESI
77. 00401144  |.  83C0 01       ||ADD EAX,1
78. 00401147  |>  83C7 05       ||ADD EDI,5
79. 0040114A  |.  8D77 FE       ||LEA ESI,[EDI-2]
80. 0040114D  |.  83C1 14       ||ADD ECX,14
81. 00401150  |.  81FE 40420F00 ||CMP ESI,0F4240
82. 00401156  |.^ 0F82 F4FEFFFF |\JB 00401050
83. 0040115C  |.  D1EB          |SHR EBX,1
84. 0040115E  |.  81CB 00000080 |OR EBX,80000000
85. 00401164  |.  D16C24 14     |SHR DWORD PTR SS:[ESP+14],1
86. 00401168  |.^ 0F85 D3FEFFFF \JNE 00401041

и несмотря на явную бредовость кода, всё равно немного выигрывает по скорости...
К тому же замена lay=(lay>>1)|(1<<(BITS-1)) на вроде бы лучшую lay|=mask замедляет а не ускоряет программу...
Я тоже весьма потрясён ))

add:
исправил аттач, чтобы были одинаковые и стабильные исходные данные и всё стало на свои места (тестирование 1000 элементов стабильнее тестирования миллиона, поскольку меньше вероятность вмешательства системы)

 

Одинаковые данные для тестов употребляете ? =)

 

Proteus
Громадное спасибо - ты спас мою веру в ассемблер )
Теперь асм как и положено ему в ~1,4 раза обгоняет C++.

 

Ну тогда полечи от тормозов мою асмовую вставку...
Дельфы 6-7 есть? =))) Знаю,знаю, не уважаете вы это дело...
Тормозит почти в два раза, хотя работает корректно.

 

Если честно нету)) Даже билдера никогда не ставил...

 

persicum

Угу дельфы давно не держу, так что сам если что подправишь по мелочи.
Еще не знаю как дельфя адресует локальные переменные - если через ebp, то первый вариант работать не будет, если через esp, то всё будет ок. Второй вариант чуть-чуть помедленнее, но не использует ebp и потому не конфликтует с хи-левелом.
Возможно получится ещё немного ускориться, объявив lay, mask, endArray как глобальные переменные, поскольку прямая адресация быстрее относительной через esp/ebp.

И не забывай что этот вариант развёрнутого цикла требует чтобы размер массива был кратен 4м двордам иначе отсортирует лишний хвост.

ЗЫ: в твоём варианте много времени ест xcgh - она как и loop пригодны для оптимизации по размеру, но не по скорости. Для ускорения почти всегда следует разбивать сложные составные команды на их элементарные составляющие.

 

И для полноты картины - сортировка оформленнная в виде процедуры (fasm)
RadixSort lpArray, nElements, сохраняющей ebp ebx esi edi (а-ля api) и работающей с любым размером массива (хвост не кратный развороту цикла обрабатывается дополнительно).
Поскольку оптимизация по скорости, то временные переменные описаны глобально - к ним доступ немного быстрее чем к стековым

 

Локальные переменные асмовым вставкам как правило не нужны...
Передача параметров идет через регистры (fastcall?).
Внутри самой асмовой процедуры можно завести статические абсолютные переменные, если очень-очень надо и push pop почемуто не тянут.

А частное и остаток от деления на четыре слабо взять?
Поскоку преимуществ асмого кода перед дельфи я не нашел, то оставлю на паскакале так как это в 1000 раз легче для сопровождения и въезжания потом через nnn месяцев =)))

 

см. #37, но это усложняет и замедляет процесс, а потому актуально только когда размер массива заранее неизвестен.