Unclear Powershell performance issue

NOTE. This is the solution for Project Euler Issue 14 . If you still want to fix this problem yourself, then read no further.

The problem was to find a number below a million that, as the starting number for the Collatz sequence , produces the longest such sequence. My initial code was as follows:

$r = @{}

for($i = 1; $i -lt 1000000; $i++) {
    $n = 0
    $a = $i
    while ($a -gt 1) {
        if ($r[$a]) {
            $n += $r[$a]
            break
        }
        if ($a % 2 -eq 0) {
            $a /= 2
        } else {
            $a = $a * 3 + 1
        }
        $n++
    }
    $r[$i] = $n
}

$r.GetEnumerator() | sort Value | select -l 1 | %{$_.Key}

      

        
        
        
      

    

which tries to use a hash table as a cache for subsequences already encountered to save time. I was very surprised when the script had over eight minutes running time on my machine. Re-creating the same code in C #:

using System;
using System.Collections.Generic;

class Problem14
{
    public static void Main()
    {
        var ht = new Dictionary<long, int>();

        for (int i = 1; i < 1000000; i++)
        {
            int count = 0;
            long j = i;

            while (j > 1)
            {
                if (ht.ContainsKey(j))
                {
                    count += ht[j];
                    break;
                }
                if (j % 2 == 0)
                    j /= 2;
                else
                    j = 3 * j + 1;

                count++;
            }
            ht[i] = count;
        }

        KeyValuePair<long, int> max = new KeyValuePair<long, int>();
        foreach (var n in ht)
        {
            if (n.Value > max.Value)
                max = n;
        }
        Console.WriteLine(max.Key);
    }
}

      

        
        
        
      

    

had a running time of just over one second. I knew that speed was not the main focus in Powershell. It's an administration language, and for these tasks, the relationship of PS code to cmdlets is probably very different from what I'm doing here.

However, I don't know what exactly is causing the slowdown.

Suspecting a hash table, I replaced it with array caching. This resulted in a runtime of about 200ms in C # and about 32 minutes in Powershell. The code was as follows:

$r = ,0*1000000

for($i = 1; $i -lt 1000000; $i++) {
    $n = 0
    $a = $i
    while ($a -gt 1) {
        if ($r[$a]) {
            $n += $r[$a]
            break
        }
        if ($a % 2 -eq 0) {
            $a /= 2
        } else {
            $a = $a * 3 + 1
        }
        $n++
    }
    if ($i -lt 1000000) {
        $r[$i] = $n
    }
}

$max = 0
for($i=1; $i -lt 1000000; $i++) {
    if ($r[$i] > $r[$max]) {
        $max = $i
    }
}
$max

      

        
        
        
      

    

and

using System;

class Problem14
{
    public static void Main()
    {
        var cache = new int[1000000];

        for (int i = 1; i < 1000000; i++)
        {
            int count = 0;
            long j = i;

            while (j > 1)
            {
                if (j < 1000000 && cache[j] != 0)
                {
                    count += cache[j];
                    break;
                }
                if (j % 2 == 0)
                    j /= 2;
                else
                    j = 3 * j + 1;

                count++;
            }
            cache[i] = count;
        }

        var max = 0;
        for (int i = 1; i < cache.Length; i++)
        {
            if (cache[i] > cache[max])
                max = i;
        }

        Console.WriteLine(max);
    }
}

      

        
        
        
      

    

Completely no caching in C # it was about 1.2 seconds. Haven't tried it in Powershell yet.

Any ideas?