Gelonida N <gelon...@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 -- http://mail.python.org/mailman/listinfo/python-list
