1

I'm looking for a method to find an element in array which is fast and can be done by short code. I tried the following 4 codes; Code 1 is straightforward and fastest. Code 2 and Code 3 are compact but slower. Code 4 is slowest because the array is entirely iterated.

From the perspective of performance Code 1 is the best but looks ugly. Is there any short code like Code 2 or Code 3 and fast like Code 1?

Code

$list = 0..99

# Code 1
Write-Host "Code 1:" (Measure-Command {
  $list | % {
    $target = $_
    $found = $null
    foreach ($elem in $list) {
      if ($elem -eq $target) {
        $found = $target
        break
      }
    }
  }
}).TotalSeconds

# Code 2
Write-Host "Code 2:" (Measure-Command {
  $list | % {
    $target = $_
    $found = [Array]::Find($list, [Predicate[Int]]{ $args[0] -eq $target })
  }
}).TotalSeconds

# Code 3
Write-Host "Code 3:" (Measure-Command {
  $list | % {
    $target = $_
    $found = [System.Linq.Enumerable]::First($list, [Func[object,bool]]{ param($x) $x -eq $target })
  }
}).TotalSeconds

# Code 4
Write-Host "Code 4:" (Measure-Command {
  $list | % {
    $target = $_
    $found = $null
    $founds = @($list | ? { $_ -eq $target })
    if ($founds.Count -gt 0) {
      $found = $founds[0]
    }
  }
}).TotalSeconds

Output

Code 1: 0.0595818
Code 2: 0.1851123
Code 3: 0.1719588
Code 4: 0.3455028

REPL

Available on labstack

FYI

In JavaScript I always use Code B than Code A as it's shorter and performs better. This is what I want to do in PowerShell.

Code

const list = Array.from(Array(100)).map((_, i) => i);

// Code A
console.time("Code A");
list.forEach(target => {
  let found = undefined;
  for (const elem of list) {
    if (elem === target) {
      found = elem;
      break;
    }
  }
});
console.timeEnd("Code A");

// Code 2
console.time("Code B");
list.forEach(target => {
  const found = list.find(elem => elem === target);
});
console.timeEnd("Code B");

Output

Code A: 0.539ms
Code B: 0.215ms

REPL

Available on labstack

Takuya HARA
  • 499
  • 1
  • 3
  • 17
  • 1
    There are certain operators in PowerShell that will do what you just did for you. `-Contains`, and `-in`, and in terms of speed, `-in` is slightly faster as it doesn't search any further than the first match found. `$List.Foreach{ if ($_ -in $List) { Break } }`. – Abraham Zinala Sep 26 '21 at 21:21
  • On sorted lists like in your example, try the [Array.BinarySearch](https://learn.microsoft.com/en-us/dotnet/api/system.array.binarysearch) method. Also, all your code examples use `$list | %`, but it should be faster using `foreach ($item in $list)` then piping to `ForEach-Object` – Theo Sep 26 '21 at 21:28
  • @AbrahamZinala Your code just checks if the target exists in array but I want to find; returns found element if exists or returns null if it doesn't exist. – Takuya HARA Sep 26 '21 at 21:30
  • @Theo In my actual use case list is not sorted, but I didn't know about what you mentioned. Thank you. – Takuya HARA Sep 26 '21 at 21:32
  • 1
    Good tip, @AbrahamZinala, but note that `-contains` too stops after the first match: the only difference between `-in` and `-contains` is the order of operands. – mklement0 Sep 26 '21 at 21:41
  • @TakuyaHARA, if you search by element _value_, there's no reason to _return_ that value, if found - you already know it to begin with, so `$_ -in $list` seems sufficient; it would be different if you needed to know the _index_ of the value in the array, which `[Array]::IndexOf()` would give you, albeit invariably with case-_sensitive_ matching. For case-_insensitive_ matching, you'd need `[Array]::FindIndex()`, but that again requires use of a _script block_, which makes it slow. – mklement0 Sep 26 '21 at 21:48
  • I would make a hashtable. – js2010 Sep 26 '21 at 23:08
  • I really don't understand what you're trying to benchmark here - testing if every single item in a list is... in the list... you could replace the whole script with just `$list` or `$true` (depending on the end goal here). – Mathias R. Jessen Sep 27 '21 at 09:30

0 Answers0