Алгоритм решения задания № 2 (сортировка большого файла) для отбора в летнюю школу стажировку от Яндекса

Один из алгоритмов для решения задания № 2 для отбора в летнюю школу стажировку от Яндекса. Условия задания можно просмотреть здесь.

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

Подробно алгоритм описан в книге «Кормен, Лейзерсон, Ривест – Алгоритмы, построение, анализ» на странице 171.

Поскольку наибольшее число, которое может быть записано в файл в десятичной системе исчисления равно 4294967296 (10 разрядов). Далее буду предполагать, что если число имеет меньшее количество разрядов, то недостающие разряды заполнены нулями. Т.е. число 123456 будет записано в виде 0000123456.

При описании алгоритма будем пользоваться такой структурой данных

Вход: Файл с 32 – битными числами не отсортированные

Выход: Файл “Result.txt”, в котором числа отсортированы по возрастанию

Данные:

Константы

MaxDigits = 10 – максимальное количество разрядов в считываемых числах

MaxReadThreads = 10- максимальное количество читаюзщих потоков

MaxWriteThreads = 10 – максимальное количество записывающих потоков

MaxSortThreads = 10 – максимальное количество сортирующих потоков

MaxReadDigitsInArray = 1024 –

Переменная MemoryCout – количество блоков памянти, которые возможно выделить

Будем обозначать I – ый разряд числа X – > X[i]

Будем обозначать “i.txt” файл, в котором имя соответствует счетчику цикла i

Будем обозначать “i_j.txt” файл, в шимени котрого i и j заменены на соответствующие счетчики циклов

Структуры данных и описание типов потоков

————————————————————-

Memory

K – разряд по которому будет происходить сортировка

I – номер потока который считал данную область памяти.

A – массив считанных чисел

N – количество элементов в массиве

isFree – признак того что память не занята ни одним из потоков

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

————————————————————-

R – поток – читает данные из файла

N – номер потока, соответствует имени файла из которого он будет читать данные

Read(AMemory) – функция чтения памяти AMemory потоком

StartRead – функция запускающая чтение файла потоком

isFinished – признак того, что поток завершил все свои действия

————————————————————-

S – поток поток в котором будет производиться сортировка по соответствующему разряду

Sort(AMemory) – функция сортировки массива А блока памяти AMemory, по значению разряда записанного в AMemory

isFinished – признак того, что поток завершил все свои действия

————————————————————-

W – записывающий поток

Write(AMemory) – записывает

isFinished – признак того, что поток завершил все свои действия

————————————————————-

R[i] массив – список читающих потоков

S[i] массив – список сортирующих потоков

W[i] массив записывающих потоков

I = 0, .., 9.

————————————————————-

M[j] массив объектов типа Memory длина массива зависит от того какова может быть максимальная длина массива А и каким объемом оперативной памяти мы располагаем.

Алгоритм

  1. PrepareFiles
  2. For k = 2 to MaxDigits do
  3. begin
  4.   for j = 0 to MemoryCout -1 do
  5.     M[j].k:= k – записываем в область памяти номер разряда по которому будет производиться сортировка
  6.   for i = 0 to MaxReadThreads – 1 do
  7.   begin
  8.     R[i].StartRead
  9.   end;
  10.   Ждать пока все потоки R[i], W[i], S[i] не завершат сове выполнение
  11.   BuildFiles;
  12. End
  13. BuildResultFile

Описание процедур

Процедура R.StartRead

  1. isFinished:= false;
  2. Открыть на чтение файл i.txt
  3. while не конец файла do
  4. begin
  5.   Выбрать свободную память из M[j] указатель записать в AMemory, если нет свободной памяти ждать пока освободиться
  6. AMemory.isFree:= False;
  7.   Read(AMemory)
  8.   AMemory.i:= N
  9.   Выбрать свободный поток из S[i] указатель записать в S, если нет свободного сортирующего потока, то ожидать его после выбора можно перейти выбору свободной памяти и чтению в нее .
  10.   AMemory1:= AMemory
  11.   S.Sort(AMemory1), ждать завершения не обязательно
  12.   Выбрать свободный записывающий поток из W[i], указатель записать в W, если нет свободного записывающего потока то ожидаем его.
  13.   AMemory2:= AMemory1
  14.   W.Write(AMemory2), ждать завершения не обязательно
  15.   AMemory2.isFree:= True;
  16. end;
  17. isFinished:= True;

Процедура R.Read(AMemory)

  1. читать в массив AMemoryю.А числа из памяти, но не более MaxReadDigitsInArray
  2. в N записать количество прочитанных чисел

Процедура S.Sort(AMemory)

  1. isFinished:= False
  2. сортировать по возрастанию массив AMemory.A по разряду AMemory.K (Например, методом «Куча» можем его использовать, поскольку все данные есть в массиве А)
  3. isFinished:= True

Процедура W.Write(AMemory)

  1. isFinished:= False
  2. for I = 0 to AMemory.n- 1 do
  3.   Записать в файл AMemory.i_ AMemory.k.txt число AMemory.A[i]
  4. isFinished:= True

Процедура BuildFiles

  1. For I = 0 to MaxDigits -1 do
  2. begin
  3.   удалить файл “i.txt”
  4.   For j = 0 to MaxDigits – 1 do
  5.   begin
  6.     Записать в файл “i.txt” числа из “j _i.txt”
  7.     Удалить файл “j _i.txt”
  8.   end;
  9. end;

Процедура PrepareFiles

  1. While исходный файл не закончился do
  2. begin
  3.   прочитать в X число из файла
  4.   Записать его значение в файл “X[0].txt”
  5. end;

Процедура BuildResultFile

  1. For I = 0 to MaxDigits -1 do
  2. begin
  3.   Записать в результирующий файл “Result.txt” числа из файлf “i.txt “
  4.   Удалить файл “i.txt”
  5. end;

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

Share

Tags: , ,

Leave a Reply