Path: csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <d@davea.name>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.025
X-Spam-Evidence: '*H*': 0.95; '*S*': 0.00; 'case.': 0.05; 'cc:addr :python-list': 0.10; 'looked': 0.10; '(the': 0.15; '(string': 0.16; 'comparisons,': 0.16; 'mismatch': 0.16; 'remembered': 0.16; 'to:addr:pearwood.info': 0.16; 'to:addr:steve+comp.lang.python': 0.16; "to:name:steven d'aprano": 0.16; 'string': 0.17; 'wrote:': 0.17; 'certainly': 0.17; 'passes': 0.17; 'string,': 0.17; 'obviously': 0.18; '(or': 0.18; 'define': 0.20; 'earlier': 0.21; 'rapidly': 0.22; 'defined': 0.22; 'required.': 0.22; 'cc:2**0': 0.23; 'random': 0.24; 'cc:no real name:2**0': 0.24; "we'd": 0.24; 'testing': 0.24; 'cc:addr:python.org': 0.25; 'header:In-Reply- To:1': 0.25; 'header:User-Agent:1': 0.26; '(which': 0.26; 'am,': 0.27; 'possibly': 0.27; '(as': 0.27; "doesn't": 0.28; "d'aprano": 0.29; 'equality': 0.29; 'probability': 0.29; 'steven': 0.29; 'strings,': 0.29; 'case,': 0.29; 'character': 0.29; 'selection': 0.29; "i'm": 0.29; 'point.': 0.33; "can't": 0.34; 'subject:?': 0.35; 'something': 0.35; 'really': 0.36; 'but': 0.36; 'wanted': 0.36; 'characters': 0.36; 'compare': 0.36; 'possible': 0.37; 'being': 0.37; 'quite': 0.37; 'subject:: ': 0.38; 'some': 0.38; 'sure': 0.38; 'science': 0.38; 'received:192': 0.39; 'notice': 0.39; 'where': 0.40; 'received:192.168': 0.40; 'end': 0.40; 'further': 0.61; 'first': 0.61; 'safe': 0.63; 'times': 0.63; 'within': 0.64; 'else.': 0.65; 'population': 0.65; 'header:Reply- To:1': 0.68; 'received:74.208': 0.71; 'reply-to:no real name:2**0': 0.72; '(every': 0.84; 'received:74.208.4.194': 0.84; 'items,': 0.91; 'matter),': 0.91; 'average': 0.93; 'few.': 0.93
Date: Thu, 06 Sep 2012 06:07:38 -0400
From: Dave Angel <d@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120714 Thunderbird/14.0
MIME-Version: 1.0
To: Steven D'Aprano <steve+comp.lang.python@pearwood.info>
Subject: Re: Comparing strings from the back?
References: <roy-B37C28.21540103092012@news.panix.com> <504564ba$0$29978$c3e8da3$5496439d@news.astraweb.com> <k25afd$7vj$1@news.albasani.net> <mailman.194.1346795987.27098.python-list@python.org> <k275on$i1l$1@news.albasani.net> <k276r0$k5k$1@news.albasani.net> <504761ef$0$29981$c3e8da3$5496439d@news.astraweb.com> <k27osg$q7t$1@news.albasani.net> <50477cbb$0$29981$c3e8da3$5496439d@news.astraweb.com> <mailman.272.1346885254.27098.python-list@python.org> <50485fca$0$29977$c3e8da3$5496439d@news.astraweb.com>
In-Reply-To: <50485fca$0$29977$c3e8da3$5496439d@news.astraweb.com>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Provags-ID: V02:K0:rfhkhwrUmc8/7W62+KBB4vvPRusMeDNCzRgcOvew/QO 05xIueCpaxzE9+YKKFV92aaKn01ESIrkDinAUr20BrSRAIWMm6 ZOMKQr++ChZXHS6+QQHYBbBSaJSL7fuovUQPGNWraT/5BTMoY/ 1LUEp5YmAJWHpou+c7Jnn4DCWde8dXZT7G6juI7f/i/53meTyE wA3bXSSTz32QTOxUuye4xaAeK4vasss3b50TKfpsMEIHWoPAqW fB7XFaMEFn/e9pcvFIIodM4ROlW3TlCWkef4QWWbO8ndQ0D+Jc +/PPiY6hFNkykpM1LSwNtPuxnAka9Suu2OapPZUKvCjRTdb3A= =
Cc: python-list@python.org
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
Precedence: list
Reply-To: d@davea.name
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.287.1346926087.27098.python-list@python.org>
Lines: 42
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1346926087 news.xs4all.nl 6944 [2001:888:2000:d::a6]:52591
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:28569

On 09/06/2012 04:33 AM, Steven D'Aprano wrote:
> <snip>
>
> I may have been overly-conservative earlier when I said that on
> average string equality has to compare half the characters. I thought
> I had remembered that from a computer science textbook, but I can't
> find that reference now, so possibly I was thinking of something else.
> (String searching perhaps?). In any case, the *worst* case for string
> equality testing is certainly O(N) (every character must be looked
> at), and the *best* case is O(1) obviously (the first character fails
> to match). But I'm not so sure about the average case. Further thought
> is required. 

For random strings (as defined below), the average compare time is
effectively unrelated to the size of the string, once the size passes
some point.

Define random string as being a selection from a set of characters, with
replacement.  So if we pick some set of characters, say 10 (or 256, it
doesn't really matter), the number of possible strings is 10**N.

The likelihood of not finding a mismatch within k characters is  
(1/10)**k   The likelihood of actually reaching the end of the random
string is (1/10)**N.  (which is the reciprocal of the number of strings,
naturally)

If we wanted an average number of comparisons, we'd have to calculate a
series, where each term is a probability times a value for k.
   sum((k * 9*10**-k) for k in range(1, 10))


Those terms very rapidly approach 0, so it's safe to stop after a few. 
Looking at the first 9 items, I see a value of 1.1111111

This may not be quite right, but the value is certainly well under 2 for
a population of 10 characters, chosen randomly.  And notice that N
doesn't really come into it. 

-- 

DaveA