Usuwanie duplikatów linii z TStringList bez sortowania w Delphi

Question

Wiem, jak usunąć duplikaty łańcuchów z TStringList przy użyciu dupignore dla posortowanej listy ciągów.

CallData := TStringList.Create; 
CallData.Sorted := True; 
Call.Duplicates := dupIgnore; 

ale w moim przypadku ciągów nie musi być sortowane.

Używanie duplikatów wyszukiwania pętli FOR jest bardzo powolne (również przy użyciu indexOF()), gdy TStringList ma setki tysięcy wierszy.

if OpenDialog1.Execute then 
    begin 
    Try 
     y := TStringList.create; 
     f := TStreamReader.create(OpenDialog1.FileName, TEncoding.UTF8, True); 
     while not f.EndOfStream do 
     begin 
     l := f.ReadLine; 
     X.Add(l); 
     end; 

     g := Tstreamwriter.create('d:\logX.txt', True, TEncoding.UTF8); 
     for I := 0 to X.count - 1 do 
     begin 


      if y.IndexOf(X[I]) = -1 then 

      y.Add(X[I]); 

     end; 

     for j := 0 to y.count - 1 do 
     g.WriteLine(y[j]); 

    Finally 
     f.free; 
     y.free; 
     g.free; 
    End; 
    end; 

Czy istnieje lepszy sposób?

Answer 1

Oto jak chciałbym podejść do tego problemu:

1. utworzyć słownik wprowadzonego na sznurku. Nie ma znaczenia, że ​​jest to typ wartości.
2. Powtórz listę ciągów w odwrotnej kolejności.
3. Dla każdego ciągu sprawdź, czy jest on w słowniku.
4. Jeśli znajduje się w słowniku, usuń z listy ciągów. W przeciwnym razie dodaj do słownika.

Jeśli istnieje duża liczba duplikatów, które należy usunąć, to na wydajność powyższego wpłynie wielokrotne usunięcie z listy ciągów. To dlatego, że każdy element do usunięcia powoduje przesunięcie kolejnych elementów o jeden indeks. Możesz tego uniknąć, kopiując do nowej listy zamiast usuwać w miejscu.

Alternatywnie, można pracować w miejscu tak:

1. Tworzenie słownika wprowadzonego na sznurku. Nie ma znaczenia, że ​​jest to typ wartości.
2. Inicjowanie zmiennej o nazwie Count na zero.
3. Powtórz listę ciągów w kolejności do przodu.
4. Dla każdego ciągu sprawdź, czy jest on w słowniku.
5. Jeśli znajduje się w słowniku, nie rób nic. W przeciwnym razie dodaj do słownika, skopiuj do indeksu Count z listy, a następnie zwiększ Count.
6. Po zakończeniu iteracji zmień rozmiar listy, aby zawierały elementy Count.

Punktem słownika jest to, że odnośnik jest operacją O (1), a więc drugi algorytm ma złożoność O (n).

Answer 2

Użyłbym oszustwa, mając listę posortowaną i nieposortowaną. Tak:

y := TStringList.create; 
    s := TStringList.create; 
    s.Sorted := TRUE; 
    s.Duplicates := dupIgnore; 

    f := TStreamReader.create(OpenDialog1.FileName, TEncoding.UTF8, True); 
    while not f.EndOfStream do 
    begin 
    l := f.ReadLine; 
    s.Add(l); 
    if s.Count > y.Count then y.Add(l); 
    end; 

    // etc. 

Answer 3

function compareobjects 
      (list  : Tstringlist; 
      index1 : integer; 
      index2 : integer 
     )   : integer; 
begin 
    if index1 = index2 then 
    result := 0 
    else 
    if integer(list.objects[index1]) < integer(list.objects[index2]) then 
     result := -1 
    else 
     result := 1; 
end; 

begin 
    Try 
    y := TStringList.create; 
    y.Sorted := true; 
    y.Duplicates := dupignore; 
    f := TStreamReader.create('c:\106x\q47780823.bat'); 
    i := 0; 
    while not f.EndOfStream do 
    begin 
     inc(i); 
     line := f.readline; 
     y.Addobject(line,tobject(i)); 
    end; 
    y.Sorted := false; 
    y.CustomSort(compareobjects); 

    for i := 0 to y.count - 1 do 
     WriteLn(y[i]); 

    Finally 
     f.free; 
     y.free; 
    End; 
    readln; 
end. 

będę śledzić liczbę linii (i) i przypisać go z łańcucha przez odlewanie jako przedmiot; posortuj listę i usuń duplikaty, tak jak poprzednio, ale następnie odznacz je, używając niestandardowego sortowania obiektów.