怎样快速删除TStringList型变量中的重复项？(15分)

TENTODBV · 2003-03-24

有一个TStringList类型的SL
var
SL:TStringList;
其中大约有200万个ListItem,其中有大量重复项，大约占总数的一半,怎样快速删除重复项？

我用的笨办法是先排序(用TStringList的sort方法)，然后再提取不重复项。当item项数不大（几十万）时，速度还
可以接受，但当item项数进一步加大时，大量的时间都花在排序上了。

ReallyFail · 2003-03-24

我曾看到一篇HUBDOG葵花宝典上面的文章，其中有一篇是关于删除TSTRINGS的里头的
项目的，不知道你看过没有，没看过的话看看，可能对删除ITEM有一定的帮助！

yetxr · 2003-03-24

我想最好的方法是在添加时先判断有Item中是知有该项，这样就不会存在这样的问题了，如果要到后面才来删除就太费事了。
if 有 then
exit
else
添加；

TENTODBV · 2003-03-24

TO yetxr
你说的方法我试过，我是将StringList的sorted属性设为true,然后find,返回false则添加,
结果很慢

jlutt-sadan · 2003-03-24

试试这个，感觉也不是挺快，没有和其它的比较
procedure TForm1.Button1Click(Sender: TObject);
var
sl: TStringList;
begin
sl := TStringList.Create;
try
with sl do begin
Sorted := True;
Duplicates := dupIgnore;
AddStrings(Memo1.Lines);
end;
Listbox1.Items.Assign(sl);
finally
sl.Free;
end;

end;

procedure TForm1.Button2Click(Sender: TObject);
var
i:Integer;
begin
for i:=0 to 10000 do
Memo1.Lines.Add(IntToStr(i));
for i:=0 to 10000 do
Memo1.Lines.Add(IntToStr(i));
end;

ReallyFail · 2003-03-24

那只能用类似yetxr的方法了。刚才看了TSTRINGLIST，在删除上已经不大可能有优化了。
但可以做适当的改进，不要使用SORTED属性，自己写个折半查找函数（可以返回位置，及是否找到）。
增加时调用该函数若找到就推出，否则插入函数返回的位置。

TENTODBV · 2003-03-24

TO ReallyFail
Find本身就具有你所说的功能，除了返回是否找到的布尔值外，它的第二个参数返回插入
位置，但要求SORTED属性为true

TStringList用的是快速排序。我前面的方法之所以慢，我想是因为没有充分利用在排序
过程中的比较结果(即在排序的比较过程中发现相同的值立即删除其中一个，而不是排序完再删除)。

Traveller · 2003-03-24

jlutt-sadan的方法是最简便的

ReallyFail · 2003-03-24

感觉SORTED属性若为真的话，在加入的时候是先加入然后在排序！！！！！！
而我的做法是先查找然后在插入。上面的做法，就是自己写查找算法，找到就不插入，
找不到就插入，这样子就自己形成有序的ITEMS。而不要在去排序了。因为排序的话你要
移动N次的内存。但插如可能就一次！！且有序的查找（可以用折半查找）还是满快的！！

以上如有错误之处请多见量我的不懂装懂！！！！！！！！！！！不好意思！！！

pnljh · 2003-03-24

排序后用二分查找

beta · 2003-03-24

关键是添加的时候就要注意！

添加之前先置 [red]Sorted[/red] 属性为 [blue]True[/blue]，然后置 [red]Duplicates[/red] 属性为 [blue]dupIgnore[/blue]，
这样，在添加的时候就[red]自动忽略[/red][blue]重复项[/blue]了。

TENTODBV · 2003-03-24

二分法只能用于已经排序的列表，而TStringList是不允许对Sorted为true的列表进行
插入操作的,这就不得不反复切换Sorted为true和false

beta · 2003-03-24

//TStringList是不允许对Sorted为true的列表进行
//插入操作的,这就不得不反复切换Sorted为true和false
不用啊，你直接 Add 进去，它会自动帮你插入到适当（排序）的位置的啊。

TENTODBV · 2003-03-25

我测试的结果，在多数情况下，当item项数较多的情况下用以下方法
Sorted := True;
Duplicates := dupIgnore;
的速度还不如添加时用如下方法
Sorted := false;
Duplicates := dupAccept;
当全部添加完后，再排序，最后提取不重复项

yetxr · 2003-03-25

too 楼主
没有必要自己去排序的，你就用TStringlist的方法就可以
如下：
var
i:integer;
s:string;//你要添加的字符
begin
if stringlist.indexof(s)>-1 then
Stringlist.add(s)
else
exit;
但愿对你有所帮助

小笨苯 · 2003-03-26

我的意见是：
再另建立一个TStringList实例B，设置其自动排序，从已知的这个TStringList实例A中，取出一个
放入B中，再从A中取出一个，和B中的所有元素比较一下（由于B一开始就是排序的，所以用Find肯定
会很快），如果没找到，就将其添加到B中，否则再从A中取下一个......如此反复，当取完A
中的元素，B中的元素也就是不重复，且排好序的了。

coolbaby · 2003-03-26

sort一下
再判断

gamegirl · 2003-03-26

LiChaoHui · 2003-03-26

既然已经排过序了，那么相同的项必然是相邻的
只比较相邻的就可以了

ReallyFail · 2003-03-26

to yetxr
如果按照你的做法的话，如果INDEXOF返回为-1，那么你在加入的时候肯定是加到最后
一条，而这时候想排序的话你肯定要做一次排序。那还不如自己先查找，找不到的话返回
该插入的位置，然后再INSERT！找到就不插入！！！！。这样基本就不用去排序了。相信
查找的速度肯定比排序快吧？？而且自己写个折半查找并不是很难吧？？

怎样快速删除TStringList型变量中的重复项？(15分)

TENTODBV

Unregistered / Unconfirmed

ReallyFail

Unregistered / Unconfirmed

yetxr

Unregistered / Unconfirmed

TENTODBV

Unregistered / Unconfirmed

jlutt-sadan

Unregistered / Unconfirmed

ReallyFail

Unregistered / Unconfirmed

TENTODBV

Unregistered / Unconfirmed

Traveller

Unregistered / Unconfirmed

ReallyFail

Unregistered / Unconfirmed

pnljh

Unregistered / Unconfirmed

beta

Unregistered / Unconfirmed

TENTODBV

Unregistered / Unconfirmed

beta

Unregistered / Unconfirmed

TENTODBV

Unregistered / Unconfirmed

yetxr

Unregistered / Unconfirmed

小笨苯

Unregistered / Unconfirmed

coolbaby

Unregistered / Unconfirmed

gamegirl

Unregistered / Unconfirmed

LiChaoHui

Unregistered / Unconfirmed

ReallyFail

Unregistered / Unconfirmed

Similar threads