SORU
23 Mayıs 2011, PAZARTESİ


Neden bu F# bu kadar yavaş?kod

C Levenshtein bir uygulama# ve F#. C# sürümü 10 kat daha hızlı yaklaşık 1500 karakter iki dizeleri. C#: 69 ms, F# 867 ms. Neden? Söyleyebileceğim kadarıyla, aynı şeyi yapıyorlar? Eğer bir Yayın ise önemli değil ya da bir hata Ayıklama derlemesi.

Eğer herkes, özellikle sizin için, size gelirse burada Mesafe uygulaması, Düzen bozulur. EDİT: Kod çalışıyor here.

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]

CEVAP
23 Mayıs 2011, PAZARTESİ


Asıl sorun min3 işlev derlenmiş olarak genel bir işlevi kullanan bir genel karşılaştırma (düşündüm bu kullanır sadece IComparable ama aslında daha da karmaşık olacaktır kullanın yapısal karşılaştırma için F# türleri ve bu oldukça karmaşık mantık).

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

C# sürümü, işlev genel değil (sadece int alır). F artırabilirsiniz# ekleme türü ek açıklamalar ile sürüm (C aynı şey olsun#):

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

...ya inline min3 yaparak bu durumda kullanılan int için özel olacak ():

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

Uzunlukta rasgele bir dize str 300, aşağıdaki numaralarını ulaşın:

> 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

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • BioHunta

    BioHunta

    28 Mayıs 2006
  • ibebrent

    ibebrent

    23 Temmuz 2007
  • Manuel Vizcaino

    Manuel Vizca

    27 Mayıs 2008