Problème de performance de Weird Powershell

Question

REMARQUE: Ceci est une solution pour Project Euler Problem 14. Si vous voulez toujours le résoudre vous-même, ne lisez pas.

Le problème était de trouver le nombre inférieur à un million qui, en tant que numéro de départ pour le Collatz sequence, produit la plus longue séquence de ce type. Mon code initial était comme suit:

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

qui tente d'utiliser une table de hachage comme cache pour les sous-séquences déjà rencontrées pour gagner du temps. J'ai été très surpris quand ce script a duré plus de huit minutes sur ma machine. Recréation du même code en 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); 
    } 
} 

avait une durée d'exécution d'un peu plus d'une seconde. Je savais que la vitesse d'exécution n'était pas un objectif primordial dans Powershell. C'est un langage d'administration et pour ces tâches, le rapport du code PS aux cmdlets est probablement très différent de ce que je fais ici.

encore, je ne sais pas ce qui cause exactement le ralentissement.

Soupçonnant la table de hachage, je l'ai remplacé pour la mise en cache avec un tableau. Cela s'est traduit par un temps d'exécution d'environ 200 ms en C# et d'environ 32 minutes en Powershell. Code était la suivante:

$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 

et

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

Une variante complètement cacheless était d'environ 1,2 secondes en C#. N'a pas encore essayé à Powershell.

Des idées?

Answer 1

Tout d'abord, PowerShell est un langage interprété (non jitted, ni compilé). Ça va toujours faire mal. ;-)

En second lieu, il y a un langage construit que vous pouvez utiliser qui permet d'éviter plusieurs étapes interprétées. Par exemple, au lieu d'utiliser une instruction for (;;), utilisez une plage:

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

Pourrait aider un peu.

Plus important encore, éviter l'utilisation excessive de break et continue des mots-clés dans les boucles - inverser votre logique, si possible, pour éviter cela. En interne, ces mots-clés signalent l'utilisation d'exceptions .NET et sont donc des opérations coûteuses.

Hope this helps votre compréhension un peu.

EDIT: ces mots-clés utilisent des exceptions .NET pour la signalisation

De 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