[简单研究] 大数据检索:哈希表与字典 1


[1] Key检索与Value检索

问题:假设有a,b两个文本,每行一个数据,都有近1000W行,请导出a,b数据的交集.

这个问题用哈希表/字典只要几十秒就解决了,如果用数组,只怕要到海枯石烂.

虽然我们知道要用哈希表/字典来解决问题,那将数据保存为Key还是Value?



如果保存为Key,就调用ContainsKey()方法来检索,这是哈希表/字典的效率.


如果保存为Value,就调用ContainsValue()方法来检索,它是数组的效率.

所以用哈希表/字典保存数据,数据保存的位置还是很有讲究的.

[2] 哈希表与字典的效率之差

哈希表的定义如下:

$hash=@{} 

字典的定义如下,注意TKey指的是Key的数据类型,TVal是Value的数据类型.

字典定义的数据类型要与保存的数据一致.

$dic=New-Object 'System.Collections.Generic.Dictionary[TKey,TVal]'

看下面一段代码:


#哈希表测试
Measure-Command{
    $hash=@{}
    foreach($i in 1..30000000)
    {
        $hash.Add($i,$i)
    }
    foreach($i in 1..30000000)
    {
        [void] $hash.ContainsKey($i)
    }
}

#字典测试
Measure-Command{
    $dic=New-Object 'System.Collections.Generic.Dictionary[int,int]'
    foreach($i in 1..30000000)
    {
        $dic.Add($i,$i)
    }
    foreach($i in 1..30000000)
    {
        [void] $dic.ContainsKey($i)
    }
}
pause

运行结果:

Days              : 0
Hours             : 0
Minutes           : 1
Seconds           : 13
Milliseconds      : 318
Ticks             : 733182244
TotalDays         : 0.000848590560185185
TotalHours        : 0.0203661734444444
TotalMinutes      : 1.22197040666667
TotalSeconds      : 73.3182244
TotalMilliseconds : 73318.2244

Days              : 0
Hours             : 0
Minutes           : 1
Seconds           : 1
Milliseconds      : 530
Ticks             : 615306849
TotalDays         : 0.000712160704861111
TotalHours        : 0.0170918569166667
TotalMinutes      : 1.025511415
TotalSeconds      : 61.5306849
TotalMilliseconds : 61530.6849

由此可以看出,字典的效率略胜一筹

×用微信扫描并分享
本文链接: https://www.pstips.net/hashtable-vs-dictionary.html
请尊重原作者和编辑的辛勤劳动,欢迎转载,并注明出处!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

一条评论 “[简单研究] 大数据检索:哈希表与字典