Implementacja Levenshtein w językach C # i F #. Wersja C # jest 10 razy szybsza dla dwóch ciągów około 1500 znaków. C #: 69 ms, F # 867 ms. Czemu? O ile wiem, robią dokładnie to samo? Nie ma znaczenia, czy jest to wersja Release czy Debug.
EDYCJA: Jeśli ktoś przychodzi tutaj szukając implementacji Edit Distance, to jest zepsuty. Kod roboczy jest tutaj .
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]
c#
performance
f#
inline
Robert Jeppesen
źródło
źródło
Odpowiedzi:
Problem polega na tym, że
min3
funkcja jest kompilowana jako funkcja ogólna, która używa ogólnego porównania (myślałem, że używa ona tylkoIComparable
, ale w rzeczywistości jest bardziej skomplikowana - użyłaby porównania strukturalnego dla typów F # i jest to dość złożona logika).> let min3(a, b, c) = min a (min b c);; val min3 : 'a * 'a * 'a -> 'a when 'a : comparison
W wersji C # funkcja nie jest ogólna (po prostu bierze
int
). Możesz ulepszyć wersję F #, dodając adnotacje typu (aby uzyskać to samo, co w C #):let min3(a:int, b, c) = min a (min b c)
... lub wykonując
min3
jakoinline
(w takim przypadku będzie wyspecjalizowany,int
gdy zostanie użyty):let inline min3(a, b, c) = min a (min b c);;
W przypadku losowego ciągu
str
o długości 300 otrzymuję następujące liczby:> 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
źródło
inline
działa jak szablon C ++, który specjalizuje się wint
oparciu o witrynę wywołań.inline
. Powodem, dla którego domyślne zachowanie jest inne, jest to, że opiera się on na typach .Net, które są obsługiwane przez środowisko wykonawcze (i prawdopodobnie nie są tak dobre do pisania ogólnego kodu numerycznego). Użycie zachowania C ++ w języku F # doprowadziłoby jednak do rozdęcia kodu, ponieważ F # używa o wiele więcej typów ogólnych.