Pourquoi ce code F # est-il si lent?

Question

Un Levenshtein mise en œuvre en C# et F#. La version C# est 10 fois plus rapide pour les deux chaînes d'environ 1500 caractères. C#: 69 ms, F# 867 mme. Pourquoi? Aussi loin que je peux dire, qu'ils font exactement la même chose? N'a pas d'importance si c'est une Version ou d'une version de Débogage.

EDIT: Si quelqu'un vient ici à la recherche spécifiquement pour la Distance d'Édition mise en œuvre, il est cassé. Code de travail est ici.

C#:

private static int min3(int a, int b, int c)
{
   return Math.Min(Math.Min(a, b), c);
}

public static int EditDistance(string m, string n)
{
   var d1 = new int[n.Length];
   for (int x = 0; x < d1.Length; x++) d1[x] = x;
   var d0 = new int[n.Length];
   for(int i = 1; i < m.Length; i++)
   {
      d0[0] = i;
      var ui = m[i];
      for (int j = 1; j < n.Length; j++ )
      {
         d0[j] = 1 + min3(d1[j], d0[j - 1], d1[j - 1] + (ui == n[j] ? -1 : 0));
      }
      Array.Copy(d0, d1, d1.Length);
   }
   return d0[n.Length - 1];
}

F#:

let min3(a, b, c) = min a (min b c)

let levenshtein (m:string) (n:string) =
   let d1 = Array.init n.Length id
   let d0 = Array.create n.Length 0
   for i=1 to m.Length-1 do
      d0.[0] <- i
      let ui = m.[i]
      for j=1 to n.Length-1 do
         d0.[j] <- 1 + min3(d1.[j], d0.[j-1], d1.[j-1] + if ui = n.[j] then -1 else 0)
      Array.blit d0 0 d1 0 n.Length
   d0.[n.Length-1]

Answer 1

Le problème est que l' min3 fonction est compilé comme une fonction générique qui utilise générique de comparaison (je pensais que ce n'utilise qu' IComparable, mais il est en fait plus compliqué qu'il faudrait utiliser la comparaison structurelle de types F#, et il est assez logique complexe).

> let min3(a, b, c) = min a (min b c);;
val min3 : 'a * 'a * 'a -> 'a when 'a : comparison

Dans la version C#, la fonction n'est pas générique (il faut juste int). Vous pouvez améliorer le F# version en ajoutant des annotations de type (pour obtenir la même chose qu'en C#):

let min3(a:int, b, c) = min a (min b c)

...ou en faisant en min3 comme inline (auquel cas, il sera spécialisé pour int lorsqu'elle est utilisée):

let inline min3(a, b, c) = min a (min b c);;

Pour une chaîne de caractères aléatoires str d'une longueur de 300, - je obtenir les numéros suivants:

> levenshtein str ("foo" + str);;
Real: 00:00:03.938, CPU: 00:00:03.900, GC gen0: 275, gen1: 1, gen2: 0
val it : int = 3

> levenshtein_inlined str ("foo" + str);;
Real: 00:00:00.068, CPU: 00:00:00.078, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 3