Форум: "Основная";
Текущий архив: 2005.01.02;
Скачать: [xml.tar.bz2];

Вниз

Сортировка строк и удаление дубликатов   Найти похожие ветки 

← →
Хакер ©   (2004-12-18 13:03) [0]

Задача: В файле А отсортировать строки по алфавиту и удалить дубликаты и записать в файл Б.
Сейчас реализовано:

procedure Run_Progam_Sort;
Var
 FStroka:TStringList;
Begin
Windows.DeleteFile(Pchar(Form1.Edit2.Text));

FStroka:=TStringList.Create;

 FStroka.CaseSensitive:=True;
 FStroka.Duplicates:=dupIgnore;
 FStroka.Sorted:=True;

     FStroka.LoadFromFile(Form1.Edit1.Text);
     FStroka.SaveToFile(Form1.Edit2.Text);

FStroka.Free;

End;

но есть проблема - выделенная строка работает очень медленно, необходимо реализовать более производительно.

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

Также очень жалательна экономия памяти (допустимо использовать памяти до двойного размера файла, но быстродействие важнее)

---

← →
TUser ©   (2004-12-18 13:46) [1]

> но есть проблема - выделенная строка работает очень медленно,
> необходимо реализовать более производительно.

Значит, файл большой. А каждая строка там при загрузке ищется бинарным поиском. Время log(n), т.е. для загрузки файла из N строк надо Sun(i=1..N,log(i)) времени. MathCad говорит, что это логарифм от (N+1)!. При этом каждое сравнение строк - это линейное время. Т.е. считай, что время Sum(i = 1..N, L*log(N)), где L - средняя длина строки, или примерно O(L*log(N+1!))

Более быстрые способы - руками реализовать нагруженное дерево, в котором хранить все строки. Время поиска каждой строки - линейно зависит от ее размера, а поиск и сравнение есть одна и та же операция. Иными словами, всего O(L*N).
Поэтому делай так - грузи файл в TStringList с дублями (это будет весьма быстро), потом строй свое дерево из этих строк, обходом дерева загоняй их в стринг лист и сохраняй.

---

← →
TUser ©   (2004-12-18 13:59) [2]

Кстати, еще чуть не забыл. При добавлении строки в отсортированный список часто вызывается System.Move, - а это тоже тормоза и не хилые. Деревья спасут.

---

← →
Хакер ©   (2004-12-18 14:36) [3]

Вообще-то у меня идея главная в том, чтобы удалить из файла дубликаты, но я, в результате анализа большинства алгоритмов пришёл к выводу, что сортировка необходима.

TUser © [1] спасибо, как-нибудь попрбую, но с деревьями никогда не работал и не совсем понимаю, насколько они дадут выигрыш в скорости ..

когда-то давно я эту задачу ([0]) решал с помощью array of string , сперва сортировал быстрой сортировкой, а потом перегонял во второй массив, сравнивая с последним элементом -> для удаления дубликатов.
работало _достаточно_ быстро ... но "ело" примерно 3*FileSize памяти (((

Сейчас пробую задачу решить "на новом уровне" - сделал красиво (0) но как оказалось, очень медленно (

чтобы не быть "голословным", приведу цифры:
файл содержит строки длиной 5 цифр
всего 100000 строк, файл размером 700000 байт
загрузка его в память методом readln() do eof - 100 ms LoadFromFile 140 ms  в среднем ...
бытрая сортировка в массиве 467 мс - в файле примерно половина дубликатов, все цифры случайные, несортированные
просмотр и очистка - от дубликатов в другой массив - тоже примерно 100 мс всего около 700 мс

а по методу [0] - 22000 мс !! - так медленно :((((((

---

← →
TUser ©   (2004-12-18 14:49) [4]

В принцыпе, идеальных алгоритмов не бывает. Для хранения информации связные структуры удобны для операций вставки, а массивы - для поиска. Тебе же нужно и то и другое. В принцыпе все (ну, почти все) алгоритмы которые обеспечивают и то, и другое, так или иначе основаны на деревьях (в т.ч. хеш-таблицы - это тоже, по сути дерево). Эти алгоритмы сложнее для понимания и реализации, но с ними просто надо разобраться.
На мой взгляд, лучше всего это описано в кн. Ахо, Хопкрофт, Ульман. "Структуры данных и алгоритмы". Также неплохо у Кнута и Вирта.
Я приведу простой пример работы с нагруженными деревьями, который сам когда-то писал. В частности, здесь реализовано хранение большого количества строк (примерно по 10 символов, всего строк - неск. млн., загрузка занимала примерно секунд 30-40 на довольно слабых машинах) и поиск нужной строки. Если разберешь код, от это поможет.

---

← →
TUser ©   (2004-12-18 14:50) [5]

unit uTree;

interface
uses Classes;

var MaxLength:integer = 10;

type
TTree = class
 private
  FParent:TTree;
  FChildren:array [1..4] of TTree;
  FCount:integer;
  FLetter:char;

  function rSequence:string;
 public
  constructor Create(Parent:TTree; Letter:char);
  destructor Destroy; override;

  function GetChild(Letter:char):TTree;

  property Parent:TTree read FParent;
  property Sequence:string read rSequence;
  property Count:integer read FCount write FCount;
  property Letter:char read FLetter;
 end;

var Ecoli:TTree;

const Lets:array [1..4] of char =
          ("A","C","G","T");

function NewTree:TTree;

procedure AddSequence(Root:TTree; Seq:string);
function GetCount(Root:TTree; Seq:string):integer;
procedure ListShorts(Root:TTree; List:TStrings);

implementation
uses SysUtils, Forms;

function GetLetterCode(C:char):byte;
begin
  C:=UpCase(C);
  case C of
     "A": result:=1;
     "C": result:=2;
     "G": result:=3;
     "T": result:=4;
     else result:=0;
     end;
end;

function TTree.rSequence:string;
begin
  if FParent <> nil then
     result:=FParent.Sequence+FLetter
     else
     result:=""
end;

constructor TTree.Create(Parent:TTree; Letter:char);
var i:integer;
begin
  FParent:=Parent;
  FLetter:=UpCase(Letter);
  FCount:=0;
  for i:=1 to 4 do
     FChildren[i]:=nil;
end;

destructor TTree.Destroy;
var i:integer;
begin
  for i:=1 to 4 do
     if FChildren[i] <> nil then
        FChildren[i].Free;
  inherited;
end;

function TTree.GetChild(Letter:char):TTree;
var i:byte;
begin
  i:=GetLetterCode(Letter);
  if i = 0 then
     result:=nil
     else
     result:=FChildren[i];
end;

function NewTree:TTree;
begin
  result:=TTree.Create(nil," ");
end;

procedure AddSequence(Root:TTree; Seq:string);
var C:TTree;
   i:byte;
begin
  if Seq <> "" then begin
     i:=GetLetterCode(Seq[1]);
     if i = 0 then
        raise Exception.Create("Wrong letter "+Seq[1]);
     C:=Root.GetChild(Seq[1]);
     if C = nil then begin
        C:=TTree.Create(Root,Seq[1]);
        Root.FChildren[i]:=C;
        end;
     C.Count:=C.Count + 1;
     AddSequence(C,copy(Seq,2,length(Seq)-1));
     end else
     Root.Count:=Root.Count+1;
end;

function GetCount(Root:TTree; Seq:string):integer;
begin
  if Root = nil then
     result:=0
     else
  if Seq <> "" then
     result:=GetCount(Root.GetChild(Seq[1]),copy(Seq,2,length(Seq)-1))
     else
     result:=Root.Count;
end;

procedure ListShorts(Root:TTree; List:TStrings);
var i,j:integer;
   LenLists:array {[0..MaxLength-1]} of TStringList;

procedure Go(Root:TTree; Level:integer);
var i:integer;
    C:TTree;
    S:string;
begin
   if Level < MaxLength then
      for i:=1 to 4 do begin
         C:=Root.GetChild(Lets[i]);
         if C <> nil then
            Go(C,Level+1)
            else
            LenLists[length(Root.Sequence)].Add("["+inttostr(length(Root.Sequence)+1)+"]"#9+Root.Sequence+Lets[i]);
         end;
   if Random(100) <= 1 then
      Application.ProcessMessages;
end;

begin
  List.Clear;
  SetLength(LenLists,MaxLength);

  for i:=0 to MaxLength-1 do
     LenLists[i]:=TStringList.Create;

  try
   Go(Root,0);
   for i:=0 to MaxLength-1 do
      if LenLists[i].Count > 0 then
         List.Add(LenLists[i].Text);
  finally
   for i:=0 to MaxLength-1 do
      LenLists[i].Free;
   SetLength(LenLists,0);
  end;
end;

end.

---

← →
TUser ©   (2004-12-18 14:51) [6]

В принцИпе - 2 раза лохонулся :))

---

← →
Verg ©   (2004-12-18 14:53) [7]

Если ты о скорости добавления и поиска, то забудь про array of ...

Бинарное дерево - это рекурсивная струкутра, у которой каждый элемент прдеставлен
1. ключ (в твоем случае строка)
2. Сылка (указатель) на  элемент, который по ключу больше
3. Сылка (указатель) на  элемент, который по ключу меньше
4. Прочие данные.

При включении в такое дерево не требуется значительных перемещений данных (move), а количество сравнений в случае сбалансированного дерева стремится к логарифм(по основанию 2) от числа элементов дерева. Т.е., например, при 1 млн. записей, чтобы найти нужную, необходимо ~20 сравнений ключей (всего).

---

← →
TUser ©   (2004-12-18 14:58) [8]

Чтобы не запутать, надо сразу сказать, что бинарные и нагруженные деревья - это разные веши. В [4] и [5] речь идет про нагруженные, в [7] - про бинарные.

С бинарными будет как раз проблема в обеспечении их сбалансированности. Т.е. log(N), конечно, лучше, чем N, но для этого надо переодически производит перестройку дерева, что довольно медленно.

---

← →
Verg ©   (2004-12-18 15:08) [9]

> TUser ©   (18.12.04 14:58) [8]


Если считать, что поступающие (из файла) в дерево ключи носят случайный (с точки зрения "больше-меньше") характер, то дерево будет достаточно сбалансированным, к.т. я не зря оставил фразу "стремиться к логарифм..."

Ты же говоришь (может я и не правильно понял) о слиноветвящихся B-деревьях.
Эту "тему" я сильно подзабыл....

---

← →
Хакер ©   (2004-12-18 23:52) [10]

пока сделал на масивах, как будет время, постараюсь с деревьями разобраться ;))
TUser ©   (18.12.04 14:58) [8]
Verg ©   (18.12.04 15:08) [9]
спасибо за советы))

---

← →
Хакер ©   (2004-12-18 23:53) [11]

TUser ©   (18.12.04 14:58) [8]

> Чтобы не запутать, надо сразу сказать, что бинарные и
> нагруженные деревья - это разные веши

про деревья я уже запутался ;))
- ну и ладно ..  пока они не очень нужны ;)

---

Страницы: 1 вся ветка

Форум: "Основная";
Текущий архив: 2005.01.02;
Скачать: [xml.tar.bz2];

Наверх

Память: 0.5 MB
Время: 0.056 c