TStringList启用二进制搜索而不求助于？
TStringList enable Binary search without resorting?
我正在从 ADO 查询构建一个字符串列表，在查询中 return 排序结果然后按顺序添加它们要快得多。这给了我一个已经排序的列表，然后调用 Sort 或设置 sorted true 会花费我时间，因为 Quicksort 算法在已经排序的列表上表现不佳。有什么方法可以将 TStringList 设置为在没有 运行 排序的情况下使用二进制搜索？
在你问我无权访问 CustomSort 属性之前。
假设 StringList 所需的排序顺序与 AdoQuery 的 ORDER BY 相同，我不确定我是否理解您的担心。
当然要做的事情是在 StringList 仍然为空时将 Sorted 设置为 True，然后然后 插入来自 AdoQuery 的行。这样，当 StringList 将要添加一个条目时，它将使用 IndexOf 搜索它，而 IndexOf 又将使用 Find（执行二进制搜索）来检查重复项。但是以这种方式使用 Add 不涉及快速排序，因为 StringList 已经将自己视为已排序。
鉴于您的评论和您自己的回答，我 运行 下面的程序通过 NexusDB 的 Quality Suite 中的 Line Timer 分析器。结果是，尽管使用二分查找与 TStringList.IndexOf 的执行速度存在明显差异，但它们与使用（或不使用）TStringList 的快速排序无关。此外，这种差异可以通过我使用的二进制搜索与 TStringList.Find 工作方式之间的细微差别来解释 - 请参阅下面的更新 #2。
该程序生成 200k 个 100 个字符的字符串，然后将它们插入到一个 StringList 中。 StringList 以两种方式生成，首先在添加任何字符串之前将 Sorted 设置为 True，然后仅在添加字符串后将 Sorted 设置为 True。 StringList.IndexOf 然后您的 BinSearch 用于查找已添加的每个字符串。结果如下：
Line Total Time Source
80 procedure Test;
119 0.000549 begin
120 2922.105618 StringList := GetList(True);
121 2877.101652 TestIndexOf;
122 1062.461975 TestBinSearch;
123 29.299069 StringList.Free;
124
125 2970.756283 StringList := GetList(False);
126 2943.510851 TestIndexOf;
127 1044.146265 TestBinSearch;
128 31.440766 StringList.Free;
129 end;
130
131 begin
132 Test;
133 end.
我遇到的问题是你的BinSearch实际上从来没有returns1而且失败的次数等于搜索的字符串数。如果你能解决这个问题，我很乐意重新进行测试。
program SortedStringList2;
[...]
const
Rows = 200000;
StrLen = 100;
function ZeroPad(Number : Integer; Len : Integer) : String;
begin
Result := IntToStr(Number);
if Length(Result) < Len then
Result := StringOfChar('0', Len - Length(Result)) + Result;
end;
function GetList(SortWhenEmpty : Boolean) : TStringList;
var
i : Integer;
begin
Result := TStringList.Create;
if SortWhenEmpty then
Result.Sorted := True;
for i := 1 to Rows do
Result.Add(ZeroPad(i, StrLen));
if not SortWhenEmpty then
Result.Sorted := True;
end;
Function BinSearch(slList: TStringList; sToFind : String) : integer;
var
i, j, k : integer;
begin
try
i := slList.Count div 2;
k := i;
if i = 0 then
begin
Result := -1;
// SpendLog('BinSearch List Empty, Exiting...');
exit;
end;
while slList.Strings[i] <> sToFind do
begin
if CompareText(slList.Strings[i], sToFind) < 0 then
begin
j := i;
k := k div 2;
i := i + k;
if j=i then
break;
end else
if CompareText(slList.Strings[i], sToFind) > 0 then
begin
j := i;
k := k div 2;
i := i - k;
if j=i then
break;
end else
break;
end;
if slList.Strings[i] = sToFind then
result := i
else
Result := -1;
except
//SpendLog('<BinSearch> Exception: ' + ExceptionMessage + ' At Line: ' + Analysis.LastSourcePos);
end;
end;
procedure Test;
var
i : Integer;
StringList : TStringList;
procedure TestIndexOf;
var
i : Integer;
Index : Integer;
Failures : Integer;
S : String;
begin
Failures := 0;
for i := 1 to Rows do begin
S := ZeroPad(i, StrLen);
Index := StringList.IndexOf(S);
if Index < 0 then
Inc(Failures);
end;
Assert(Failures = 0);
end;
procedure TestBinSearch;
var
i : Integer;
Index : Integer;
Failures : Integer;
S : String;
begin
Failures := 0;
for i := 1 to Rows do begin
S := ZeroPad(i, StrLen);
Index := BinSearch(StringList, S);
if Index < 0 then
Inc(Failures);
end;
//Assert(Failures = 0);
end;
begin
StringList := GetList(True);
TestIndexOf;
TestBinSearch;
StringList.Free;
StringList := GetList(False);
TestIndexOf;
TestBinSearch;
StringList.Free;
end;
begin
Test;
end.
更新我在维基百科文章https://en.wikipedia.org/wiki/Binary_search_algorithm中写了自己实现的搜索算法如下：
function BinSearch(slList: TStringList; sToFind : String) : integer;
var
L, R, m : integer;
begin
L := 0;
R := slList.Count - 1;
if R < L then begin
Result := -1;
exit;
end;
m := (L + R) div 2;
while slList.Strings[m] <> sToFind do begin
m := (L + R) div 2;
if CompareText(slList.Strings[m], sToFind) < 0 then
L := m + 1
else
if CompareText(slList.Strings[m], sToFind) > 0 then
R := m - 1;
if L > R then
break;
end;
if slList.Strings[m] = sToFind then
Result := m
else
Result := -1;
end;
这似乎工作正常，使用它重新分析测试应用给出了这些结果：
Line Total Time Source
113 procedure Test;
153 0.000490 begin
154 3020.588894 StringList := GetList(True);
155 2892.860499 TestIndexOf;
156 1143.722379 TestBinSearch;
157 29.612898 StringList.Free;
158
159 2991.241659 StringList := GetList(False);
160 2934.778847 TestIndexOf;
161 1113.911083 TestBinSearch;
162 30.069241 StringList.Free;
在该显示中，二分搜索明显优于 TStringList.IndexOf 并且与我的预期相反，在添加字符串之前或之后将 TStringList.Sorted 设置为 True 并没有真正的区别。
Update#2原来BinSearch比TStringList.IndexOf快的原因纯粹是因为BinSearch用了CompareText 而 TStringList.IndexOf 使用 AnsiCompareText （通过 .Find）。如果我将 BinSearch 更改为使用 AnsiCompareText，它会比 TStringList.IndexOf!
慢 1.6 倍
最后我只是破解了二进制搜索来检查字符串列表，就像数组一样：
Function BinSearch(slList: TStringList; sToFind : String) : integer;
var
i, j, k : integer;
begin
try
try
i := slList.Count div 2;
k := i;
if i = 0 then
begin
Result := -1;
SpendLog('BinSearch List Empty, Exiting...');
exit;
end;
while slList.Strings[i] <> sToFind do
begin
if CompareText(slList.Strings[i], sToFind) < 0 then
begin
j := i;
k := k div 2;
i := i + k;
if j=i then
break;
end else
if CompareText(slList.Strings[i], sToFind) > 0 then
begin
j := i;
k := k div 2;
i := i - k;
if j=i then
break;
end else
break;
end;
if slList.Strings[i] = sToFind then
result := i
else
Result := -1;
except
SpendLog('<BinSearch> Exception: ' + ExceptionMessage + ' At Line: ' + Analysis.LastSourcePos);
end;
finally
end;
end;
如果需要，我稍后会清理它。
我正要建议使用插入器 class 直接更改 FSorted 字段而不调用其 setter 方法，作为副作用调用 Sort 方法。但是看Delphi2007年TStringList的实现，发现Find总是会二分查找，不检查Sorted属性。如果列表项未排序，这当然会失败，但在您的情况下是这样。所以，只要你记得调用 Find 而不是 IndexOf，你什么都不用做。
我正在从 ADO 查询构建一个字符串列表，在查询中 return 排序结果然后按顺序添加它们要快得多。这给了我一个已经排序的列表，然后调用 Sort 或设置 sorted true 会花费我时间，因为 Quicksort 算法在已经排序的列表上表现不佳。有什么方法可以将 TStringList 设置为在没有 运行 排序的情况下使用二进制搜索？ 在你问我无权访问 CustomSort 属性之前。
假设 StringList 所需的排序顺序与 AdoQuery 的 ORDER BY 相同，我不确定我是否理解您的担心。
当然要做的事情是在 StringList 仍然为空时将 Sorted 设置为 True，然后然后 插入来自 AdoQuery 的行。这样，当 StringList 将要添加一个条目时，它将使用 IndexOf 搜索它，而 IndexOf 又将使用 Find（执行二进制搜索）来检查重复项。但是以这种方式使用 Add 不涉及快速排序，因为 StringList 已经将自己视为已排序。
鉴于您的评论和您自己的回答，我 运行 下面的程序通过 NexusDB 的 Quality Suite 中的 Line Timer 分析器。结果是，尽管使用二分查找与 TStringList.IndexOf 的执行速度存在明显差异，但它们与使用（或不使用）TStringList 的快速排序无关。此外，这种差异可以通过我使用的二进制搜索与 TStringList.Find 工作方式之间的细微差别来解释 - 请参阅下面的更新 #2。
该程序生成 200k 个 100 个字符的字符串，然后将它们插入到一个 StringList 中。 StringList 以两种方式生成，首先在添加任何字符串之前将 Sorted 设置为 True，然后仅在添加字符串后将 Sorted 设置为 True。 StringList.IndexOf 然后您的 BinSearch 用于查找已添加的每个字符串。结果如下：
Line Total Time Source
80 procedure Test;
119 0.000549 begin
120 2922.105618 StringList := GetList(True);
121 2877.101652 TestIndexOf;
122 1062.461975 TestBinSearch;
123 29.299069 StringList.Free;
124
125 2970.756283 StringList := GetList(False);
126 2943.510851 TestIndexOf;
127 1044.146265 TestBinSearch;
128 31.440766 StringList.Free;
129 end;
130
131 begin
132 Test;
133 end.
我遇到的问题是你的BinSearch实际上从来没有returns1而且失败的次数等于搜索的字符串数。如果你能解决这个问题，我很乐意重新进行测试。
program SortedStringList2;
[...]
const
Rows = 200000;
StrLen = 100;
function ZeroPad(Number : Integer; Len : Integer) : String;
begin
Result := IntToStr(Number);
if Length(Result) < Len then
Result := StringOfChar('0', Len - Length(Result)) + Result;
end;
function GetList(SortWhenEmpty : Boolean) : TStringList;
var
i : Integer;
begin
Result := TStringList.Create;
if SortWhenEmpty then
Result.Sorted := True;
for i := 1 to Rows do
Result.Add(ZeroPad(i, StrLen));
if not SortWhenEmpty then
Result.Sorted := True;
end;
Function BinSearch(slList: TStringList; sToFind : String) : integer;
var
i, j, k : integer;
begin
try
i := slList.Count div 2;
k := i;
if i = 0 then
begin
Result := -1;
// SpendLog('BinSearch List Empty, Exiting...');
exit;
end;
while slList.Strings[i] <> sToFind do
begin
if CompareText(slList.Strings[i], sToFind) < 0 then
begin
j := i;
k := k div 2;
i := i + k;
if j=i then
break;
end else
if CompareText(slList.Strings[i], sToFind) > 0 then
begin
j := i;
k := k div 2;
i := i - k;
if j=i then
break;
end else
break;
end;
if slList.Strings[i] = sToFind then
result := i
else
Result := -1;
except
//SpendLog('<BinSearch> Exception: ' + ExceptionMessage + ' At Line: ' + Analysis.LastSourcePos);
end;
end;
procedure Test;
var
i : Integer;
StringList : TStringList;
procedure TestIndexOf;
var
i : Integer;
Index : Integer;
Failures : Integer;
S : String;
begin
Failures := 0;
for i := 1 to Rows do begin
S := ZeroPad(i, StrLen);
Index := StringList.IndexOf(S);
if Index < 0 then
Inc(Failures);
end;
Assert(Failures = 0);
end;
procedure TestBinSearch;
var
i : Integer;
Index : Integer;
Failures : Integer;
S : String;
begin
Failures := 0;
for i := 1 to Rows do begin
S := ZeroPad(i, StrLen);
Index := BinSearch(StringList, S);
if Index < 0 then
Inc(Failures);
end;
//Assert(Failures = 0);
end;
begin
StringList := GetList(True);
TestIndexOf;
TestBinSearch;
StringList.Free;
StringList := GetList(False);
TestIndexOf;
TestBinSearch;
StringList.Free;
end;
begin
Test;
end.
更新我在维基百科文章https://en.wikipedia.org/wiki/Binary_search_algorithm中写了自己实现的搜索算法如下：
function BinSearch(slList: TStringList; sToFind : String) : integer;
var
L, R, m : integer;
begin
L := 0;
R := slList.Count - 1;
if R < L then begin
Result := -1;
exit;
end;
m := (L + R) div 2;
while slList.Strings[m] <> sToFind do begin
m := (L + R) div 2;
if CompareText(slList.Strings[m], sToFind) < 0 then
L := m + 1
else
if CompareText(slList.Strings[m], sToFind) > 0 then
R := m - 1;
if L > R then
break;
end;
if slList.Strings[m] = sToFind then
Result := m
else
Result := -1;
end;
这似乎工作正常，使用它重新分析测试应用给出了这些结果：
Line Total Time Source
113 procedure Test;
153 0.000490 begin
154 3020.588894 StringList := GetList(True);
155 2892.860499 TestIndexOf;
156 1143.722379 TestBinSearch;
157 29.612898 StringList.Free;
158
159 2991.241659 StringList := GetList(False);
160 2934.778847 TestIndexOf;
161 1113.911083 TestBinSearch;
162 30.069241 StringList.Free;
在该显示中，二分搜索明显优于 TStringList.IndexOf 并且与我的预期相反，在添加字符串之前或之后将 TStringList.Sorted 设置为 True 并没有真正的区别。
Update#2原来BinSearch比TStringList.IndexOf快的原因纯粹是因为BinSearch用了CompareText 而 TStringList.IndexOf 使用 AnsiCompareText （通过 .Find）。如果我将 BinSearch 更改为使用 AnsiCompareText，它会比 TStringList.IndexOf!
最后我只是破解了二进制搜索来检查字符串列表，就像数组一样：
Function BinSearch(slList: TStringList; sToFind : String) : integer;
var
i, j, k : integer;
begin
try
try
i := slList.Count div 2;
k := i;
if i = 0 then
begin
Result := -1;
SpendLog('BinSearch List Empty, Exiting...');
exit;
end;
while slList.Strings[i] <> sToFind do
begin
if CompareText(slList.Strings[i], sToFind) < 0 then
begin
j := i;
k := k div 2;
i := i + k;
if j=i then
break;
end else
if CompareText(slList.Strings[i], sToFind) > 0 then
begin
j := i;
k := k div 2;
i := i - k;
if j=i then
break;
end else
break;
end;
if slList.Strings[i] = sToFind then
result := i
else
Result := -1;
except
SpendLog('<BinSearch> Exception: ' + ExceptionMessage + ' At Line: ' + Analysis.LastSourcePos);
end;
finally
end;
end;
如果需要，我稍后会清理它。
我正要建议使用插入器 class 直接更改 FSorted 字段而不调用其 setter 方法，作为副作用调用 Sort 方法。但是看Delphi2007年TStringList的实现，发现Find总是会二分查找，不检查Sorted属性。如果列表项未排序，这当然会失败，但在您的情况下是这样。所以，只要你记得调用 Find 而不是 IndexOf，你什么都不用做。