TStringList

← →
mazik (2003-04-30 10:07) [0]

Добрый день.Помогите как-нить оптимизировать процесс сравнения двух наборов TStringList и нахождения в них различающихся строк с последующим выводом их в TRichedit.Проблема заключается в том, что в процессе сравнения программа в "диспетчере задач" не отвечает ,выполняется долго.Сравниваемые наборы имеют размеры около 4Мб.Или так и надо?
musor1.Sort;
musor2.Sort;
i:=0;
while i<>(musor1.Count) do begin
k:=musor2.IndexOf(musor1[i]);
if k<>-1 then begin
musor1.Delete(i);
musor2.Delete(k) end else i:=i+1;end;
//musor1,musor2:TStringList

← →
PGM (2003-04-30 10:22) [1]

Application.ProcessMessages внутри цикла стедлает программу более отзывчивой.
А для ускорения я не стал бы использрвать IndexOf - списки то отсортированные! Двигай по обоим и сравнивай на больше-меньше. Будет гораздо быстрее. Да и раз есть удаление лучше бы двигаться от конца к началу.

← →
jack128 (2003-04-30 10:30) [2]

IndexOf - лишнее!

var i1, i2 : integer;
ResulStrings : TstringList;
i1 := 0 ; i2 := 0;
while (i1 < musor1.Count) and (i2 < musor2.count) do begin
if musor1[i1] <> musor2[i2] then
if musor1[i1] > musor2[i2] then begin
ResulStrings.Add(musor2[i2]);
inc(i2);
end
else begin
ResultStrings.Add(musor1[i1]);
inc(i1);
end;
end;
for i := i1 to musor1.count do ResultString.Add(musor1[i]);
for i := i2 to musor2.count do ResultString.Add(musor2[i]);

Возможны баги, конечно...

← →
jack128 (2003-04-30 10:33) [3]

Уже вижу баги :-)
for i := i1 to musor1.count -1 do ResultString.Add(musor1[i]);
for i := i2 to musor2.count -1 do ResultString.Add(musor2[i]);

И списки естественно должны быть отсортированны

← →
REA (2003-04-30 11:05) [4]

В D7 есть еще THashedStringList, но не думаю, что с ним получится быстрее, чем метод jack128. Разве что сортировка может быть быстрее, если там Hash используется. Count имеет смысл вынести в переменные - не будет вызовов функций.

← →
han_malign (2003-04-30 11:12) [5]

если нужно получить именно два листа с уникальными для обоих значениями:
{Sort естественно} i:=0;j:=0; while(i<musor1.Count)and(j<musor2.Count)do begin while(j<musor2.Count)and(musor1[i]<musor2[j])do begin inc(j); if(j mod 100 = 0)//для разумной альтернативы между скоростью и "жизнью" приложения then ProcessMessages; end; if((j<musor2.Count)//проверяем что musor2 еще не кончился and(musor1[i]=musor2[j]))then begin musor1.Delete(i);musor2.Delete(j); end; inc(i); if(i mod 100 = 0)//для разумной альтернативы между скоростью и "жизнью" приложения then ProcessMessages; end;
- мысль такая - в каждом списке пропускаем все элементы которые меньше текущего в другом, то есть, заведомо не равны

← →
han_malign (2003-04-30 11:18) [6]

> Count имеет смысл вынести в переменные - не будет вызовов функций.
- не имеет, идет обращение непосредственно к TStringList.FCount, и при работе с листами, с упаковкой на лету, он меняется...

← →
jack128 (2003-04-30 11:30) [7]

Ещё можно предложить ResultStrings.Capacity := 1000; выставить в самом начале

← →
REA (2003-04-30 11:37) [8]

>при работе с листами, с упаковкой на лету, он меняется...

В алгоритме Jack128 не меняется.

>идет обращение непосредственно к TStringList.FCount
function TStringList.GetCount: Integer;
begin
Result := FCount;
end;
Оно конечно идет, но через функцию.

← →
Sha (2003-04-30 11:42) [9]

Решил тоже позабавиться (настроение праздничное:) var i1, i2, j1, j2, k: integer; sl1, sl2, sl3: TStringList; begin //предполагается, что sl1 и sl2 не содержат дубликатов sl3:=TStringList.Create; j1:=sl1.Count; j2:=sl2.Count; i1:=0; i2:=0; while true do begin; if i2=j2 then begin; while i1<j1 do begin; sl3.Add(sl1[i1]); inc(i1); end; break; end else if i1=j1 then begin; while i2<j2 do begin; sl3.Add(sl2[i2]); inc(i2); end; break; end else begin; k:=AnsiCompareStr(sl1[i1],sl2[i2]); if k<0 then begin; sl3.Add(sl1[i1]); inc(i1); end else if k>0 then begin; sl3.Add(sl2[i2]); inc(i2); end else begin; inc(i1); inc(i2); end; end end; .............. sl3.Free; end;

← →
jack128 (2003-04-30 11:45) [10]

Sha © (30.04.03 11:42)

> //предполагается, что sl1 и sl2 не содержат дубликатов
Если так предположить, я оптимизирую твой код так :
ResultStrings.AddStrings(sl1);
ResultStrings.AddStrings(sl2);
:-))

← →
han_malign (2003-04-30 11:53) [11]

2 REA
Classes.pas
TList
property Count: Integer read FCount write SetCount;

IInterfaceList
TInterfaceList
TCollection
property Count: Integer read GetCount write SetCount;
TStrings
property Count: Integer read GetCount;

- да, не заметил, в Borland-е явно кто-то перетрудился...

← →
Sha (2003-04-30 11:54) [12]

2jack128 © (30.04.03 11:45)

Не так понял. Очевидно, что имелось ввиду: каждый не содержат дубликатов внутри себя.

Уже празднуешь? :)))

← →
Sha (2003-04-30 12:12) [13]

А теперь задумаемся, как предложенные решения будут работать в вырожденном случае, когда количество записей в одном списке 100000, а в другом - 1.

← →
han_malign (2003-04-30 14:00) [14]

Кстати есть полезный метод Find, который все таки дихотомией ищет а не перебором...

← →
Leran2002 (2003-04-30 14:33) [15]

> mazik (30.04.03 10:07)

Если строки не слишком длинные, можно поробвать использовать БД, для поиска строк...
Будут 2 таблицы скажем A и B с одним полем, txt например...

Ну загоняешь строки из musor1 в A, а из musor2 в B...
Дальше один запросик и усе... :))

SELECT txt FROM A WHERE txt not in (SELECT txt FROM B)

или

SELECT txt FROM B WHERE txt not in (SELECT txt FROM A)

Поиск сработает на 100%... Удачи...

← →
evvcom (2003-04-30 14:41) [16]

> Leran2002 © (30.04.03 14:33)
> Если строки не слишком длинные, можно поробвать использовать БД

Может сюда еще всю мощь Интернета подключить?

← →
Leran2002 (2003-04-30 14:51) [17]

> evvcom © (30.04.03 14:41)

Я предложил метод который можно использовать, и по моему очень даже не плохой...

Так что считаю Ваше замечание совсем не в тему...

← →
Smithson (2003-04-30 15:00) [18]

Leran2002
Просили же оптимизировать метод...
Загоняешь в БД... Сколько, по-твоему, будет загоняться в БД два списка по 40 Мег?

← →
Leran2002 (2003-04-30 15:17) [19]

← →
evvcom (2003-04-30 15:26) [20]

> Leran2002 © (30.04.03 14:51)
>
> Я предложил метод который можно использовать, и по моему
> очень даже не плохой...
>
> Так что считаю Ваше замечание совсем не в тему...

Использование БД потребует установки доп. ПО. Если BDE, то на машине, где стоит Дельфи, БДЕ уже есть. Правильно, здесь не важно, а вот на другие машины, чтобы поставить такую вроде простенькую прогу, простого копирования exe будет совсем недостаточно. Или OCX-компоненты, тоже надо их еще регистрировать, столько геморроя от такой маленькой программки. Не стоит того, поэтому, я считаю, что мое замечание совсем даже в тему.

← →
Leran2002 (2003-04-30 15:49) [21]

> evvcom © (30.04.03 15:26)

Еще раз повторяю я только предложил метод, а надо это или не надо пускай решает хозяин данной веточки...
Ладно думаю не стоит продолжать спор... Без обид...

TStringList Найти похожие ветки