1

Тема: vsaud - векторне сортування масиву невпорядкованих даних.

/*vsaud - vector sorting of array unordered data*/
Векторне сортування масиву невпорядкованих даних.

Нехай задано 5-ти гігібайтний масив невпорядкованих данних, який необхідно відсортувати.
Проаналізуємо поставлену задачу...

Основною одиницею вимірювання інформації є байт (з восьми бітів (нулів та одиниць)), який може містити 256-ть значень (від 0 (0x00) до 255 (0xFF - в шістнадцятковій системі числення)). Існує велика ймовірністі того, що у файлі подібного розміру ці значення зустрічатимуться неодноразово (при сталості своїх значень, і змінності своїх положень). Таким чином, впорядкувавши (приміром в порядку зростання) будь-яким з відомих алгоритмів сортування подібний масив невпорядкованих даних, ми отримаємо вихідний файл із значень від 0 до 255 з періодом повторення кожного з них відповідно до їх кількості у вхідному файлі.

Проаналізувавши відповідним чином подібну задачу, ми можемо прийти до висновку про те, що найбільш ефективним методом впорядкування такого масиву, буде створення векторної таблиці із полями (достатнього розміру, щоб описати максимальну кількость елементів масиву) та присвоєння кожному із значень масиву вектора і занесення у відповідне йому поле кількості віднайдених елементів. Оскільки ми сортуємо байтний масив даних, нам знадобиться лише 256 векторів із розміром поля векторної таблиці у вісім байтів (оскільки, адрес поля ми вираховуватимемо простим зсувом в ліво значення його вектора), щоб мати можливість описати максимальну кількість елементів масиву більшу за 4GiB (>2^32). Тож розміром таблиці, буде: 256V * 8B = 2048B (2-ва кілобайти).

Асамблерний джерельний код циклу, алгоритму векторного сортування для даної задачі складається лише з п'яти рядків і на процесорі i486 виконується за 14 тактів, та виглядає наступним чином:

.2:movzx ax, [si]; //отримуємо значення (елемента масиву) вектора
   inc   si; //просуваємо si на наступне значення елемента масиву
   shl   ax, 3; //обчислюємо адрес поля таблиці на яке вказує вектор
es inc   word [eax]; //збільшуємо значення поля таблиці на одиницю
   loop  .2; //переходимо до наступного значення вектора

Даний цикл повинен повторюватися відповідно до кількості елементів масиву і на момент завершення останнього з них, у полях таблиці ми отримаємо кількість усіх значень елементів масиву відповідно до їх векторів. Таким чином, масив невпорядкованих даних буде відсортовано лише за один прохід, що не можливо досягнути при використанні інших алгоритмів сортування невпорядкованих даних.

Як випливає з вище наведеного коду, при використанні si як індекса джерела, ми не можемо адресувати пам'ть вище 64KiB (4GiB при використанні esi). Та оскільки, ми маємо можливість впорядкувати масив за один прохід, фактично не порівнюючи елементи масиву один з одним, то ми можемо розбити файл масиву на зручні для нас фрагменти у 4GiB/64KiB чи навіть розміром в один блок данних 4/2/1KiB або 512B (відповідно до використовуваної файлової системи).

Джерельний код для роботи із 512-ти байтним блоком даних виглядатиме наступним чином:

.1:call  load_next_block; //завантажуємо наступний блок даних
   push  cx; //зберігаємо кількість завантажуваних блоків
      mov   cx, 512; //кількість байтів в блоці даних для проходу
      xor   si, si; //встановлюємо si на початок блоку даних
   .2:movzx ax, [si]; //отримуємо значення (елемента масиву) вектора
      inc   si; //просуваємо si на наступне значення елемента масиву
      shl   ax, 3; //обчислюємо адрес поля таблиці на яке вказує вектор
   es inc   word [eax]; //збільшуємо значення поля таблиці на одиницю
      loop  .2; //переходимо до наступного значення вектора
   pop   cx; //відновлюємо кількість блоків для завантаження
   loop  .1; //зменшуємо її на одиницю та завантажуєм наступний блок даних

Зрозуміло що таким чином ми зможемо опрацювати 64Ki блоків, або 32MiB даних файлу. Тому такий цикл ми будемо вимушені вкласти в інший для опрацювання наступного фрагменту файла і можливо змінити si на esi, якщо захочемо модифікувати його для роботи з більшим об'ємом даних в циклі на один прохід по фрагменту. Та це вже залежить від конкретної програми сортування з роботою по даному алгоритмі і виходить за межі теми. Тому я на цьому завершую і сподіваюсь, що викладене вище є достатньо чітким і зрозумілим для пояснення роботи алгоритму векторного сортування масиву невпорядкованних даних.

p.s. - адміністрації сайту. Помістіть будь ласка мою попередню тему про генератор випадкових чисел з "корзини" принаймні в розділ "інше" (помістив випадково(ось що буває, коли цілу ніч працюєш над чимось:)).

Подякували: 0xDADA11C71

2

Re: vsaud - векторне сортування масиву невпорядкованих даних.

1. Цей алгоритм зветься "сортуванням підрахунком".
2. Власне сортування ви не виконали - тільки зібрали дані для виконання сортування.
3. Ви використовуєте чомусь половинки регістрів, замість того, щоб використовувати їх всі (окрім eax). Звісно, ніц страшного, але дивно.
4. У вас купа незадіяних регістрів, а ви зберігаєте дані в стек.

Подякували: 0xDADA11C71

3 Востаннє редагувалося 0xDADA11C7 (04.10.2014 10:39:26)

Re: vsaud - векторне сортування масиву невпорядкованих даних.

3. Ви використовуєте чомусь половинки регістрів, замість того, щоб використовувати їх всі (окрім eax). Звісно, ніц страшного, але дивно.

Це 16 бітний код для Real Mode (простіше - для MS DOS). Раджу почитати про програмування в 32 розрядній системі - вінді, наприклад. З 16 бітного режиму можна достучатися до EAX, але це неефективно (опкоди мають довгі префікси), хоч іноді й потрібно. Те саме можна сказати і про доступ до нижньої частини регістрів з 32-бітного Protected Mode.
Для довідки
В 286+ процесорі існує гібридний режим - 16 бітний Protected Mode, втім використовувався він й тоді вкрай рідко. Ще існує недокументований (але працює на всіх менстріймових процесорах)  Unreal Mode 16 бітний для коду і 32 бітний для даних, який може адресувати всю пам’ять без танка з бубном, як у Real Mode. Єдине його обмеження це те, що код має розміщуватися у першому мегабайті пам’яті.

4 Востаннє редагувалося 0xDADA11C7 (04.10.2014 13:26:21)

Re: vsaud - векторне сортування масиву невпорядкованих даних.

Стосовно оптимізаці кода. По-перше koala правильно сказав про недоцільність зберігання даних в стеці, коли ми маємо незадіяні регістри. По-друге визначтеся в якому середовищі виконуватиметься ваша програма. Якщо це і486 Real Mode, то і оптимізувати треба для нього.
Оце

 .2:movzx ax, [si]; //отримуємо значення (елемента масиву) вектора
inc si; //просуваємо si на наступне значення елемента масиву

замініть на LODSW, попередньо скинув прапорець напрямку перед циклом командою cld.

Подякували: koala1