Algorithms

PowerShell is rarely the right tool for heavy algorithmic work, but the object pipeline does the equivalent of LINQ in one or two cmdlets. Sort-Object, Group-Object, Compare-Object, Select-Object -Unique, and Measure-Object cover the patterns operators run into most: sort, group, dedupe, diff, aggregate.

Search

Linear search over an array.

function Test-Contains {
    param([object]$Needle, [object[]]$Haystack)
    foreach ($x in $Haystack) {
        if ($x -eq $Needle) { return $true }
    }
    $false
}

$items = @('red', 'green', 'blue')
Test-Contains -Needle 'green' -Haystack $items

The pipeline version. -contains is the operator; -in is the inverse.

$items -contains 'green'                  # True
'green' -in $items                         # True

Filter to matches with Where-Object.

$items | Where-Object { $_ -like 'gr*' }

Membership at O(1) with a hashtable.

$set = @{}
foreach ($x in $items) { $set[$x] = $true }
$set.ContainsKey('green')

Sorting

Sort-Object covers the standard cases. Sort by property, multi-key sort, descending order, case-insensitive, unique.

$items | Sort-Object
$rows  | Sort-Object Length -Descending
$rows  | Sort-Object Region, Name           # multi-key
$rows  | Sort-Object -Unique Name

For numeric vs lexical sorting, pass an expression with the right type.

'10','2','33','4','5' | Sort-Object               # lexical: 10 2 33 4 5
'10','2','33','4','5' | Sort-Object { [int]$_ }   # numeric: 2 4 5 10 33

Grouping

Group-Object returns GroupInfo objects with Name (the key), Count, and Group (the underlying rows).

Get-Process |
    Group-Object Company |
    Sort-Object Count -Descending |
    Select-Object Name, Count

# group by computed key
$rows | Group-Object { $_.Email -split '@' | Select-Object -Last 1 }

Dedup

Three ways, in order of preference for the operator’s everyday work.

$items | Select-Object -Unique                          # in-pipeline
$items | Sort-Object -Unique                            # also sorts
[System.Collections.Generic.HashSet[string]]$items      # .NET, fastest

Diff

Compare-Object is PowerShell’s structured diff. Returns rows with SideIndicator: <= for reference-only, => for difference-only, == for shared (with -IncludeEqual).

Compare-Object (Get-Content a.txt) (Get-Content b.txt)

Compare-Object $before $after -Property Name |
    Where-Object SideIndicator -eq '=>'

Aggregate

Measure-Object sums, averages, counts, and finds min / max over a property.

Get-ChildItem -Recurse |
    Measure-Object Length -Sum -Average -Maximum -Minimum

$rows | Measure-Object Count -Sum

Recursion

function Get-Factorial {
    param([int]$N)
    if ($N -le 1) { return 1 }
    $N * (Get-Factorial -N ($N - 1))
}

Get-Factorial -N 5

120

PowerShell has no tail-call optimization. Deep recursion blows the stack; prefer iteration for anything above a few hundred frames.

References

• Structures for the arrays, hashtables, and PSCustomObject these algorithms operate on.

• I/O and Pipelines for the parallel pipeline (ForEach-Object -Parallel) when the work is independent.

• Get-Help Sort-Object, Get-Help Group-Object, Get-Help Compare-Object, Get-Help Measure-Object.