ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Roman Ilyin                          2:5020/400     23 Jan 2002  02:29:11
 To : Andrey Maximenko
 Subject : Re: Сортировка файла, не помещающегося в   п  амять
 -------------------------------------------------------------------------------- 
 

 Доброе время суток, Andrey!
 Вы писали --> Victor Sotnikov 22 января 2002 [11:00:30]:
 
  >> Спасибо, хороший способ. Hо - только когда диапазон чисел (пусть и
  >> целых) достаточно мал, чтобы организовать такой массив в памяти.
  >> А что будем делать, когда массив был бы слишком велик?
 
 AM>Главный вопрос: отсортировать данные (получить конкретный результат)
 AM>или построить наилучший алгоритм?
 
 AM>Если всего лишь навсего отсортировать, то берешь любую локальную базу
 AM>данных (Fox, Clipper, Delphi, Access или др)
 AM>и строишь индекс.
 AM>У меня 300 тыс чисел сортирует за 10 сек (Clipper 5.3, PIII-800)
 
 300тыс - это мелочи, и сортровать такой массив через базу данных
 имхо извращение, ибо долго. У человека же "массив не умещается
 в памяти", т.е. гораздо больше. (300 000 * 8 байт = 24мб)
 
 Для примера - сортирует 100 тыс longint (400 кбайт) за 0.08сек на IP166mmx.
 Про P-2, P-3 и прочие - молчу. ;)
 =========Hачало цитаты==============
 {tmt-Pascal source}
 Var tt  : Array[0..99999] of Longint;
     i,n : Longint;
 
 Procedure QuickSort(Var arr; lo,hi : Longint); Assembler;
 Asm
    Push   EBX
    Push   ECX
    Push   EDX
 
    Xor    EAX,EAX
    Push   EAX
    Push   EAX
    Mov    ESI,[arr]
    Mov    EBX,[lo]
    Mov    EDX,[hi]
    Shl    EBX,2
    Shl    EDX,2
    Push   EBX
    Push   EDX
 @@SortLoop:
    Pop    EDX    { HI }
    Pop    ECX    { LO }
    Test   EDX,EDX
    JZ     @@The_END
    Mov    EBX,EDX
    Add    EBX,ECX
    Shr    EBX,3
    Push   ECX
    ShL    EBX,2
    Push   EDX
    Mov    EAX,[ESI+EBX] { MID }
 
 @@Step_Loop:
 
 @@LO_Loop:
    Mov    EBX,[ESI+ECX] { LO }
    Cmp    EBX,EAX
    JGE    @@LO_Exit
    Add    ECX,4
    Jmp    @@LO_Loop
 @@LO_Exit:
 
 @@HI_Loop:
    Mov    EBX,[ESI+EDX] { HI }
    Cmp    EAX,EBX
    JGE    @@HI_Exit
    Sub    EDX,4
    Jmp    @@HI_Loop
 @@HI_Exit:
 
    Cmp    ECX,EDX
    JG     @@NoSwap
      Mov    EDI,[ESI+ECX]
      Mov    EBX,[ESI+EDX]
      Mov    [ESI+EDX],EDI
      Mov    [ESI+ECX],EBX
      Sub    EDX,4
      Add    ECX,4
      Cmp    ECX,EDX
      JG     @@NoSwap
      Jmp    @@Step_Loop
 @@NoSwap:
 
    Pop    EAX { HI }
    Pop    EDI { LO }
 
    Cmp    EDI,EDX
    JGE    @@Nope1
    Push   EDI
    Push   EDX
 @@Nope1:
 
    Cmp    ECX,EAX
    JGE    @@SortLoop
    Push   ECX
    Push   EAX
 
    Jmp    @@SortLoop
 @@The_END:
 
    Pop   EDX
    Pop   ECX
    Pop   EBX
 end;
 
 Begin
    Randomize;
    For i:= 0 to 99999 do tt[i]:= Random(100000);
    Write('Sorting 100000 longints... ');
    QuickSort(tt,0,99999);
    Writeln('done.');
    n:= 0;
    For i:= 1 to 99999 do If tt[i]<tt[i-1] then Inc(n);
    Writeln('Errors: ',n);
 end.
 =========Конец цитаты================
 зы: Исходник не мой...
 
 -==================================================-
 Удачи!
 Roman Ilyin.  [grisper@voronezh.net]
 
 --- ifmail v.2.15dev5
  * Origin: Информсвязь-Черноземье (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Сортировка файла, не помещающегося в память   Victor Sotnikov   19 Jan 2002 02:32:18   Re: Сортировка файла, не помещающегося в память   Roman Ilyin   19 Jan 2002 17:23:59   Re: Сортировка файла, не помещающегося в память   Victor Sotnikov   21 Jan 2002 20:40:08   Сортировка файла, не помещающегося в память   Roman Ilyin   22 Jan 2002 00:26:36   Сортировка файла, не помещающегося в память   Victor Sotnikov   22 Jan 2002 04:28:51   Сортировка файла, не помещающегося в память   Roman Ilyin   22 Jan 2002 10:13:52   Сортировка файла, не помещающегося в память   Victor Sotnikov   25 Jan 2002 01:27:16   Сортировка файла, не помещающегося в память   Roman Ilyin   25 Jan 2002 11:22:39   Сортировка файла, не помещающегося в память   Victor Sotnikov   27 Jan 2002 16:05:27   Сортировка файла, не помещающегося в память   Stanislav Shwartsman   22 Jan 2002 08:18:48   Сортировка файла, не помещающегося в память   Alexander Bushmakin   23 Jan 2002 02:59:22   Re: Сортировка файла, не помещающегося в память   Andrey Maximenko   22 Jan 2002 15:00:30   Re: Сортировка файла, не помещающегося в п амять   Roman Ilyin   23 Jan 2002 02:29:11   Re: Сортировка файла, не помещающегося в память   Victor Sotnikov   25 Jan 2002 01:14:56   Re: Сортировка файла, не помещающегося в память   Andrey Belyakov   21 Jan 2002 21:27:39   Re: Сортировка файла, не помещающегося в память   Nick Kovaliov   22 Jan 2002 00:45:05   Сортировка файла, не помещающегося в память   Roman Ilyin   22 Jan 2002 10:13:53   Re: Сортировка файла, не помещающегося в память   Nick Kovaliov   22 Jan 2002 12:54:42   Сортировка файла, не помещающегося в память   Ilia Kantor   22 Jan 2002 21:24:18   Re: Сортировка файла, не помещающегося в память   Victor Sotnikov   22 Jan 2002 04:26:48