On 10/09/2012 18:07, Dan Goodman wrote:
> On 04/09/2012 03:54, Roy Smith wrote:Just had another thought about this. Although it's unlikely to be
>> Let's assume you're testing two strings for equality. You've already
>> done the obvious quick tests (i.e they're the same length), and you're
>> down to the O(n) part of comparing every character.
>> I'm wondering if it might be faster to start at the ends of the strings
> From the rest of the thread, it looks like in most situations it won't
> However, if you were in a situation with many strings which were almost
necessary in practice since (a) it's rarely necessary at all, and (b)
when it is, hashing and optionally interning seems like the better
approach, I had another idea that would be more general. Rather than
starting from the beginning or the end, why not do something like: check
the first and last character, then the len/2 character, then the len/4,
then 3*len/4, then len/8, 3*len/8, etc. You'd need to be a bit clever
about making sure you hit every character but I'm sure someone's already
got an efficient algorithm for this. You could probably even make this
cache efficient by working on cache line length blocks. Almost certainly
entirely unnecessary, but I like the original question and it's a nice
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.