Powershell 2和.net:针对超大型哈希表进行优化

Question

我刚刚接触过Powershell，对。net还是个新手。

我正在运行一个PS脚本，以一个空哈希表开始。哈希表将增长到至少15,000到20,000个条目。哈希表的键将是字符串形式的电子邮件地址，值将是布尔值。(我只需要跟踪我是否看到过一个电子邮件地址。)

到目前为止，我一直在一次增长一个哈希表项。我检查以确保键值对不存在(PS在这种情况下会出错)，然后添加对。

这是我们正在讨论的代码部分:

...
    if ($ALL_AD_CONTACTS[$emailString] -ne $true) {
      $ALL_AD_CONTACTS += @{$emailString = $true}
    }
...

我想知道从PowerShell或。net的角度来看，如果你提前知道这个哈希表将是巨大的，比如15,000到20,000个条目或更多，是否可以做些什么来优化这个哈希表的性能。

谢谢!

Answer 1

我使用Measure-Command进行了一些基本测试，使用了一组20 000个随机单词。

单独的结果如下所示，但总的来说，通过首先分配一个具有单个条目的新哈希表来添加一个哈希表似乎是非常低效的:)尽管在选项2到5之间有一些小的效率提高，但总的来说它们都执行得差不多。

如果让我选择，我可能会倾向于选项5，因为它很简单(每个字符串只有一个Add调用)，但是我测试的所有替代方案似乎都是可行的。

$chars = [char[]]('a'[0]..'z'[0])
$words = 1..20KB | foreach {
  $count = Get-Random -Minimum 15 -Maximum 35
  -join (Get-Random $chars -Count $count)
}
# 1) Original, adding to hashtable with "+=".
#     TotalSeconds: ~800
Measure-Command {
  $h = @{}
  $words | foreach { if( $h[$_] -ne $true ) { $h += @{ $_ = $true } } }
}
# 2) Using sharding among sixteen hashtables.
#     TotalSeconds: ~3
Measure-Command {
  [hashtable[]]$hs = 1..16 | foreach { @{} }
  $words | foreach {
    $h = $hs[$_.GetHashCode() % 16]
    if( -not $h.ContainsKey( $_ ) ) { $h.Add( $_, $null ) }
  }
}
# 3) Using ContainsKey and Add on a single hashtable.
#     TotalSeconds: ~3
Measure-Command {
  $h = @{}
  $words | foreach { if( -not $h.ContainsKey( $_ ) ) { $h.Add( $_, $null ) } }
}
# 4) Using ContainsKey and Add on a hashtable constructed with capacity.
#     TotalSeconds: ~3
Measure-Command {
  $h = New-Object Collections.Hashtable( 21KB )
  $words | foreach { if( -not $h.ContainsKey( $_ ) ) { $h.Add( $_, $null ) } }
}
# 5) Using HashSet<string> and Add.
#     TotalSeconds: ~3
Measure-Command {
  $h = New-Object Collections.Generic.HashSet[string]
  $words | foreach { $null = $h.Add( $_ ) }
}

Answer 2

几个星期后，我还没能想出一个完美的解决方案。谷歌的一个朋友建议把哈希分解成几个更小的哈希。他建议，每次我去查找一个键，在我找到正确的"桶"之前，我都会有几次失误，但他说，当碰撞算法运行到(已经很大的)哈希表中插入条目时，读惩罚不会像写惩罚那么糟糕。

我接受了这个想法，并将其进一步发展。我把哈希分成16个小桶。当将电子邮件地址作为键插入到数据结构中时，我实际上首先计算电子邮件地址本身的哈希值，并执行mod 16操作以获得0到15之间的一致值。然后我使用这个计算值作为"桶"号。

所以我没有使用一个大哈希，而是有一个16个元素的数组，它的元素是电子邮件地址的哈希表。

在内存中构建包含20,000多个电子邮件地址的"主列表"的总速度，使用拆分的哈希表桶，现在大约快了1000%。(快10倍)。

访问哈希中的所有数据没有明显的速度延迟。这是目前为止我能想到的最好的解决方案。它有点难看，但性能的提高说明了一切。

Answer 3

您将花费大量CPU时间重新分配Hashtable中的内部'数组'。您是否尝试过。net构造函数的哈希表，需要一个容量?

$t = New-Object Hashtable 20000
...
if (!($t.ContainsKey($emailString))) { 
    $t.Add($emailString, $emailString) 
}

我的版本使用相同的$emailString作为键&值，没有。net将$true装箱到一个[object]作为占位符。在PowerShell 'if'条件下，非空字符串将计算为$true，因此您检查的其他代码不应该更改。你使用'+= @{…}在性能敏感的。net代码中是一个大忌。您可能只是通过使用'@{}'语法为每个电子邮件分配一个新的哈希表，这可能会浪费大量时间。

将非常大的集合分解为(相对较小)数量较小的集合的方法称为"分片"。您应该使用Hashtable构造函数，它接受一个容量，即使您按16分片。

另外，@Larold是对的，如果你不查找电子邮件地址，那么使用'New-Object ArrayList 20000'来创建一个预分配的列表。

此外，集合的增长是昂贵的(每次"增长"的1.5或2倍)。这样做的效果是，您应该能够通过一个数量级减少预分配的数量，并且如果每次"数据加载"集合调整一次或两次大小，您可能不会注意到。我敢打赌，前10-20代的"增长"需要时间。