Hey Tim, <br><br>Sounds like an interesting idea; but I'm guessing that the difference would be negligible between the two implementations for any small set of data, so to actually get a difference you could measure reliably you'd need to work with large sets of data and thus slow your test suite down. I guess my point is that you have already tested the functionality of the algorithm, would it be worth the added complexity of timing the tests? What's the benefit? <br>
<br>My tuppence worth anyway!<br><br>Cheers<br><br>Tom<br><br><div class="gmail_quote">On 25 October 2011 10:55, Tim Cowlishaw <span dir="ltr"><<a href="mailto:tim@timcowlishaw.co.uk">tim@timcowlishaw.co.uk</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Hi all,<br>
<br>
This might be a pretty hare-brained idea, but I was wondering if<br>
anyone's ever tried to write specs that test the time complexity of a<br>
given method call?<br>
<br>
For reference, I'm currently writing a ruby implementation of the<br>
aho-corasick string matching algorithm [1], the behaviour of which can<br>
be specified by the following rspec specs:<br>
<a href="https://gist.github.com/1312065" target="_blank">https://gist.github.com/1312065</a><br>
<br>
However, these specs can be vacously satisfied by the following<br>
implementation, which doesn't perform the aho-corasick algorithm, but<br>
instead matches strings by a naive iterative process:<br>
<a href="https://gist.github.com/1312074" target="_blank">https://gist.github.com/1312074</a><br>
<br>
Now, the motivation for doing this in the first place was in order to<br>
locate all the members of a set of strings which are present in<br>
another string in O(n) time, where n is the length of the string to be<br>
matched against. The naive approach takes O(knm) where n is the length<br>
of the matched string, k is the number of 'candidate' strings in the<br>
set, and m is the average length of a candidate string. Therefore, it<br>
seems to me that I should write a spec which says something like `it<br>
"should take constant time relative to the length of the string to<br>
match'` as this encapsulates my requirements, and doesn't over-specify<br>
the implementation. However, my gut feeling is that this is a pretty<br>
silly idea (and also tricky to implement, as I'd need to build in some<br>
degree of tolerance to the time measurements).<br>
<br>
Therefore, does anyone have a better approach for specifying the<br>
required time-complexity of a certain method or process? Or is it just<br>
something that doesn't need testing?<br>
<br>
Thanks,<br>
<br>
Tim<br>
<br>
<br>
REFERENCES<br>
---------------------<br>
[1] <a href="http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm" target="_blank">http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm</a><br>
_______________________________________________<br>
Chat mailing list<br>
<a href="mailto:Chat@lists.lrug.org">Chat@lists.lrug.org</a><br>
<a href="http://lists.lrug.org/listinfo.cgi/chat-lrug.org" target="_blank">http://lists.lrug.org/listinfo.cgi/chat-lrug.org</a><br>
</blockquote></div><br>