StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POWhy is this F# code so slow?
text
Body
copied!<p>A Levenshtein implementation in C# and F#. The C# version is 10 times faster for two strings of about 1500 chars. C#: 69 ms, F# 867 ms. Why? As far as I can tell, they do the exact same thing? Doesn't matter if it is a Release or a Debug build. </p> <p>EDIT: If anyone comes here looking specifically for the Edit Distance implementation, it is broken. Working code is <a href="https://bitbucket.org/vgrit/clrsquirrel/src/82840c2ce95b/ClrSquirrel/ClrSquirrel.fs" rel="noreferrer">here</a>.</p> <p><strong>C#</strong>:</p> <pre class="lang-cs prettyprint-override"><code>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]; } </code></pre> <p><strong>F#</strong>:</p> <pre class="lang-ml prettyprint-override"><code>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] </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload