从数组的属性获取唯一索引项的最快方法

Question

制作一个像这样的数组，它代表我正在寻找的内容：

$array = @(1..50000).foreach{[PSCustomObject]@{Index=$PSItem;Property1='Hello!';Property2=(Get-Random)}}

获取索引属性“43122”的项目的最快方法是什么？

我有一些想法，但我觉得必须有一种更快的方法：

管道在哪里

measure-command {$array | where-object index -eq 43122} | % totalmilliseconds
420.3766

哪里的方法

measure-command {$array.where{$_ -eq 43122}} | % totalmilliseconds
155.1342

首先制作一个哈希表并查询“索引”结果。起初很慢，但随后的查找速度会更快。

measure-command {$ht = @{};$array.foreach{$ht[$PSItem.index] = $psitem}} | % totalmilliseconds
124.0821

measure-command {$ht.43122} | % totalmilliseconds
3.4076

有没有比先构建哈希表更快的方法？也许是不同的 .NET 数组类型，例如某种特殊类型的索引列表，我可以最初将其存储在其中，然后运行一个方法来根据唯一属性提取项目？

Answer 1

部分归功于 PowerShell 能够调用.Net方法，它为过滤对象提供了一些安静的可能性。在 stackoverflow 上，您会发现很多（PowerShell）问题和答案，用于衡量特定提取命令或cmdlet的性能。这通常会留下错误的印象，因为完整的 (PowerShell) 解决方案的性能应该比其各部分的总和更好。每个命令都取决于预期的输入和输出。特别是在使用 PowerShell 管道时，命令 (cmdlet) 会与先前的命令和后续的命令交互。因此，重要的是要着眼于大局并了解每个命令如何以及在何处获得其性能。
这意味着我无法告诉您应该选择哪个命令，但是通过更好地理解下面列出的命令和概念，我希望您能够更好地为您的特定解决方案找到“最快的方法”。

[Linq.Enumerable]::Where

语言集成查询 (LINQ)通常被（取消）资格作为 PowerShell 中筛选对象的快速解决方案（另请参阅使用 LINQ 的高性能 PowerShell）：

(Measure-Command {
    $Result = [Linq.Enumerable]::Where($array, [Func[object,bool]] { param($Item); return $Item.Index -eq 43122 })
}).totalmilliseconds
4.0715

刚刚结束4ms！其他任何方法都无法打败它...
但是，在得出LINQ比任何其他方法高出 100 倍或更多的结论之前，您应该牢记以下几点。当您仅查看活动本身的性能时，在衡量 LINQ 查询的性能时存在两个陷阱：

• LINQ 有一个很大的缓存，这意味着您应该重新启动一个新的 PowerShell 会话来测量实际结果（或者如果您经常想要重用查询，则不重新启动）。重新启动PowerShell会话后，您会发现启动LINQ查询的时间大约延长了6倍。
• 但更重要的是，LINQ 执行惰性求值（也称为延迟执行）。这意味着除了定义应该做什么之外实际上还没有做任何事情。这实际上显示您是否想访问以下属性之一$Result：

(Measure-Command {
    $Result.Property1
}).totalmilliseconds
532.366

通常需要15ms检索单个对象的属性：

$Item = [PSCustomObject]@{Index=1; Property1='Hello!'; Property2=(Get-Random)}
(Measure-Command {
    $Item.Property1
}).totalmilliseconds
15.3708

最重要的是，您需要实例化结果以正确测量 LINQ 查询的性能（为此，我们只检索测量中返回对象的属性之一）：

(Measure-Command {
    $Result = ([Linq.Enumerable]::Where($array, [Func[object,bool]] { param($Item); return $Item.Index -eq 43122 })).Property1
}).totalmilliseconds
570.5087

（仍然很快。）

HashTable

哈希表通常很快，因为它们基于二分搜索算法，这意味着您最多必须猜测才能ln 50000 / ln 2 = 16 times找到您的对象。然而，为单个查找构建一个HashTabe有点过头了。但是，如果您控制对象列表的构造，则可以随时构造哈希表：

(Measure-Command {
    $ht = @{}
    $array = @(1..50000).foreach{$ht[$PSItem] = [PSCustomObject]@{Index=$PSItem;Property1='Hello!';Property2=(Get-Random)}}
    $ht.43122
}).totalmilliseconds
3415.1196

对比：

(Measure-Command {
    $array = @(1..50000).foreach{[PSCustomObject]@{Index=$PSItem;Property1='Hello!';Property2=(Get-Random)}}
    $ht = @{}; $array.foreach{$ht[$PSItem.index] = $psitem}
    $ht.43122
}).totalmilliseconds
3969.6451

Where-Objectcmdlet与Where方法

正如您自己可能已经得出的结论，该Where方法的出现速度大约是Where-Objectcmdlet 的两倍：

Where-Objectcmdlet：

(Measure-Command {
    $Result = $Array | Where-Object index -eq 43122
}).totalmilliseconds
721.545

Where方法：

(Measure-Command {
    $Result = $Array.Where{$_ -eq 43122}
}).totalmilliseconds
319.0967

原因是该Where命令要求您将整个数组加载到内存中，而 cmdlet 实际上不需要这样做Where-Object。如果数据已经在内存中（例如，通过将其分配给变量$array = ...），这并不是什么大问题，但这实际上可能是一个缺点：除了它消耗内存之外，您必须等到所有对象都被接收之后才能进行操作。开始过滤...

不要低估 PowerShell cmdlet 的强大功能，尤其Where-Object要关注与管道结合的整体解决方案。如上所示，如果您只测量特定操作，您可能会发现这些 cmdlet 速度很慢，但如果您测量整个端到端解决方案，您可能会发现没有太大区别，并且 cmdlet 甚至可能优于其他技术。LINQ 查询极其被动，而 PowerShell cmdlet 则极其主动。
一般来说，如果您的输入尚未在内存中并通过管道提供，您应该尝试继续在该管道上进行构建，并通过避免变量赋值( $array = ...)和使用括号 ( (...)) 来避免以任何方式停止它：

假设您的对象来自较慢的输入，在这种情况下，所有其他解决方案都需要等待最后一个对象才能开始过滤，其中已经Where-Object动态过滤了大多数对象，并且一旦找到它，不确定地传递给下一个 cmdlet...

例如，我们假设数据来自文件csv而不是内存......

$Array | Export-Csv .\Test.csv

Where-Objectcmdlet：

(Measure-Command {
    Import-Csv -Path .\Test.csv | Where-Object index -eq 43122 | Export-Csv -Path .\Result.csv
}).totalmilliseconds
717.8306

Where方法：

(Measure-Command {
    $Array = Import-Csv -Path .\Test.csv
    Export-Csv -Path .\Result.csv -InputObject $Array.Where{$_ -eq 43122}
}).totalmilliseconds
747.3657

这只是一个测试示例，但在大多数情况下，数据在内存中不能立即可用，Where-Object 流式传输似乎比使用Where 方法更快。
此外，该Where方法使用更多的内存，如果您的文件（对象列表）大小超过可用的物理内存，则性能可能会更差。（另请参阅：可以在 PowerShell 中简化以下嵌套 foreach 循环吗？）。

ForEach-Objectcmdlet vsForEach方法vsForEach命令

您可以考虑迭代所有对象并将它们与语句进行比较，而不是使用Where-Objectcmdlet 或方法 。在深入讨论这种方法之前，值得一提的是，比较运算符本身已经迭代了 left 参数，引用：WhereIf

当运算符的输入是标量值时，比较运算符返回布尔值。当输入是值的集合时，比较运算符返回任何匹配的值。如果集合中没有匹配项，比较运算符将返回一个空数组。

这意味着，如果您只想知道具有特定属性的对象是否存在，而不关心对象本身，您可能只需比较特定属性集合：

(Measure-Command {
    If ($Array.Index -eq 43122) {'Found object with the specific property value'}
}).totalmilliseconds
55.3483

对于ForEach-Objectcmdlet 和方法，您会发现该方法比使用其对应方法（ cmdlet 和方法）ForEach花费的时间稍长一些，因为嵌入式比较的开销稍多一些：Where-ObjectWhere

直接从内存中：
ForEach-Objectcmdlet：

(Measure-Command {
    $Result = $Array | ForEach-Object {If ($_.index -eq 43122) {$_}}
}).totalmilliseconds
1031.1599

ForEach方法：

(Measure-Command {
    $Result = $Array.ForEach{If ($_.index -eq 43122) {$_}}
}).totalmilliseconds
781.6769

从磁盘流式传输：
ForEach-Objectcmdlet：

(Measure-Command {
    Import-Csv -Path .\Test.csv |
    ForEach-Object {If ($_.index -eq 43122) {$_}} |
    Export-Csv -Path .\Result.csv
}).totalmilliseconds
1978.4703

ForEach方法：

(Measure-Command {
    $Array = Import-Csv -Path .\Test.csv
    Export-Csv -Path .\Result.csv -InputObject $Array.ForEach{If ($_.index -eq 43122) {$_}}
}).totalmilliseconds
1447.3628

ForEach但 即使使用嵌入比较，当内存中已可用时，该ForEach 命令看起来也接近使用该方法的性能：Where$Array

直接凭记忆：

(Measure-Command {
    $Result = $Null
    ForEach ($Item in $Array) {
        If ($Item.index -eq 43122) {$Result = $Item}
    }
}).totalmilliseconds
382.6731

从磁盘流式传输：

(Measure-Command {
    $Result = $Null
    $Array = Import-Csv -Path .\Test.csv
    ForEach ($Item in $Array) {
        If ($item.index -eq 43122) {$Result = $Item}
    }
    Export-Csv -Path .\Result.csv -InputObject $Result
}).totalmilliseconds
1078.3495

ForEach但是，如果您只查找一次（或第一次）出现，则使用该命令可能还有另一个优点：Break一旦找到该对象，您就可以退出循环，并且只需跳过数组迭代的其余部分即可。换句话说，如果该项目出现在最后，可能没有太大区别，但如果它出现在开头，您就有很多机会赢得。25000为了平衡这一点，我采用了搜索的平均索引 ( )：

(Measure-Command {
    $Result = $Null
    ForEach ($Item in $Array) {
        If ($item.index -eq 25000) {$Result = $Item; Break}
    }
}).totalmilliseconds
138.029

请注意，您不能使用cmdlet 和方法Break的语句，请参阅：如何从 PowerShell 中的 ForEach-Object 退出ForEach-ObjectForEach

爆发 _{（2023-05-23 添加）}

正如ili所评论的，虽然并非完全不可能使用带有参数的Select-Objectcmdlet来中断管道，但当处理了指定数量的管道项时，该参数实际上会中断管道，例如：-First

$Array | Where-Object index -eq 43122 | Select-Object -First 1

^{（另请参阅：在方法内使用 continue/return 语句.ForEach()- 是否更好使用foreach ($item in $collection)？）}

对于Where()具有可选参数的方法，该方法允许附加选择功能，限制从过滤器返回的项目数，例如：

$array.where({$_ -eq 43122}, 'First', 1)

结论

纯粹查看测试的命令并做出一些假设，例如：

• 输入不是瓶颈（$Array已经驻留在内存中）
• 输出不是瓶颈（$Result实际上没有使用）
• 您只需要出现一次（第一次）
• 在迭代之前、之后和之中没有其他事情可做

使用ForEach 命令并简单地比较每个索引属性直到找到对象，似乎是此问题的给定/假设边界中最快的方法，但如开头所述；要确定最适合您的使用案例的方法，您应该了解您在做什么并查看整个解决方案，而不仅仅是其中的一部分。

有关的：

• PowerShell 脚本性能注意事项
• 掌握（可步进）管道

Answer 2

我认为最快的方法是使用哈希表，并理所当然地认为构建它需要一些时间。另外，我会反转哈希表，以便您要查找的属性是键，索引的数组将是值。

请注意，虽然您的示例创建了一个起始索引为 1 的数组，但稍后在检索确切索引（从 0 开始）时需要考虑这一点。另请注意，通过使用(Get-Random)属性来搜索可能会留下重复值。对于演示来说，这很好，但请记住，在这样做时，找到的索引将是一系列重复项中的最后一个索引。

# create the demo array of objects
$startIndex = 0
$array = @($startIndex..50000).Foreach{[PSCustomObject]@{Index=$PSItem; Property1='Hello!'; Property2=(Get-Random)}}

# create the hashtable where Property2 is the key and the array index the value
Write-Host 'Create HashTable: ' -NoNewline
(Measure-Command { $ht = @{}; foreach ($i in $array) { $ht[$i.Property2] = ($i.Index - $startIndex) } }).TotalMilliseconds

# try and find the index. This will take longer if there was no Property2 with value 43122 
Write-Host 'Find array index: ' -NoNewline
(Measure-Command { $ht[43122] }).TotalMilliseconds

我的 Windows 7 机器（12 GB RAM，SSD 磁盘）上的输出：

Create HashTable: 250.3011
Find array index: 0.3865