时间戳

首页 > 解决方案 > 填充非常大的哈希表 - 如何最有效地做到这一点？

performance - 填充非常大的哈希表 - 如何最有效地做到这一点？

问题描述

背景/上下文：

我必须交叉检查/比较多个数据集（它们往往相互不一致），以识别“数据集 A 中的项目 X 匹配数据集 B 中的项目 Y 或 Z”。

涉及的那些数据集有些大（10 万条记录）并且涉及我戳 SQL 数据库。

经过一些初步的研究和性能测试，我已经从解析“海量数组”转变为有效地使用“索引哈希表”来处理关键属性点。

挑战：

一旦你开始使用它们，使用 Hashtables 会非常快......但我的问题在于有效地构建它们。感觉就像我“快到了”，但不得不求助于（相对）缓慢的方法（50,000 条记录大约需要 300-400 秒）。

这是我现在尝试索引的基本数据的样子（我从 SQL 中获取了不同设备名称的列表以及它对所述设备有多少记录的计数）：

DEVICENAME      COUNTOF
==========      ========
DEVICE_1        1
DEVICE_2        1
DEVICE_3        2
....            ...
DEVICE_49999    3
DEVICE_50000    1

当前解决方案：

我目前正在通过循环遍历结果集（我从 SQL 作为结果集提取的数组）并为每个行项使用“.add”来构建我的哈希表。

所以只是一个简单的...

for ($i=0; $i -lt @($SQL_Results).CountOf; $i++) {
    $MyIndexHash.Add( @($SQL_Results[$i]).DeviceName,  @($SQL_Results[$i]).CountOf)
}

相对而言，这“有点慢”（上述构建 50,000 个订单项需要 300-400 秒）。如果需要，我可以等待，但是由于（预感）我尝试了以下“近乎即时”的操作，因此它嘲笑可能有更好的方法来做到这一点（大约需要 3 秒）。

$MyIndexHash.Keys = $SQL_Results.DEVICENAME

但是 - 这仅填充了哈希表的 KEYS，而不是关联的值。而且我还没有找到有效实现以下目标的方法（将数组中的值直接大量分配到哈希表中）：

$MyIndexHash.Keys = ($SQL_Results.DEVICENAME, $SQL_Results.COUNTOF)

这是一个“纯粹的性能”问题——因为我需要做的其他一些比较将是 80,000 和 150,000 行项目。如果我必须“等待”通过循环遍历我的 SQL 结果数组的每一行来构造哈希表，那就这样吧。

注意- 我看过 - Powershell 2 和 .NET：针对超大哈希表进行优化？- 但由于我有可变的（嗯 - “未知但可能很大”）数据集来处理我不确定我可以/想要开始分解哈希表。

此外，哈希表中的查找（一旦填充）毕竟是超快的......这只是我希望可以以某种更有效的方式完成的哈希表的构造？

欢迎任何关于如何更有效地改进构建哈希表的建议。

谢谢！

更新/调查

根据@Pawel_Dyl 对哈希表分配应该有多快的评论，我对我的代码的变体和更大的（200k 行项目）数据值集进行了一些调查。

以下是测试结果和持续时间：

#Create the Demo Data... 200k lines
$Src = 1..200000 | % { [pscustomobject]@{Name="Item_$_"; CountOf=$_} }

# Test # 1 - Checking (... -lt $Src.Count) option vs (... -lt @($Src)Count ) ...
# Test 1A - using $Src.CountOf
$timer = [System.Diagnostics.Stopwatch]::StartNew()
$hash1A = @{}
foreach ($i in $Src) { $hash1A[$i.Name] = $i.CountOf }
$Timer.Stop()
$Timer.ElapsedMilliseconds
# Duration = 736 ms

# Now with @()
$timer = [System.Diagnostics.Stopwatch]::StartNew()
$hash1B = @{}
foreach ($i in @($Src)) { $hash1B[$i.Name] = $i.CountOf }
$Timer.Stop()
$Timer.ElapsedMilliseconds
# Duration = 728 ms

##################

# Test # 2 - Checking (... -lt $Src.Count) option vs (... -lt @($Src).Count ) ...

$timer = [System.Diagnostics.Stopwatch]::StartNew()
$hash2A = @{}
for ($i=0; $i -lt @($Src).Count; $i++) {
    $hash2A.Add(@($Src[$i]).Name, @($Src[$i]).CountOf)
}
$Timer.Stop()
$Timer.ElapsedMilliseconds
# Duration == 4,625,755 (!) (commas added for easier readability!

$timer = [System.Diagnostics.Stopwatch]::StartNew()
$hash2B = @{}
for ($i=0; $i -lt $Src.Count; $i++) {
    $hash2B.Add( $Src[$i].Name, $Src[$i].CountOf )
}
$Timer.Stop()
$Timer.ElapsedMilliseconds
# Duration == 1788 ms

所以问题是通过使用@()-s 来引用循环中的数组。旨在防止来自 SQL 的单行数组/结果（由于某种奇怪的原因，Powershell 没有作为一个概念，而是将其视为 DATAOBJECT 而不是数组完全不同（因此 .Count 之类的东西不可用无需强制 POSH 通过 @() 将其作为数组处理）。

所以“现在”的解决方案是添加一个简单的... If (@($MyArray).Count -eq 1) {Do stuff with @() } ElseIf (@($MyArray).Count -gt 1) {在不使用 @()-s 的情况下做事}

这就是我们的罪魁祸首——在循环中使用@()-s 花费了将近 1.25 小时，而相同的操作大约需要 1 秒。

改变这一点已经大大加快了速度（到只需要 0.1 秒来构建每个哈希表，即使“愤怒”处理了 90,000 多个对象。代码稍微不方便，但是哦，我仍然不明白为什么Powershell 对“1 行数组”的概念有疑问，并决定以不同的方式处理这些/作为单独的数据类型，但你去吧。

我仍然会查看 DataReader 的建议，看看我在哪里/如何最好地在代码中使用它们作为未来的改进。非常感谢所有的建议和很好的解释，让一切都变得有意义！

标签： performancepowershellhashtable

解决方案

注意：我强烈建议您不要将Count其用作输出列的名称，因为这会与 PowerShell 中的默认属性发生冲突。示例：@().Count返回0. 您的代码可能有效，但非常模棱两可。DeviceCount强烈建议将您的查询更改为使用或类似。

关于在 PowerShell 中获得此功能的最快速度，您可以使用 SqlDataReader 执行所有操作并直接循环输出。假设您的数据源是 SQL Server：

$ConnectionString = 'Data Source={0};Initial Catalog={1};Integrated Security=True' -f $SqlServer, $Database
$SqlConnection = [System.Data.SqlClient.SqlConnection]::new($ConnectionString)
$SqlCommand = [System.Data.SqlClient.SqlCommand]::new($SqlQuery, $SqlConnection)

$Data = @{}
$SqlConnection.Open()
try {
    $DataReader = $SqlCommand.ExecuteReader()
    while ($DataReader.Read()) {
        $Data[$DataReader.GetString(0)] = $DataReader.GetInt32(1)
    }
}
finally {
    $SqlConnection.Close()
    $SqlConnection.Dispose()
}

在我的系统上，我可以在大约 700 毫秒内获取和处理 160,000 条记录（请记住，我没有使用聚合函数）。

使用$Data.Add($DataReader.GetString(0), $DataReader.GetInt32(1))语法代替$Data[$DataReader.GetString(0)] = $DataReader.GetInt32(1)对我来说慢了大约 20%。但是，这种方法确实有一个重要的警告。 $HashTable.Add($Key, $Value)将在重复键上引发错误。 $HashTable[$Key] = $Value只会默默地替换值。确保您的 SQL 查询正确且不会返回重复值

您也可以使用$DataReader['DeviceName']而不是$DataReader.GetString(0)，但这意味着 SqlDataReader 必须进行查找，所以它会稍微慢一些（大约 10%）。使用 GetX() 方法的缺点是 a) 参数0和1引用列顺序，因此您必须知道输出的列顺序（通常不是什么大问题）和 b) 您必须知道数据类型输出（通常也没什么大不了的）。

在第一次运行时，我没有看到使用 Dictionary 而不是 HashTable 的显着性能差异，但在第一次运行之后，使用 Dictionary 的速度大约快 20%。也就是说，跑冷我看不出有什么区别。运行热我看到字典运行得更快。你不妨测试一下。如果是这样，而不是使用$Data = @{}，使用这个：

$InitialSize = 51000 # The more accurate this guess is without going under, the better
$Data = [System.Collections.Generic.Dictionary[String,Int32]]::new($InitialSize)

为了进一步参考，如果您需要对 SQL 结果集进行更快的查找，其中您的查找确实具有重复的查找值，通常使用 DataView 最快，它在排序时确实使用索引进行搜索：

$ConnectionString = 'Data Source={0};Initial Catalog={1};Integrated Security=True' -f $SqlServer, $Database
$SqlConnection = [System.Data.SqlClient.SqlConnection]::new($ConnectionString)
$SqlCommand = [System.Data.SqlClient.SqlCommand]::new($SqlQuery, $SqlConnection)

$DataTable = [System.Data.DataTable]::new()
$SqlConnection.Open()
try {
    $DataReader = $SqlCommand.ExecuteReader()
    $DataTable.Load($DataReader)
}
finally {
    $SqlConnection.Close()
    $SqlConnection.Dispose()
}

$DataView = [System.Data.DataView]::new($DataTable)
$DataView.Sort = 'DeviceName' # Create an index used for Find() and FindRows()
$DataView.Find('DEVICE_1') # -1 means not found, otherwise it's the index of the row
$DataView.FindRows('DEVICE_1')

您可以使用 DataAdapter 或 DataSet；我刚刚选择在这里只使用一个 DataTable，因为我有已经这样做的代码。

推荐阅读