据说牛得一塌糊涂的哈希(Hash)列表 - DelphiHash.pas(50)

  • 主题发起人 小雨哥
  • 开始时间

小雨哥

Unregistered / Unconfirmed
GUEST, unregistred user!
据听说排队买iPad人群中,有人买到手后就把iPad砸了,并把砸iPad的视频传到了网上,有很多人不理解,问他们既然只是想把iPad砸了,为什么还要排队赶早?这些人回答:iPad不是叫苹果吗?我们才是正真了解iPad的,是苹果,当然要尝试榨汁才是最合适的。橙子是不是也可以榨汁?哈哈我现在在一台AMD双核2.8G电脑上,上面帖子里的数据,由于受电脑限制,只能做9万次循环的测试,下面我要看看做999万次的测试结果会怎么样:Time Elapsed Testeach Compare loop 9999999each Effect loop 100Result := (SUM(100)(for each Compare TimeElapsed)) / 100-------------------------------------1) General Compare: 1611-------------------------------------2) JB_AND_SB Compare: 1576-------------------------------------3) Memory Compare: 1585-------------------------------------呼~~~,好长的时间。但结果在我的意料中:看着SB,实际非常JB的JB_AND_SB函数大获全胜。内存比较函数也超越第一项字符串比较函数,获得第二名。这次内存比较函数的进步,得益于AMD的HT3.0超高内存带宽的优势,这个带宽,整整比Intel的高了一倍多(从这里也可以看出,AMD与Intel相比,虽然使用了更高带宽,但实际效果并没有成倍上升)。当然,这里只是一个测试。虽然我们已经知道JB_AND_SB函数性能不错,但是在写代码中,我仍然不会选择它,原因很简单,s1=s2 无论是看着还是写着,都是清晰明了的,既然s1=s2性能也已经非常不错了,没有理由换成一个性能可能更好,但好得甚为有限的另外的函数,更何况 Delphi 自带的运行时库函数,稳定性是由所有 Delphi 爱好者和使用者、做了无数次义务小白鼠后确定下来的,质量无疑更有保证。这就是我宁愿使用 s1=s2 ,而不使用 JB_AND_SB 的原因。
 

小雨哥

Unregistered / Unconfirmed
GUEST, unregistred user!
呵呵,是的。老是看不到有营养的帖子了。对上面函数的写法做个说明:1)全部比较不使用function,而使用procedure,为的是让返回的结果不能直接参与运算。2)全部函数增加inline编译标志,为的是尽量不因为手写代码导致多次call调用,如果不使用内联,人类习惯与计算机习惯的差异方面,肯定就直接输给用asm写成的代码了。3)在书面函数可能的范围下,尽量不犯常规优化错误。
 
Q

QQ在线

Unregistered / Unconfirmed
GUEST, unregistred user!
汗了,我没表达清楚。。。我是说这句慢了if Result^.Key = Key then
Exit然后,我的意思是让Resut.Key换个N个hash键值代替,而不是使用其实函数计算后再比较。一: THashKeyValue = array [0..3] of Cardinal;
TKeyValuePair = record Next: PKeyValuePair;
//Key: AnsiString;
// 去掉key,使用下列数据类型 hashKey: THashKeyValue;
value: Integer;
end;
二:然后在Add时:function GetHashKeyValue(buf: PChar;
len: Integer): THashKeyValue;
begin
result[0] := hash1function(...);
result[1] := hash2function(...);
result[2] := hash3function(...);
result[3] := hash4function(...);
end;
procedure TAnsiStringHashList.Add(const Key: AnsiString;
const Value: integer);var ix: integer;
hash: THashKeyValue;
Bucket: PKeyValuePair;
begin
hash := GetHashKeyValue(PChar(Key), Length(Key));
ix := hash[0] mod Cardinal(BucketSize);
New(Bucket);
Lock;
try Bucket^.hashKey := hash;
Bucket^.Value := Value;
Bucket^.Next := Buckets[Hash];
Buckets[Hash] := Bucket;
Inc(FCount);
finally Unlock;
end;
end;
三:在Find函数中,使用THashKeyValue类型进行比较,而不是Key: string的字符串的比较为啥用N个hash键值比较,就是因为如果一个字串/内容,如果N次hash都是一样,则认为该内容是一样的,N越大,冲突的机率越小,一般弄到三个基本不会重复,这个看具体情况或场合。BTW:hash表,在Add的时候,应该作一次Find操作,检查现有的hashlist是否存在该key,如存在,则Result = -1,表示已存在。当然,也不算BUG,但对于写hash表的处理而言,要的就是Add一个唯一索引值的效果,如不需要,也无所谓。
 
Q

QQ在线

Unregistered / Unconfirmed
GUEST, unregistred user!
有了这个基础后,那么每次去比较的操作就是THashKeyValue: array [0..X] of Cardinal的比较。我相信:这个比较时间,基本可以忽略。当Add时,就将计算出来的hashKey保存起来,这样,下次Add/Find的时候,只是计算了一次SrcKey的hash值,而不是将已存在的hash列表所有的键盘都计算一次。其实这个也算不上什么大问题,只在hash的广度合适,它的深度不高,基本不会出慢的情况。之前我刚开始测试hash表的情况,也是直接用string = string进行检测,后来发现深度在X时,速度就慢下来了,add,10W条记录就要2-3s,后来才发现这问题的。才找了N多资料,后来google了到一篇文章(具体叫啥忘了,只记得关键字:暴雪,hash,冲突,一而再,再而三的机率基本是XXX。。。忘了),才用起这方法来了。其实N=2已经够用了。呵呵。
 

小雨哥

Unregistered / Unconfirmed
GUEST, unregistred user!
噢,明白你的意思了。N=2 通常是够用了,=4 更保险、心理感觉会好些。在建立Hash表的时候就执行这些操作,是一个不错的思路,但里面涉及到一些具体的应用场合,比如重复键是否在数据源存在、重复键取舍原则等等。一般Hash应用环境里,通常是首先调试Hash函数,该函数本身,要求在常量时间内完成应用环境下的哈希生成,然后调试深度广度比,这个调整与哈希函数本身的离散均匀度也有关系。所以,我觉得即使在Add时处理重复键(直接返回或者用新值替换),本身也应该是在常量时间内完成,而不应该明显变慢,因为我觉得这个是由Hash这个架构特色决定并保证的呀。
 

小雨哥

Unregistered / Unconfirmed
GUEST, unregistred user!
最后介绍一下 TAnsiStringHashList 类中 Assign 和 AssignTo 方法里的二个思路。当发生 Assign (AssignTo)行为的时候,我们会判断 Assign 的目标,在发现实际上是二个 TAnsiStringHashList 需要进行分派数据时,针对 Hash 实际的工作价值,Assign 可以有二个行为:1)将源Hash表里的数据,完整地复制到目标Hash表里。这个就是我上面代码中贴出的情况。通过这样的完整复制,二个Hash表完全独立,可以各自做自己希望的操作。缺点是复制需要时间,尤其Hash表通常用在极大数量检索上,这种复制产生的复制时间是非常巨大的,内存耗费也是非常巨大的。但是,Hash表通常是用来干什么的?最常用的是用来快速Key/Value检索。基于Hash这种特殊的工作目的,真的有必要完整地复制数据吗?这个我就不知道了,也许会有人需要这种复制。但是更多时候我们可能仅仅是需要另开一个线程来协助检索。这种情况下,完全可以做到让数据共享。这就是下面的二:2)源和目标数据共享。方法很简单,由于Hash表的 Buckets 是一个最大为 BucketSize 的数组,那么我们只要利用 Move 函数,将这个数组里的数据挪到新的数组里就可以了。这种 Move 操作可以瞬间完成,内存的占用也只有一个 Buckts 数组,与思路一里花费巨大内存的情况完全不同。完成以后,新生成的 Hash 表就可以协助对原有数据进行检索了。这是非常高效的。 if Source is TAnsiStringHashList then
begin
Self.FUseLock := TAnsiStringHashList(Source).FUseLock;
TAnsiStringHashList(Source).Lock;
Self.Lock;
try Self.BucketSize := TAnsiStringHashList(Source).BucketSize;
SetLength(Self.Buckets, Self.BucketSize);
Move(TAnsiStringHashList(Source).Buckets, Self.Buckets, Self.BucketSize);
Self.FCount :=TAnsiStringHashList(Source).FCount;
finally Self.Unlock;
TAnsiStringHashList(Source).Unlock;
end;
end;
但是请注意了,这样一来,二个实例的任何一个都不能执行 Clear 动作了,因为数据是共享的,任何一方执行 Clear ,另一方也再也拿不到数据了,甚至按照目前我帖子里的写法,二个实例的任何一个都不能释放,因为任何一个释放,一定会在 Destroy 方法里调用 Clear ....... 汗....吧滴、吧滴、吧滴...也许需要一个引用计数....
 
J

jake502010

Unregistered / Unconfirmed
GUEST, unregistred user!
留个名吧,地质那小子在哪抄的诗呀!感谢谢小雨哥,加油,DELPHI是无所不能的!建义开个专栏,DELPHI无所不能,把其他语言实现的功能,在DELPHI中写出更美的代码!
 
M

msfm

Unregistered / Unconfirmed
GUEST, unregistred user!
加入混战 呵呵 d2010 那个高手帮我改改这个function MyProcedure(a,b:string):boolean;asmpushad cmp eax,0 je @@exit cmp edx,0 je @@exit mov ecx,eax-4 cmp ecx,edx-4 jne @@exit mov esi,eax mov edi,edx cld rep cmpsw je @@ok @@exit: mov result,false jmp @@leave @@ok: mov result,true @@leave: popadend;
procedure TForm1.FormCreate(Sender: TObject);var a,b:string;
begin
a:='ab草D';
b:='ab草D';
if myprocedure(a,b) then
caption:='ok' else
caption:='no'end;
 

白河愁

Unregistered / Unconfirmed
GUEST, unregistred user!
rep cmpsw有这个,必慢!
 

小雨哥

Unregistered / Unconfirmed
GUEST, unregistred user!
楼上的楼上,呵呵,考试么?我将你的代码写清楚些,函数名也改得正式一些,注释也补上,写在下面,看看可以得几分:function WideStringCompare(a, b: WideString):Boolean;{$IFDEF PUREPASCAL}var i:integer;
pa,pb:pWORD;
// 或许写成 pa,pb:pWideChar 更贴切begin
Result := false;
if (Length(a) <> length(b)) or (Length(a) = 0) then
else
begin
pa := @a[1];
pb := @b[1];
i := length(a);
while pa^ = pb^do
begin
inc(pa);inc(pb);dec(i, 2);
if i < 1 then
begin
Result :=True;
break;
end;
end;
end;
end;
{$else
}asm pushad cmp eax,0 // a = '' je @@exit // goto @@exit cmp edx,0 // b ='' je @@exit // goto @@exit mov ecx,eax-4 // length(a) -> ecx cmp ecx,edx-4 // ecx - length(b) <> 0 jne @@exit // goto @@exit mov esi,eax // p1 = @a[1] mov edi,edx // p2 = @b[1] cld // dir + rep cmpsw // loop stepsize = 2, ++p1, ++p2, p1^ - p2^ je @@ok // = 0 goto @@ok@@exit: mov result,false // Result = 0 jmp @@leave@@ok: mov result,true // Result = 1@@leave: popadend;
{$ENDIF}不过这个 asm 写成的函数,依我估计,肯定比我上面用 JB_AND_SB 写成的函数慢。
 

小雨哥

Unregistered / Unconfirmed
GUEST, unregistred user!
呵呵,不是“强烈的自信”,是“百分百的事实”!假如你真的仔细参与了上面讨论,应该已经看到:JB_AND_SB 函数当中的循环步长是 Longword,就是说,每循环一次跨出 4 步,而你贴的 asm 代码的循环步长是 word,也就是每次循环跨 2 步!你说是一次跨 2 步快呢?还是一次跨 4 步快?从你的回复看,你的回答可能会让我们很吃惊的。因此,我在前面帖子里贴出了做 999 万次循环测试的结果,由于是高级语言代码,确实在有一倍跨步优势的情况下,针对 asm 仅有很微小的进步。但,毕竟是进步。
 

小雨哥

Unregistered / Unconfirmed
GUEST, unregistred user!
汗啊,确实 JB 函数输掉了。asm 的测试函数改写成这个帖子规定要求的测试函数格式如下:procedure asmCompare(s1, s2 :WideString;
var lresult: Boolean);asm pushad cmp eax,0 // a = '' je @@fail // goto @@fail cmp edx,0 // b ='' je @@fail // goto @@fail mov ecx,eax-4 // length(a) -> ecx cmp ecx,edx-4 // ecx - length(b) <> 0 jne @@fail // goto @@fail mov esi,eax // p1 = @a[1] mov edi,edx // p2 = @b[1] cld // dir + rep cmpsw // loop step size = 2, ++p1, ++p2, p1^ - p2^ je @@succ // = 0 goto @@succ@@fail: popad mov [ecx],0 // lresult = false jmp @@exit@@succ: popad mov [ecx],1 // lresult = true@@exit:end;
实测结果,很快!Time Elapsed Testeach Compare loop 99999each Effect loop 100Result := (SUM(100)(for each Compare TimeElapsed)) / 100-------------------------------------1) General Compare: 41-------------------------------------2) JB_AND_SB Compare: 41-------------------------------------3) Memory Compare: 43-------------------------------------4) asm Compare: 16 <-------- 就是这个,字符串比较用它吧-------------------------------------
 
M

msfm

Unregistered / Unconfirmed
GUEST, unregistred user!
hash 单元 晚上认真学习 画画指针流程图 害的我又下了 一遍 PASCAL数据结构(清华大学那本)
 
M

msfm

Unregistered / Unconfirmed
GUEST, unregistred user!
小雨 果然是难得的奇才啊 批准你进入 艾博龙 公司 编写DELPHI
 

Similar threads

I
回复
0
查看
692
import
I
I
回复
0
查看
589
import
I
I
回复
0
查看
500
import
I
I
回复
0
查看
479
import
I
顶部