<div dir="ltr">By using native compilation, I got these numbers:<br><br>$ erlc +native words.erl<br>$ erl<br><br>> {ok, Bin} = file:read_file("AV1611Bible.txt").<br>> f(L), {_, L} = timer:tc(fun() -> words:go(Bin) end).<br>
<br>> length(L).<br><br>98643 us., this is 20x faster than the baseline solution.<br><br>But again ... can we do better than that?<br><br>/Zab<br><br></div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/4/8 Zabrane Mikael <span dir="ltr"><<a href="mailto:zabrane3@gmail.com" target="_blank">zabrane3@gmail.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Here's a faster solution for the problem:<br><br>-------------------------------------------------<br>
<div>-module(words).</div><div><br></div><div>-export([go/1]).</div><div><br></div><div>-define(WHITESPACE(C), ((C == $\s) orelse (C == $\n) orelse (C == $\t) orelse (C == $\f) orelse (C == $\r) orelse (C == $\v))).<br>
</div><div><br></div><div>go(<<>>) -><br></div><div> [{0, 0}];</div><div>go(Bin) -></div><div> go(Bin, 0, 0, []).</div><div><br></div><div>go(<<C/integer, Rest/binary>>, Pos, Sz, Acc) -></div>
<div> case ?WHITESPACE(C) of</div><div> true when Sz > 0 -></div><div> go(Rest, Pos + Sz + 1, 0, [{Pos, Sz} | Acc]);</div><div> true -></div><div> go(Rest, Pos + Sz + 1, 0, Acc);</div>
<div> false -></div><div> go(Rest, Pos, Sz + 1, Acc)</div><div> end;</div><div>go(<<>>, _, 0, Acc) -></div><div> lists:reverse(Acc);</div><div>go(<<>>, Pos, Sz, Acc) -></div>
<div> lists:reverse([{Pos, Sz} | Acc]).</div><div>-------------------------------------------------<br><br>$ erlc words.erl<div class="im"><br>$ erl<br>> {ok, Bin} = file:read_file("AV1611Bible.txt").<br>
</div>> {, L} = timer:tc(fun() -> words:go(Bin) end).<br>
<br>764842 us. Almost 2.6 times faster than the "regular expression" based solution.<br><br>> length(L).</div><div>840245</div><div><br></div><div>We also found more words (equiv. to: $ wc -w AV1611Bible.txt).<br>
<br>So guys, can we do better than that? Please advice/help/hack!<br><br>regards<br>/Zab<br><br></div><div class="gmail_extra"><div><div class="h5"><br><br><div class="gmail_quote">2013/4/8 Zabrane Mikael <span dir="ltr"><<a href="mailto:zabrane3@gmail.com" target="_blank">zabrane3@gmail.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">Thanks James. Already checked that.<div><br>
</div><div>/Zab</div></div><div class="gmail_extra"><div><div><br><br><div class="gmail_quote">2013/4/8 James Aimonetti <span dir="ltr"><<a href="mailto:james@2600hz.com" target="_blank">james@2600hz.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">-----BEGIN PGP SIGNED MESSAGE-----<br>
Hash: SHA1<br>
<br>
You may want to research the widefinder project that Tim Bray did a<br>
while ago; I think there were quite a few submissions in Erlang that<br>
had interesting optimizations for text processing.<br>
<div><div><br>
<br>
On 04/08/2013 11:17 AM, Zabrane Mickael wrote:<br>
> Hi guys,<br>
><br>
> I'm facing a nice problem in order to accelerate words search in a<br>
> fairly large file.<br>
><br>
> * Problem: get a list of [{offset, size} | ...] for each word in a<br>
> text file.<br>
><br>
> * Baseline: For the purpose of the exercise, I'm using an online<br>
> version of "King James Bible".<br>
><br>
> $ wget <a href="http://printkjv.ifbweb.com/AV_txt.zip" target="_blank">http://printkjv.ifbweb.com/AV_txt.zip</a> $ unzip -a AV_txt.zip<br>
><br>
> $ erl<br>
>> {ok, Bin} = file:read_file("AV1611Bible.txt"). {ok, MP} =<br>
>> re:compile("\\w+"). {match, L} = re:run(Bin, MP, [global]).<br>
>> length(L).<br>
> 839979<br>
><br>
> When timing this version on my machine, I got:<br>
>> timer:tc( fun() -> re:run(Bin, MP, [global]) end ).<br>
><br>
> 2002007 us., which is OK. But can we do better? And how fast we can<br>
> go?<br>
><br>
> The word separators for this problem are: $\s, $\t, $\n, and $\r.<br>
> You can use anything you'd like to accelerate the solution (binary<br>
> matching, os:cmd(), open_port, NIF, LinkedIn driver).<br>
><br>
> The only one constraint is to get back a list of [{offset, size} |<br>
> ...] as a result.<br>
><br>
> Waiting your hacks ... thanks!!!<br>
><br>
> Regards, Zab<br>
><br>
><br>
><br>
</div></div>> _______________________________________________ erlang-questions<br>
> mailing list <a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
> <a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
><br>
<br>
<br>
- --<br>
James Aimonetti<br>
Distributed Systems Engineer / DJ MC_<br>
<br>
2600hz | <a href="http://2600hz.com" target="_blank">http://2600hz.com</a><br>
<a href="mailto:sip%3Ajames@2600hz.com" target="_blank">sip:james@2600hz.com</a><br>
tel: 415.886.7905<br>
-----BEGIN PGP SIGNATURE-----<br>
Version: GnuPG v1.4.11 (GNU/Linux)<br>
Comment: Using GnuPG with Thunderbird - <a href="http://www.enigmail.net/" target="_blank">http://www.enigmail.net/</a><br>
<br>
iQEcBAEBAgAGBQJRYo4kAAoJENc77s1OYoGgYX8H/2wgYJGINGrseQpw7gYpuy7W<br>
lAQ2dHBHFUcn2V8kTKBZpCIxC62DRgeuNmJQ6wiHn5KuNonLtUcFSN2Nh2Z2KKNi<br>
TbbOJOJggswpgLK2Cop+pk2+9811x1bhCPDm5cLtrK2m3D8lMjgCLdvycEfbaAd5<br>
oAKZgIJ7PD2syccMoMcyn6UI6Jf0DrEG+U0r6Aiy81rSZv1WqEtzWT1M4rfb6LYO<br>
wFUwPWBhgcDAYUA+6A1I+uaav/IU+lGmQ/gie5ZXHvIbrTl2uD++4fyZU6QKD5Ck<br>
VkJhOO/PPS3XccE5m+tgWm38ZnLiikREiVtOZYQxNA0RCue9Bwoq4B5awy1MgBA=<br>
=jtwl<br>
-----END PGP SIGNATURE-----<br>
_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
</blockquote></div><br><br clear="all"><div><br></div></div></div><span><font color="#888888">-- <br>Regards<br>Zabrane
</font></span></div>
</blockquote></div><br><br clear="all"><div><br></div></div></div><span class="HOEnZb"><font color="#888888">-- <br>Regards<br>Zabrane
</font></span></div></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br>Regards<br>Zabrane
</div>