| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL | | Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

	« предыдущая ветвь | форум | следующая ветвь »

Сортировка строк

Страницы:   < 1 2 >

F1 ©   (2002-10-24 11:06:00) 

Есть задачка: Отсортировать строки в файле(по алфавиту)
При этом главное скорость. Ну и желательно памяти поменьше кушать.Файл большой-100тыс строк, каждая 5-20 символов. Вобщем я написал, сортирует достаточно быстро(на PIII-550 DIMM 320Mb 3..4 секунды), но памяти жрет примерно (5..10)*размер файла. И на компах, где мало оперативки винды начинают колбасить файл подкачки и скорость сразу падает в 10-ки раз. Посмотрите, может кто-нибудь знает способ лучше??? (камешки и пузырики здесь просто отдыхают ;-))))

program ConsoleStr;
{$APPTYPE CONSOLE}
uses
SysUtils, Windows;

type
//Структура листа дерева
PSuperNode=^TSuperNode;
TSuperNode = record
c:char;
NodeNext:PSuperNode;
NodeChild:PSuperNode;
end;

var
FS:TextFile;
Mem,FSize,RSize,CountString,NowString:LongWord;
Root:array[char] of PSuperNode;
S:String;
FileNameO,FileNameS:String;
Mess:Array[0..63] of Char;



//-------Добавление слова в дерево----------
procedure AddSuperNode(Node:PSuperNode;Index:Integer);
var
Fl:Boolean;
N:PSuperNode;
begin
if Index>Length(S) then //смотрим, не кончилось ли слово
begin //слово кончилось
if Node^.NodeChild=Nil then //есть ли дочерние узлы
begin //нет
Mem:=Mem+SizeOf(TSuperNode);
New(Node^.NodeChild);
Node:=Node^.NodeChild;
Node^.NodeNext:=Nil;
Node^.NodeChild:=Nil;
Node^.c:=#0;
inc(CountString);
end else
begin //есть
Mem:=Mem+SizeOf(TSuperNode);
New(N);
N^.NodeChild:=Nil;
N^.c:=#0;
N^.NodeNext:=Node^.NodeChild;
Node^.NodeChild:=N;
inc(CountString);
end;
end else
begin // Слово не кончилось
if Node^.NodeChild=Nil then
begin //дочерних нет
Mem:=Mem+SizeOf(TSuperNode);
New(Node^.NodeChild);
Node:=Node^.NodeChild;
Node^.NodeNext:=Nil;
Node^.NodeChild:=Nil;
Node^.c:=S[Index];
AddSuperNode(Node, Index+1);
end else
begin //дочерние есть
if Node^.NodeChild^.c>S[Index] then
begin //Нужно букву вставлять на первое место
Mem:=Mem+SizeOf(TSuperNode);
New(N);
N^.c:=S[Index];
N^.NodeChild:=Nil;
N^.NodeNext:=Node^.NodeChild;
Node^.NodeChild:=N;
AddSuperNode(N, Index+1);
end else
begin
fl:=true;
Node:=Node^.NodeChild;
while fl do //ищем, куда же вставить букву
begin
if Node^.NodeNext=Nil then fl:=False else
if Node^.NodeNext^.c<=S[Index] then Node:=Node^.NodeNext else
fl:=False;
end;
if Node^.c<>S[Index] then
begin
Mem:=Mem+SizeOf(TSuperNode);
New(N);
N^.c:=S[Index];
N^.NodeChild:=Nil;
N^.NodeNext:=Node^.NodeNext;
Node^.NodeNext:=N;
AddSuperNode(N, Index+1);
end else
begin //если такая буква есть, то не нужно дублировать
AddSuperNode(Node, Index+1);
end;
end;
end;
end;
end;
//-------Сохранение дерева----------
//Здесь уже все отсортированно, просто пробегаем рекурсивно, сохраняем и удаляем.
procedure SaveSuperNode(Node:PSuperNode; st:String);
Var
N,N1:PSuperNode;
begin
N1:=Node;
if Node^.c=#0 then
begin
Writeln(FS,st);
end else
if Node^.NodeChild<>Nil then
begin
st:=st+Node^.c;
Node:=Node^.NodeChild;
repeat
N:=Node^.NodeNext;
SaveSuperNode(Node,st);
Node:=N;
until Node=Nil;
end;
Dispose(N1);
end;

procedure Sort;
var
FO:TextFile;
Tick:Cardinal;
i:Char;
Index:Byte;
Node:PSuperNode;
begin
Writeln("Sort start...");
Tick:=GetTickCount;
Mem:=255*Sizeof(TSuperNode);
for i:=#1 to #255 do
begin
new(Root[i]);
Root[i]^.NodeNext:=Nil;
Root[i]^.NodeChild:=Nil;
Root[i]^.c:=i;
end;
CountString:=0;
NowString:=0;
AssignFile(FO,FileNameO);
Reset(FO);
while not eof(FO) do
begin
repeat
Readln(FO,S);
until Length(S)>0;
AddSuperNode(Root[S[1]],2);
end;
CloseFile(FO);
Writeln("Sort complete...");
Writeln("Save start...");
AssignFile(FS,FileNameS);
Rewrite(FS);
for i:=#1 to #255 do
begin
SaveSuperNode(Root[i],"");
end;
CloseFile(FS);
Tick:=GetTickCount-Tick;
Writeln("Save complete...");
Writeln("Time: "+IntToStr(Tick div 1000)+","+IntToStr(Tick mod 1000)+" seconds");
Writeln("Count word: "+IntToStr(CountString));
Writeln("Count memory: "+IntToStr(Mem));
end;

begin
if ParamCount<>2 then
begin
Mess:="Надо 2 параметра";
AnsiToOem(Mess,Mess);
Writeln(Mess);
Readln;
Halt;
end;
FileNameO:=ParamStr(1);
FileNameS:=ParamStr(2);
Sort;
Readln;
end.

Единственное, что пришло в голову - это создавать дерево в отдельной куче, а потом делать Dispose не каждого узла, а всей кучи хором. Это немного увеличит скорость, но не поможет с подгрузкой файля подкачки.

---

ЮЮ   (2002-10-24 12:44:00) [21]

>И на компах, где мало оперативки винды начинают колбасить файл подкачки и скорость сразу падает в 10-ки раз.

Отсортируй раз и храни отсортированным

---

F1   (2002-10-24 12:30:00) [22]

Ну что, ни у кого нет вариантов. Никому не приходилось сортировать строки??? Подкидывайте любые идеи, даже если не уверены, что правильные.

---

Страницы:   < 1 2 >

Наверх