Comparing strings from the back?

[Duncan Booth]

Gelonida N <gelonida at gmail.com> wrote:

> On 09/07/2012 06:06 AM, Steven D'Aprano wrote:
>> On Thu, 06 Sep 2012 06:07:38 -0400, Dave Angel wrote:
>>
>>
>> Also of some interest is the best case: O(1) for unequal strings (they
>> differ at the first character) and O(N) for equal strings.
> 
> The worst case is O(N) or N characters
> the average case is O(1) or two characters.
> 
> For denial of service attacks or systems, that are NEVER allowed to fail 
> the worst case is important.
> 
> For most other cases the average complexity counts.
> 
> However I still wonder for how many applications the complexity of 
> string comparisons would be the limiting factor.
> 
> 
and of course if you ever do find an application where that worst case 
matters there's an easy way round it: just call intern() on all the strings 
when they are created.

For the comparison to be the limiting factor you have to be doing a lot of 
comparisons on the same string (otherwise creating the string would be the 
limiting factor), so at the expense of a single dictionary insertion when 
the string is created you can get guaranteed O(1) on all the comparisons.

-- 
Duncan Booth http://kupuguy.blogspot.com