arrays - powershell 比较运算符包含 vs 大数组

Question

想知道是否有机会提高数组搜索后的性能。此刻是16秒。

Measure-Command -Expression {

$a = @()
$b = @()
1..10000 | %{$a += $_}
1..10000 | %{$b += $_}

#Try to resize but still running 16 seconds
[array]::Resize([ref]$a,10000) 
[array]::Resize([ref]$b,10000)

foreach ($i in $a){
    if ($b -contains $i) {
        #write-host $i
    }
}

}

Answer 1

+=如果是数组 重新创建整个数组 :它将旧内容与新元素一起复制到新数组中。在 PowerShell 中填充大型数组可以说是最糟糕的方法。使用 +=仅当它是不在循环内的一次性操作，或者数组很小并且时间无关紧要时。

直接填充数组:

$a = 1..10000

或者收集 foreach 的输出直接声明:

$a = foreach ($i in 1..10000) { $i }

或者使用 ArrayList:

$a = [Collections.ArrayList]@()
foreach ($i in 1..10000) { $a.Add($i) >$null }

请注意，在这种特殊情况下，将现有数组转换为 ArrayList 会更快:

$a = [Collections.ArrayList]@(1..10000)

流水线是一项复杂的操作，它比 foreach 之类的流控制语句慢几倍/很多倍(语句，不是 cmdlet)，while , do .

与内部的简单代码相比，ScriptBlock({ } cmdlet 中花括号 ForEach 中的代码，别名为 % )需要花费大量时间为每个元素创建执行上下文。

-contains检查每个元素直到找到匹配项，因此最终迭代次数为 $a.count * $b.count在最坏的情况下或平均一半。

最有效的方法是建立一个查找表:

作为哈希表:

$a = 1..10000
$b = 1..10000

$bIndex = @{}
foreach ($i in $b) { $bIndex[$i] = $true }

foreach ($i in $a) {
    if ($bIndex[$i]) {
        #write-host $i
    }
}

15 milliseconds on i7 CPU

作为 HashSet(.NET 3.5 和更新版本，built-in since Win7，可在 XP 上安装):

$a = 1..10000
$b = 1..10000

$bIndex = [Collections.Generic.HashSet[int]]$b

foreach ($i in $a) {
    if ($bIndex.Contains($i)) {
        #write-host $i
    }
}

7 milliseconds on i7 CPU

使用 HashSet 将数组相交，然后迭代结果:

$a = 1..10000
$b = 1..10000

$inBoth = [Collections.Generic.HashSet[int]]$a
$inBoth.IntersectWith([Collections.Generic.HashSet[int]]$b)
foreach ($i in $inBoth) {
    #write-host $i
}

7 milliseconds on i7 CPU

如果数组的内容不同，即交集比数组小得多，它会快很多倍。

也可以建立一个真正的 index that contains a list of original item indices在数组中 - 在重复值的情况下很有用。