Yes indeed! This seems to be as fast as the C code. I can't find any substantial difference, at least. I'll push these changes and take a look at Hongwei's comments next :)
Thanks! On 07/20/2018 03:33 AM, Artyom Shalkhakov wrote: > On Friday, July 20, 2018 at 1:22:47 PM UTC+6, Vanessa McHale wrote: > > I'll have to take a look at for/while loops :). With Hongwei's > suggestion it's nearly as fast as the C code (and it beats two > common Rust libraries), but I wouldn't mind squeezing the last > little bit out just for bragging rights (slash ATS advertising). > > > > Is this any faster? > > https://glot.io/snippets/f32psc1xh1 > > The array is now initialized only once. > > > On 07/19/2018 11:26 PM, Artyom Shalkhakov wrote: >> Hi Vanessa, >> >> I guess we could improve as follows: >> >> 1. just like in C, initialize the array only once (use >> array_ptr_alloc & array_initize) >> 2. replace the use of tail-rec functions with while loops :) (in >> classic C-style ATS) >> 3. maybe use alloca instead of malloc (since the C example does >> just that) >> >> On Friday, July 20, 2018 at 8:37:13 AM UTC+6, Vanessa McHale wrote: >> >> Hi all, >> >> I have been working on an implementation of the Levenshtein >> distance >> between two strings. I got a working implementation, but it is >> significantly slower than the C version, viz. >> >> #define MIN3(a, b, c) ((a) < (b) ? ((a) < (c) ? (a) : (c)) : >> ((b) < (c) >> ? (b) : (c))) >> >> // taken from here: >> >> https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C >> >> <https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C> >> int levenshtein(char *s1, char *s2) { >> unsigned int s1len, s2len, x, y, lastdiag, olddiag; >> s1len = strlen(s1); >> s2len = strlen(s2); >> unsigned int column[s1len+1]; >> for (y = 1; y <= s1len; y++) >> column[y] = y; >> for (x = 1; x <= s2len; x++) { >> column[0] = x; >> for (y = 1, lastdiag = x-1; y <= s1len; y++) { >> olddiag = column[y]; >> column[y] = MIN3(column[y] + 1, column[y-1] + 1, >> lastdiag + >> (s1[y-1] == s2[x-1] ? 0 : 1)); >> lastdiag = olddiag; >> } >> } >> return(column[s1len]); >> >> This is the ATS: >> >> staload "prelude/SATS/string.sats" >> >> fun min_3(x : int, y : int, z : int) : int = >> min(x, (min(y, z))) >> >> fun bool2int(x : char, y : char) : int = >> if x = y then >> 0 >> else >> 1 >> >> // Ported over from >> >> https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C >> >> <https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C> >> fn levenshtein {m:nat}{n:nat}(s1 : string(m), s2 : string(n)) >> : int = >> let >> val s1_l: size_t(m) = length(s1) >> val s2_l: size_t(n) = length(s2) >> val column: arrszref(int) = arrszref_make_elt(s1_l + 1, 0) >> >> fun loop1 { i : nat | i <= m } .<i>. (i : int(i)) : void = >> case+ i of >> | 0 => () >> | i =>> { >> val () = column[i] := i >> val () = loop1(i - 1) >> } >> >> val () = loop1(sz2i(s1_l)) >> >> fun loop2 { i : nat | i > 0 && i <= n+1 } .<n-i+1>. (x : >> int(i)) : >> void = >> if x <= sz2i(s2_l) then >> { >> val () = column[0] := x >> val () = let >> fun inner_loop { j : nat | j > 0 && j <= m+1 } >> .<m-j+1>. (y >> : int(j), last_diag : int) : >> void = >> if y <= sz2i(s1_l) then >> let >> var old_diag = column[y] >> val () = column[y] := min_3( column[y] + 1 >> , column[y - 1] + 1 >> , last_diag + >> bool2int(s1[y >> - 1], s2[x - 1]) >> ) >> in >> inner_loop(y + 1, old_diag) >> end >> in >> inner_loop(1, x - 1) >> end >> val () = loop2(x + 1) >> } >> >> val () = loop2(1) >> in >> column[s1_l] >> end >> >> I've benchmarked them both, and the C version runs about 3 >> times faster >> (!). Would anyone happen to have any insight into these? I >> may be doing >> the benchmarking wrong but I believe it is something related >> to how I am >> using arrays in ATS. >> >> The full source code is at >> https://github.com/vmchale/edit-distance >> <https://github.com/vmchale/edit-distance> >> >> Thanks, >> Vanessa >> >> -- >> You received this message because you are subscribed to the >> Google Groups "ats-lang-users" group. >> To unsubscribe from this group and stop receiving emails from it, >> send an email to ats-lang-user...@googlegroups.com <javascript:>. >> To post to this group, send email to ats-lan...@googlegroups.com >> <javascript:>. >> Visit this group at >> https://groups.google.com/group/ats-lang-users >> <https://groups.google.com/group/ats-lang-users>. >> To view this discussion on the web visit >> >> https://groups.google.com/d/msgid/ats-lang-users/946b3ea9-eb24-4cf5-bf24-9aab7a8d9383%40googlegroups.com >> >> <https://groups.google.com/d/msgid/ats-lang-users/946b3ea9-eb24-4cf5-bf24-9aab7a8d9383%40googlegroups.com?utm_medium=email&utm_source=footer>. > > -- > You received this message because you are subscribed to the Google > Groups "ats-lang-users" group. > To unsubscribe from this group and stop receiving emails from it, send > an email to ats-lang-users+unsubscr...@googlegroups.com > <mailto:ats-lang-users+unsubscr...@googlegroups.com>. > To post to this group, send email to ats-lang-users@googlegroups.com > <mailto:ats-lang-users@googlegroups.com>. > Visit this group at https://groups.google.com/group/ats-lang-users. > To view this discussion on the web visit > https://groups.google.com/d/msgid/ats-lang-users/fccac5d3-9276-4410-bf95-4516ba0859f7%40googlegroups.com > <https://groups.google.com/d/msgid/ats-lang-users/fccac5d3-9276-4410-bf95-4516ba0859f7%40googlegroups.com?utm_medium=email&utm_source=footer> -- You received this message because you are subscribed to the Google Groups "ats-lang-users" group. To unsubscribe from this group and stop receiving emails from it, send an email to ats-lang-users+unsubscr...@googlegroups.com. To post to this group, send email to ats-lang-users@googlegroups.com. Visit this group at https://groups.google.com/group/ats-lang-users. To view this discussion on the web visit https://groups.google.com/d/msgid/ats-lang-users/fdc1bc21-e4de-cb50-408e-94acc770d938%40iohk.io.
signature.asc
Description: OpenPGP digital signature
