盒子论坛 v2.1

比如：
  A[0]:='C7';
  A[1]:='C6';
  A[2]:='C9';
  A[3]:='C1';
  ...
这时候,如果想知道'C9'对应的数组序号2 ；好像没有什么好方法：
用“最笨”的方法：
  for i:=low(A) TO high(A) do
  begin
      if A[i]='C9' THEN
      begin
        找到序号:i;
        break;
       end;
      continue;
  end;

这种方法最简单，但也是最傻的，如果数组很长，比如有1万个以上；
如果频繁反找，那么效率浪费很严重；

后来想到了一个方法，就是建立一个辅助的记录类型；
按照数组值的顺序重建一个数组，这个数组做了和原数组的关系映射；
这样，就构造了一个有规律的数组；可以用二分法查找，速度快很多；
但是就是太麻烦；

type
   Trec=RECORD
      value:string;
      ord: integer;
   end;
var
  A:ARRAY[0.99] of string;
  rec :ARRAY[0.99] of Trec;

begin
  A[0].VALUE:='C13';
  A[1].VALUE:='C34';
  ....
   用快速排序把将0..99按照a[i].value从小到大写入到rec[i].value;,同时将数组A的次序值写入；
  因为 rec[i].value是排序的，所以可以用二分法查找rec的次序，在根据这个次序读取rec[i].ord 得到对应的数组A的次序；

end;

这个方法速度会快很多，因为做了一个初始化的辅助记录处理；

所以程序里，以后定位就会一直很快；

但是这样写又麻烦了很多；
----------------------------------------------
青云论坛

作者：

qingyun (qingyun)	★☆☆☆☆	-
	盒子活跃会员

2011/7/10 16:24:28

1楼：

http://www.delphibbs.com/delphibbs/DispQ.asp?LID=4011077
----------------------------------------------
青云论坛

作者：

xlonger (xlonger)	★☆☆☆☆	-
	普通会员

2011/7/10 20:19:41

2楼：

好像直接有个   AnsiIndexText().函数

function AnsiIndexText(const AText: string; const AValues: array of string): Integer;
var
  I: Integer;
begin
  Result := -1;
  for I := Low(AValues) to High(AValues) do
    if AnsiSameText(AText, AValues[I]) then
    begin
      Result := I;
      Break;
    end;
end;

不过好像也算这样for的
----------------------------------------------
我打的是酱油，而不是别的什么油。
我灌的是口水，而不是别的什么水。
我聊的折腾不是那个不折腾的折腾。
我说的阿娇不是那个邓玉娇的阿娇。
3个代表,6个为什么,9个肠胃炎。
D性强的领导干部都不喜欢热比娅。
我特别要讲的是,屁民网黄色论坛是我经常上网必选的网站之一

作者：

qingyun (qingyun)	★☆☆☆☆	-
	盒子活跃会员

2011/7/11 6:16:58

3楼：

关键是效率，c# 里可以做hash运算；
delphi高版本里，因该也支持；只是不清楚如何使用；
----------------------------------------------
青云论坛

作者：

sevencat (七猫)	★☆☆☆☆	-
	普通会员

2011/7/11 7:45:44

4楼：

可以使用jcl里的:jcl.sf.net
或者是dolx里的:http://sourceforge.net/projects/dclx/
新版本的java应该内置了。
----------------------------------------------
-

作者：

qingyun (qingyun)	★☆☆☆☆	-
	盒子活跃会员

2011/7/11 10:00:05

5楼：

这个也可以参考：
http://blog.csdn.net/okmnji79513/article/details/4737941

不过是TStringLIst 的hash运算；

缺点是单字段，如果多字段，就没这么容易了；
----------------------------------------------
青云论坛

作者：

tiny_bird (delphi_tokyo)	★☆☆☆☆	-
	盒子活跃会员

2011/7/11 11:18:24

6楼：

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, Generics.Collections, StdCtrls;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Edit1: TEdit;
    procedure FormCreate(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  dict: TDictionary<string, Integer>;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
begin
  Edit1.Text := inttostr(dict.Items['C8']);
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  dict := TDictionary<string, Integer>.Create;
  dict.Add('C6', 1);
  dict.Add('C7', 2);
  dict.Add('C8', 3);
end;

procedure TForm1.FormDestroy(Sender: TObject);
begin
  dict.Free;
end;
----------------------------------------------
winsock api，通讯，多线程，VCL，Java

作者：

qingyun (qingyun)	★☆☆☆☆	-
	盒子活跃会员

2011/7/11 17:10:30

7楼：

楼上的方法不错，简单；
就是不知道效率如何，我在结合hashStringList 对比一下。
----------------------------------------------
青云论坛

作者：

qingyun (qingyun)	★☆☆☆☆	-
	盒子活跃会员

2011/7/11 17:26:37

8楼：

这段代码：
http://blog.csdn.net/okmnji79513/article/details/4737941

我测试的结果：

200000 项 TStringList 创建耗时：159毫秒
200 项字符串搜索 TStringList 耗时：18264毫秒
200000 项索引搜索 TStringList 耗时：13毫秒
100000 项 TStringList 随位置插入耗时：64705毫秒
100000 项 TStringList 0位置插入耗时：193370毫秒
----------
200000 项 THashedStringList 创建耗时：82毫秒
200 项字符串搜索 THashedStringList 耗时：122毫秒
200000 项索引搜索 THashedStringList 耗时：15毫秒
100000 项 THashedStringList 随位置插入耗时：37毫秒
100000 项 THashedStringList 0位置插入耗时：23692毫秒
----------------------------------------------
青云论坛

作者：

qingyun (qingyun)	★☆☆☆☆	-
	盒子活跃会员

2011/7/11 19:02:58

9楼：

用 TDictionary 的方法，反查效率最高；

procedure TForm1.Button1Click(Sender: TObject);
var
dict: TDictionary<string, Integer>;

    hsl: THashedStringList;
  I: Integer;
  datePointer: TDateTime;
  hslTime, hslTimeC, hslTimeI: Int64;
  tempInt: Integer;
  tempstr: string ;
begin
{  dict := TDictionary<string, Integer>.Create;
  dict.Add('C6', 1);
  dict.Add('C7', 2);
  dict.Add('C8', 3);
}
    hslTime := 0;
    hslTimeC := 0;
    datePointer := Now();
    dict := TDictionary<string, Integer>.Create;

    for I := 1 to 200000 do
    begin
         dict.Add('string_'+IntToStr(i), i);

    end;
    hslTime := MilliSecondsBetween(Now, datePointer);
    mmo1.Lines.Add('200000 项 TDictionary 创建耗时：'+IntToStr(hslTime)+'毫秒');

    datePointer := Now();
    for I := 1 to 200000 do
    begin
     //r dict.Items['C8']);

        tempInt := dict.Items['string_'+IntToStr(i)];
       // SELF.mmo1.Lines.Add(IntToStr(tempInt));
    end;
    hslTime := MilliSecondsBetween(Now, datePointer);
    mmo1.Lines.Add('200000 项字符串搜索 TDictionary 耗时：'+IntToStr(hslTime)+'毫秒');
    FreeAndNil(dict);
end;

结果是：
200000 项 TDictionary 创建耗时：554毫秒
200000 项字符串搜索 TDictionary 耗时：211毫秒

缺点是，不像 THashedStringList  那样可以正反查；

用TstingList sorted=ture 后，在用 indexof 会执行折半查找；
得到结果是：
200000 项字符串搜索 TStringList 耗时：3682毫秒
----------------------------------------------
青云论坛

作者：

qingyun (qingyun)	★☆☆☆☆	-
	盒子活跃会员

2011/7/11 19:29:04

10楼：

总结（测试条件是20万条数据）
1. TDictionary<string, Integer> 的反查效率最高；
  基本是1/100毫秒一条，效率高的“不可思议”；
  缺点是不能正查，当然你用for循环正向查找也行，那就没意义了；
  所以，我个人感觉，TDictionary<string, Integer> 类似数据库表的索引或主键；
  假如让我用delphi去做一个数据库，索引的结构可能就是用TDictionary的方法；
  不过我想变通一下，如果是TDictionary<TRecord, Integer>;那么该如何处理；因为反向查找的时候，可能对个字段数据确定一个唯一记录；类似于主键有多个字段；这个看了一下源代码，应该能搞定；
   所以，对于固定的数组或Record类型的数组，用TDictionary辅助造一个索引，还是非常能提高效率的；

2.THashedStringList 是性价比最高的结构；正向查找效率接近1/1000毫秒一条，这个和普通的TStringList基本一致；反向查找的速度是半毫秒1条；而在 TStringList同等条件下反向查找，却基本是100毫秒一条，相差200倍的效率；
但是如果TStringList如果排序，即sorted=true;那么反向查找自动回是折半查找，效率是1/50毫秒一条；速度虽然非常快，但是因为排序了，序号已经变了，所以这里反向查找了，也没多大意义；

总的来说，建议多用TDictionary来实现类似数据库主键的效果，确实挺强的；

其实想想数据库查找数据：比如：
   SELECT * FROM TABLE1 WHERE KEY_FIELD='123';
实际上，也是通过'123'反查记录序号(oracle里就是rowid)，然后根据在根据序号得到整个记录值；套路和TDictionary完全一致；

不过 TDictionary 也有缺点：就是它必须是唯一索引；否者会提示定位多个值的错误；
----------------------------------------------
青云论坛

作者：

qingyun (qingyun)	★☆☆☆☆	-
	盒子活跃会员

2011/7/11 20:17:16

11楼：

另一个感受：
  其实数据结构的哈希运算带来很大的效率提升；
   通过今天的学习，让我更加感受到了一些辅助结构的效率提升，不是一点点；

这和数据库调优有点类似；

   在oracle 数据库里， group by 的实现，在10g以前，是先排序，在分组；
所以得到的据结果总是排好序的；但是效率有时会低；
   排序是很伤效率的；
  就上面这个例子，20万条记录，用stringList.sorted:=true; 相当于做了快速排序；但是需要8秒的时间，太费时了；
  所以oracle 10g之后，可以实现group by 的时候通过hash运算，不进行排序，所以我们看到的结果有时是不排序的，这个就大大实现了效率；至于怎么通过delphi实现不通过排序而group by的效果，我还不会呢；
----------------------------------------------
青云论坛

作者：

sevencat (七猫)	★☆☆☆☆	-
	普通会员

2011/7/11 21:38:34

12楼：

数据库一般是b+树，基本上没有hash的。因为hash是无序的，group by 可能一般会有索引吧。
哈希跟排序没关系，哈希是快查用的。
c++里这些数据结构比较多，boost里扩充了不少这样的二叉树结构。

可以存放相同key的一般叫multimap,这个不知道下面的链接能不能满足你的需要了。
http://www.torry.net/tools/developers/compilers/deex091.zip
----------------------------------------------
-

作者：

qingyun (qingyun)	★☆☆☆☆	-
	盒子活跃会员

2011/7/11 22:57:52

13楼：

在10gR2中,sort group by 已经改为hash group by,它先读一条数据,然后求hash并+1,然后处理第二条,如果第二条的hash已经存在累计值,则+1,否则则产生一个新的结果条目并+1.所以hash group by是不需要排序的,毕竟分组后排序并不是需的,很多人在分组后并不要求排序,所以这样对整个系统的性能有好处...

数据库里 hash join 不要太多；特别是1大表和小表关联的时候；
----------------------------------------------
青云论坛

作者：

billy_ (代码工人)	▲▲▲▲▲	-
	普通会员

2011/7/12 8:25:43

14楼：

sevencat (七猫)

是的还是以b+为主，hash查询时间是个常量，但是是散列应用有局限
----------------------------------------------
远离此地，专心C#

信息

登陆以后才能回复