/*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. - адміністрації сайту. Помістіть будь ласка мою попередню тему про генератор випадкових чисел з "корзини" принаймні в розділ "інше" (помістив випадково(ось що буває, коли цілу ніч працюєш над чимось:)).