Странная проблема производительности Powershell

Question

ПРИМЕЧАНИЕ: Это решение для Project Euler Задача 14 . Если вы все еще хотите решить это самостоятельно, не читайте дальше.

Проблема состояла в том, чтобы найти число ниже миллиона, которое в качестве начального числа для последовательности Коллатца дает самую длинную такую ​​последовательность. Мой начальный код был следующим:

$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}

, который пытается использовать хеш-таблицу в качестве кэша для уже встреченных подпоследовательностей, чтобы сэкономить время. Я был очень удивлен, когда на моем компьютере этот сценарий работал более восьми минут. Повторное создание того же кода в 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);
    }
}

имел время выполнения чуть более одной секунды. Я знал, что скорость исполнения не была главной целью в Powershell. Это язык администрирования, и для этих задач отношение кода PS к командлетам, вероятно, очень отличается от того, что я делаю здесь.

Тем не менее, я не знаю, что именно вызывает замедление.

Подозревая хеш-таблицу, я заменил ее для кеширования на массив. Это привело к времени выполнения около 200 мс в C # и около 32 минут в Powershell. Код был следующим:

$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

и

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);
    }
}

В C # вариант без кеша был примерно 1,2 секунды. Еще не пробовал в Powershell.

Есть идеи?

Answer 1

Прежде всего, PowerShell - это интерпретируемый язык (не скомпонованный и не скомпилированный). Это всегда будет больно. ; -)

Во-вторых, есть некоторые языковые конструкции, которые вы можете использовать, чтобы избежать нескольких интерпретируемых шагов. Например, вместо использования оператора for (;;) используйте диапазон:

0..1000000 | foreach-object { foo $_ 

Может немного помочь.

Самое главное, избегайте чрезмерного использования разрывов и продолжения ключевых слов в циклах - инвертируйте логику, если это возможно, чтобы избежать этого. Внутренне эти ключевые слова сигнализируют с использованием исключений .NET и поэтому являются дорогостоящими операциями.

Надеюсь, это поможет вам понять.

РЕДАКТИРОВАТЬ: эти ключевые слова используют исключения .NET для сигнализации

Из System.Management.Automation.FlowControlNode.Execute (...):

switch (this._tokenId)
    {
        case TokenId.ExitToken:
        {
            int exitCode = this.GetExitCode(result);
            throw new ExitException(base.NodeToken, exitCode);
        }
        case TokenId.ReturnToken:
            throw new ReturnException(base.NodeToken, result);

        case TokenId.BreakToken:
            label = this.GetLabel(result, context);
            throw new BreakException(base.NodeToken, label);

        case TokenId.ContinueToken:
            label = this.GetLabel(result, context);
            throw new ContinueException(base.NodeToken, label);

-Oisin