Удаление строковых дубликатов - Быстро

[Jiro]

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

То есть мне будет быстрее написать клиент который туда данные закинет и скачает результат, чем реализовывать процесс на локальном пк

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

[MBo]

Конечно, можно - использовать TDictionary

Если версия Delphi совсем старая - TStringList сортированный

[^D^ima]

Попробуй заменить TStringList на THashedStringList (uses inifiles) и посмотри на результат по скорости.

Цитата Jiro @ 13.12.18, 10:22

перепробовал несколько разных подходов

Какие варианты?

[Jiro]

Цитата MBo @ 13.12.18, 11:15

Конечно, можно - использовать TDictionary
Если версия Delphi совсем старая - TStringList сортированный

Версия Delphi Tokyo, попробую TDictionary.

Цитата ^D^ima @ 13.12.18, 12:22

Какие варианты?

Все что в интернетах нашёл. Описывать их все долго, в основном они все про TStringList

А TStringList - медленный, есть вариант того-же TStringList от ALcinoe который в разы быстрее, но даже это медленней чем использование
пары TArray<string>.

И хоть TArray<string> самый быстрый из найденных мною способов, всё равно процесс идёт медленно, будь то через сравнение A[x] = B[y] или CompareText.

[^D^ima]

Jiro
А что за сами строки? Большие, маленькие?

Цитата Jiro @ 13.12.18, 13:38

в основном они все про TStringList

Ты имеешь в виду опцию игнорировать дубликаты?
THashedStringList все-же попробуй

Цитата Jiro @ 13.12.18, 10:22

а в интернетах есть сервис который это делает за несколько секунд.

А откуда ты знаешь какие у него мощности? некорректно это сравнивать.

[Pavia]

Цитата Jiro @ 13.12.18, 13:38

И хоть TArray<string> самый быстрый из найденных мною способов, всё равно процесс идёт медленно,

Я использую TList
LinesRec:=TList<TRec>.Create(TComparer<TRec>.Construct(CompareRec));
// сортирую массив
LinesRec.Sort;
// помечаю тех которые надо удалить.
//снова сортирую чтобы повторы оказались в конце

//и далее используя downto удаляю
for i:=NewLinesRec.Count-1 downto 0 do
begin
if (NewLinesRec[i].Flag) then
NewLinesRec.Delete(i);
end;

Работает за пару секунд.

Добавлено 13.12.18, 16:06
^D^ima
Нет смысла вычислять хэш так как для вычисления надо пройтись по всем символам строки. А сравнение уже на первом отличном прервёт свой поиск.
Т.е сравнение работает на несколько раз быстрее чем хэши.

Сообщение отредактировано: Pavia - 13.12.18, 16:09

[Славян]

Цитата Pavia @ 13.12.18, 16:03

Нет смысла вычислять хэш так как для вычисления надо пройтись по всем символам строки. А сравнение уже на первом отличном прервёт свой поиск.

Здрасьте, приехали! А если строки - километровые, а отличия выстроились в последних метрах? И тогда ваши первые отличия придётся искать ой сколь долго! Так что - не, в общем случае ложное утверждение.

Цитата Pavia @ 13.12.18, 16:03

Т.е сравнение работает на несколько раз быстрее чем хэши.

Однозначно не во всех случаях (см. выше).

[^D^ima]

Цитата Pavia @ 13.12.18, 16:03

Нет смысла вычислять хэш так как для вычисления надо пройтись по всем символам строки.

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

Цитата Pavia @ 13.12.18, 16:03

// сортирую массив
// помечаю тех которые надо удалить.
//снова сортирую чтобы повторы оказались в конце
//и далее используя downto удаляю

а зачем так сложно делать?
не проще

  Sl:=TStringList.Create;
  sl.Duplicates:=dupIgnore;
  sl.Sorted:=true;

[Jiro]

Цитата ^D^ima @ 13.12.18, 13:44

А откуда ты знаешь какие у него мощности? некорректно это сравнивать.

Ну во первых тестил, а во вторых цитирую Zeusa автора (alcinoe)

Цитата ^D^ima @ 13.12.18, 13:44

Ты имеешь в виду опцию игнорировать дубликаты?

И так и без этого.

PaviaСлавян^D^ima
В моём случаи строки короткие и числовые, хэш вычеслять лишнее.

========

ЗЫ: Господа, тут выяснилось, что я дико натупил и делал сравнение без сортировки.

Ну как-бы одуплив свой косяк, наваял такой вот алгоритм, 250 000 строк обрабатывает менее чем за полсекунды.
Вобщем всем спасибо, и сорри что побеспокоил.

program Project1;
 
{$APPTYPE CONSOLE}
{$R *.res}
 
uses
  System.SysUtils,
  System.Classes,
  System.Types,
  //SynCommons,
  IOUtils,//.TFile,
  Generics.Collections, Generics.Defaults ,
  System.Diagnostics;
 
var
  i, i2: integer;
  LStopwatch: TStopwatch;
  SDA  : System.Types.TStringDynArray;
  ici  : Integer;
begin
  try
    LStopwatch := TStopwatch.Create;
    LStopwatch.Start;
         SDA := IOUtils.TFile.ReadAllLines('CID.txt');
         TArray.Sort<String>(SDA, TStringComparer.Ordinal);
         for i:= High(SDA) downto 0 do
         begin
            ici := 0;
             if i > 0 then  
               for i2 :=i-1 downto 0 do          
               if CompareText(SDA[i], SDA[i2]) = 0 then
               begin
                Inc(ici);
                if i2 = 0 then Delete(SDA, i-ici, ici);
               end else
               begin
                 if ici > 0 then Delete(SDA, i-ici, ici);
                 Break;
               end;            
         end;
    IOUtils.TFile.WriteAllLines('CID_out.txt', SDA);
 
    LStopwatch.Stop;
    Writeln('Elapsed: ',LStopwatch.ElapsedMilliseconds.ToString);
    Readln;
 
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
 
end.

upd

Сообщение отредактировано: Jiro - 13.12.18, 18:51

[korvin]

Цитата Pavia @ 13.12.18, 16:03

Нет смысла вычислять хэш так как для вычисления надо пройтись по всем символам строки. А сравнение уже на первом отличном прервёт свой поиск.
Т.е сравнение работает на несколько раз быстрее чем хэши.

А пройтись по всем строкам в списке вместо прямого обращения по хеш-коду не нужно?

Во-первых, сложность алгоритма (O) почти всегда определяется для худшего случая, а значит, сложность вычисления хеша и сложность посимвольнго сравнения одинаковая — O(n). Да, на практике посимвольное сравнение будет не хуже, а часто — лучше, чем вычисление хеша,

однако

во-вторых, тут обсуждается не сравнение каких-то отдельных строк, а поиск слова в коллекции, соответственно, даже если в среднем сравнение строк у тебя отрабатывает в два раза быстрее вычисления хеша (O(n/2) vs O(n), где n — длина строки), и в среднем методу поиска, использующему это посимвольное сравнение, приходится обходить половину списка (O(n/2) vs O(1) для хеш-таблицы, где n — количество элементов в списке/таблице), то для поиска строки, длинной 100 символов в списке/таблице из 300_000 строк, каждая длиной в 100 символов
– для списка с посимвольным сравнением уйдёт (O(n/2). 100) * (O(n/2). 300_000) = 50 * 150_00 = 7_500_000 операций над единичным символом.
– для хеш-таблицы уйдёт (O(n/2). 100) * (O(1). 300_000) = 50 * 1 = 50 операций над единичным символом.

Сообщение отредактировано: korvin - 15.12.18, 18:44

[Fr0sT]

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