[LRUG] Writing specs for the time-complexity of a method

[Mr Jaba]

Hey Tim,

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?

My tuppence worth anyway!

Cheers

Tom

On 25 October 2011 10:55, Tim Cowlishaw <tim at timcowlishaw.co.uk> wrote:

> Hi all,
>
> This might be a pretty hare-brained idea, but I was wondering if
> anyone's ever tried to write specs that test the time complexity of a
> given method call?
>
> For reference, I'm currently writing a ruby implementation of the
> aho-corasick string matching algorithm [1], the behaviour of which can
> be specified by the following rspec specs:
> https://gist.github.com/1312065
>
> However, these specs can be vacously satisfied by the following
> implementation, which doesn't perform the aho-corasick algorithm, but
> instead matches strings by a naive iterative process:
> https://gist.github.com/1312074
>
> Now, the motivation for doing this in the first place was in order to
> locate all the members of a set of strings which are present in
> another string in O(n) time, where n is the length of the string to be
> matched against. The naive approach takes O(knm) where n is the length
> of the matched string, k is the number of 'candidate' strings in the
> set, and m is the average length of a candidate string. Therefore, it
> seems to me that I should write a spec which says something like `it
> "should take constant time relative to the length of the string to
> match'` as this encapsulates my requirements, and doesn't over-specify
> the implementation. However, my gut feeling is that this is a pretty
> silly idea (and also tricky to implement, as I'd need to build in some
> degree of tolerance to the time measurements).
>
> Therefore, does anyone have a better approach for specifying the
> required time-complexity of a certain method or process? Or is it just
> something that doesn't need testing?
>
> Thanks,
>
> Tim
>
>
> REFERENCES
> ---------------------
> [1]
> http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm
> _______________________________________________
> Chat mailing list
> Chat at lists.lrug.org
> http://lists.lrug.org/listinfo.cgi/chat-lrug.org
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.lrug.org/pipermail/chat-lrug.org/attachments/20111025/9b604cf5/attachment.html>