自定义Powershell排序功能

问题描述 投票：0回答：3

我有一个巨大的 1M+ 名字数组，有些是字母数字有些只是字母。

CSV:
id,firstname,lastname,email,email2,profession
100,Andeee,Michella,[email protected],[email protected],police officer
101,Tybie,1Grobe,[email protected],[email protected],worker
102,Fernande,Azeria,[email protected],[email protected],developer
103,Lenna,Schenck,[email protected],[email protected],police officer
104,4Marti,Brittani,[email protected],[email protected],worker
105,Riannon,Aldric,[email protected],[email protected],doctor
106,Corry,Nikaniki,[email protected],[email protected],worker
107,Correy,Shama,[email protected],[email protected],police officer
108,Marcy,Drus,[email protected],[email protected],worker
109,Bill,Valerio,[email protected],[email protected],worker

我不想对整个数组使用 Sort-Oject 或 Sort，因为它花费的时间太长了。由于我的环境限制，这需要在 Powershell 中完成。

数组来自我从另一个 powershell 作业导出的 csv。 （我无权访问工作代码，只能访问结果）。

这是我从我找到的 Java 方法创建的示例。它因以下错误而失败：

The script failed due to call depth overflow.

$array = @("Ryan", "Kelly", "Alex", "Kyle", "Riley")
mergeSort $array

write-host $array

function mergeSort
{

   param([string[]] $arr)

      if($arr.length -ge 2){
         
         #find mid-point
         $left_len = [math]::floor([int32]$arr.length/2)                                              
         
         #declare array size of left of mid-point
         $left = [string[]]::new($left_len);                                                                 

         #find mid-point
         $right_len = [math]::ceiling([int32]($arr.Length - $arr.Length /2))                
     
         #declare array size right of mid-point
         $right = [string[]]::new($right_len);                                                               

         for ($i = 0; $i -lt $left_len.Length; $i++){
            $left= $arr[$i]
         }#for loop

         for ($i = 0; $i -lt $right_len; $i++){
            $right = $arr[$i +$arr.Length/2]
         }
     }#if($arr.length -ge 2)

   mergeSort $left

   mergeSort $right

   merge ($arr, $left, $right)
}

function merge
{
    param ([string[]] $result,[string[]] $left, [string[]] $right)

    $i1 = 0

    $12 = 0

    for ($i = 0; $i -le $result.Length; $i++) {
      if($i2 -gt $right.Length -or ($i1 -lt $left.Length -and $left[$i1].CompareTo($right[$i2]) -lt 0)) {
         $result[$i] = $left[$i1]
          $i1++
       }
       else {
          $result[$i] = $right[$i2]
          $i2++
       }

   }

   $result.legnth

 }

这是我根据大家的建议提出的最新解决方案：我想并行执行此操作，但它会引发错误：

$array = @('Ryan', 'Kelly', 'Alex', 'Kyle', 'Riley', '4test', 'test4', 'why', 'you', 'me', 'where', 'hello', 'jose', 'test', 
'Jelly', 'Plex', 'Cyle', 'Miley', '5test', '3test4', 'who', 'Bou', 'We', 'There', 'Yellow', 'Pose', 'West')

$type = ("System.Collections.Generic.SortedSet"+'`'+"2") -as "Type"
$type = $type.MakeGenericType( @( ("System.string" -as "Type"), ("system.string" -as "Type") ) )
$sortedArray = [Activator]::CreateInstance($type, 10000)

$a, $b = ($array | Split-Collection -Count ([int]$array.length/2) | %{ $_ -join ',' })

$firstCollection = $a.Split(",")
$secondCollection = $b.Split(",")

$counter = 0
$counterHalf = $array.Length/2

1..$counterHalf| ForEach {
    try {   
        $col1 = $firstCollection[$counter]
        $sortedArray.Add($col1, $counter)
    }
    catch { "Out of bound col 1" }

    try {    
        $col2 = $secondCollection[$counter]
        $sortedArray.Add($col2, $counter)
    }
    catch { "Out of bound col 2" }
    
    $counter++
}

$sortedArray


function Split-Collection {
    [CmdletBinding()]
    param(
        [Parameter(ValueFromPipeline=$true)] $Collection,
        [Parameter(Mandatory=$true)][ValidateRange(1, 247483647)][int] $Count)
    begin {
        $Ctr = 0
        $Arrays = @()
        $TempArray = @()
    }
    process {
        if (++$Ctr -eq $Count) {
            $Ctr = 0
            $Arrays += , @($TempArray + $_)
            $TempArray = @()
            return
        }
        $TempArray += $_
    }
    end {
        if ($TempArray) { $Arrays += , $TempArray }
        $Arrays
    }
}
powershell sorting scripting mergesort sort-object
3个回答
3
投票

FWIW，这是关于让您的Merge Sort代码工作的原始问题的答案。不幸的是，它的性能不是很好，所以我不知道它是否真的能帮助你解决 100 万行以上的排序问题......

好消息

我对你原来的 

mergeSort
做了一些调整似乎修复了它，至少对于你问题顶部的示例数组是这样。

修复主要是拼写错误 - 请参阅 BeyondCompare 的屏幕截图以查看我所做的更改：

坏消息

太慢了

PS> $array = [string[]] (1..10000 | % { $_.ToString() }) 
PS> measure-command {
    mergeSort $array
}

...
TotalMilliseconds : 11511.74

相比于

PS> $array = [string[]] (1..10000 | % { $_.ToString() }) 
PS> measure-command {
    $array = $array | sort-object
}

...
TotalMilliseconds : 36.8607

也许它在你所说的数据规模下表现更好，但我没有耐心去测试它:-)

丑女

我还稍微调整了代码，以便在对右侧进行任何操作之前对左侧进行排序，这意味着它不需要使用那么多内存。

这是更新后的示例，供后代使用。

$ErrorActionPreference = "Stop";
Set-StrictMode -Version "Latest";

function mergeSort
{

    param([string[]] $arr)

    if( $arr.length -gt 1 )
    {

        # sort the left side
        $left_len = [Math]::Floor([int32]$arr.length / 2)
        $left = [string[]]::new($left_len);                                                                 
        for( $i = 0; $i -lt $left_len; $i++ )
        {
            $left[$i] = $arr[$i]
        }
        mergeSort -arr $left

        # sort the right side
        $right_len = $arr.Length - $left_len
        $right = [string[]]::new($right_len);
        for( $i = 0; $i -lt $right_len; $i++ )
        {
            $right[$i] = $arr[$left_len + $i]
        }
        mergeSort -arr $right

        # merge the two sides
        merge -result $arr -left $left -right $right

    }

}

function merge
{
    param ([string[]] $result,[string[]] $left, [string[]] $right)

    $i1 = 0
    $i2 = 0

    for ($i = 0; $i -lt $result.Length; $i++)
    {
        if( ($i1 -lt $left.Length) -and (($i2 -ge $right.Length) -or $left[$i1].CompareTo($right[$i2]) -lt 0) )
        {
            $result[$i] = $left[$i1]
            $i1++
        }
        else
        {
            $result[$i] = $right[$i2]
            $i2++
        }
    }

}

$array = [string[]] @("Ryan", "Kelly", "Alex", "Kyle", "Riley")
mergeSort $array

write-host $array

要特别指出的一件事是将输入数组转换为字符串：

$array = [string[]] @("Ryan", "Kelly", "Alex", "Kyle", "Riley")

没有转换，

$array
是 
[System.Object[]]
类型，PowerShell 将在内部创建一个新的 temporary 
[string[]]
数组，将值复制到其中，然后对内部数组进行排序，但它 不会 将内部数组分配回 
$array
.

在没有演员表的情况下尝试一下，看看效果如何。

1
投票

使用具有哈希键的排序字典

$filename = 'c:\temp\test.csv'
$dict = [System.Collections.Generic.SortedDictionary[string,string]]::new()

$reader = [System.IO.StreamReader]::new($filename)
#skip header
$reader.ReadLine()
while( ($line = $reader.ReadLine()) -ne $null )
{
   if($line.Length.Trim() > 0)
   {
      $firstComma = $line.IndexOf(',')
      $id = $line.Substring(0, $firstComma)
      $dict.Add($id, $line)
   }
}
$dict
0
投票

如果您确实遇到 PowerShell 的性能问题，您可以先阅读 PowerShell 脚本性能注意事项

自上而下的实施

关于您的第一次尝试，您可能想要避免的一件事是递归函数，因为在 PowerShell 中调用函数非常昂贵，请参阅：重用静态代码的最佳方法是什么
具体错误 The script failed due to call depth overflow 很可能是由于不正确的检查，你应该在哪里停止递归调用，因此永远持续下去......

自下而上的实施

关于您的第二次尝试，使用增加赋值运算符 (

+=
) 创建集合是一个安静的常见 PowerShell 性能问题，请参阅：Why should I avoid using the increase assignment operator (
+=
) to create a collection

合并排序原型

考虑到这两个问题，你可能会得出这样的函数：

function MergeSort($List, $By) {
    $Count = @($List).get_Count()
    if ($Count -le 1) { return $List }
    $Temp = $arr = New-Object PSCustomObject[] $Count
    $Middle = [math]::ceiling($Count / 2)
    for ($Width = 1; $Width -lt $Middle; $Width = 2 * $Width) {
        for ($Start = 0; $Start -lt $Count; $Start = $Start + 2 * $Width) {
            $Left = $Right = $To = 0
            do {
                if (
                  (
                    $Right -ge $Width -or $Start + $Right -ge $Count
                  ) -or (
                    $Left -lt $Width -and $Start + $Left -lt $Count -and 
                    $List[$Start + $Left].$By -lt $List[$Start + $Width +$Right].$By
                  )
                )    { $Temp[$Start + $To++] = $List[$Start + $Left++] }
                else { $Temp[$Start + $To++] = $List[$Start + $Width + $Right++] }
            } while ($To -lt 2 * $Width -and $Start + $To -lt $Count)
        }
        $List, $Temp = $Temp, $List # Swap (the references of) the lists
    }
    $List
}

演示

$Data = ConvertFrom-Csv @'
id,firstname,lastname,email,email2,profession
100,Andeee,Michella,[email protected],[email protected],police officer
101,Tybie,1Grobe,[email protected],[email protected],worker
102,Fernande,Azeria,[email protected],[email protected],developer
103,Lenna,Schenck,[email protected],[email protected],police officer
104,4Marti,Brittani,[email protected],[email protected],worker
105,Riannon,Aldric,[email protected],[email protected],doctor
106,Corry,Nikaniki,[email protected],[email protected],worker
107,Correy,Shama,[email protected],[email protected],police officer
108,Marcy,Drus,[email protected],[email protected],worker
109,Bill,Valerio,[email protected],[email protected],worker
'@

MergeSort $Data -by lastname |Format-Table

id  firstname lastname email                       email2                    profession
--  --------- -------- -----                       ------                    ----------
101 Tybie     1Grobe   [email protected]     [email protected]     worker
105 Riannon   Aldric   [email protected]  [email protected]  doctor
102 Fernande  Azeria   [email protected] [email protected] developer
104 4Marti    Brittani [email protected]  [email protected]  worker
100 Andeee    Michella [email protected] [email protected] police officer
106 Corry     Nikaniki [email protected]  [email protected]  worker
103 Lenna     Schenck  [email protected]   [email protected]   police officer
107 Correy    Shama    [email protected]    [email protected]    police officer

但是正如 @mclayton 有用的答案 中已经指出的那样，您不太可能使用自制的 PowerShell 函数击败原生的 Sort-Object。

SortedDictionary

无论如何，@jdweng有用的答案中提到的使用

SortedDictionary<TKey,TValue>
Class的建议是击败本地
Sort-Object
命令的更好选择。

$Dictionary = [System.Collections.Generic.SortedDictionary[string,object]]::new()
$Data.foreach{ $Dictionary[$_.lastname] = $_ }
$Dictionary.Values |Format-Table

基准

我质疑您关于SortedDictionary“解是线性”的评论，但我无法证明这一点。无论如何，我想最终这里的实际表现才是最重要的。

$Data = 1..10000 |Foreach-Object { [PSCustomObject]@{ Id = $_; Name = (New-Guid).Guid } }

(Measure-Command { 
    $Dictionary = [System.Collections.Generic.SortedDictionary[string,object]]::new()
    $Data.foreach{ $Dictionary[$_.Name] = $_ }
    $Null = $Dictionary.Values
}).TotalMilliseconds

(Measure-Command { 
    $Null = $Data |Sort-Object -Property Name
}).TotalMilliseconds


(Measure-Command { 
    $Null = MergeSort $Data -By Name
}).TotalMilliseconds

结果

SortedDictionary:    96.0831
Sort-Object:        120.8665
MergeSort Function: 570.1095
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.