Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #28720

Re: Comparing strings from the back?

Path csiph.com!usenet.pasdenom.info!news.albasani.net!newsfeed.freenet.ag!news2.euro.net!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path <python-python-list@m.gmane.org>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.000
X-Spam-Evidence '*H*': 1.00; '*S*': 0.00; 'mathematics': 0.04; '(except': 0.05; 'say,': 0.05; 'nasty': 0.07; 'bounds.': 0.09; 'dict': 0.09; 'if,': 0.09; 'ignoring': 0.09; 'imply': 0.09; 'insertion': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'sep': 0.09; 'def': 0.10; 'assume': 0.11; 'cases': 0.15; "(i'm": 0.16; '2.)': 0.16; 'amortized': 0.16; 'arbitrarily': 0.16; 'assumptions': 0.16; 'b):': 0.16; 'benjamin': 0.16; 'both.': 0.16; 'bound,': 0.16; 'bounds': 0.16; 'code?': 0.16; 'complexity,': 0.16; 'disk.': 0.16; 'equality.': 0.16; 'example)': 0.16; 'insertions': 0.16; 'lookups.': 0.16; 'numpy': 0.16; 'rather,': 0.16; 'received:80.91.229.3': 0.16; 'received:plane.gmane.org': 0.16; 'slow,': 0.16; 'unequal': 0.16; 'unequal,': 0.16; 'string': 0.17; 'wrote:': 0.17; 'mathematical': 0.17; '>>>': 0.18; 'memory': 0.18; '(or': 0.18; 'code.': 0.20; 'assuming': 0.22; 'libraries': 0.22; 'defined': 0.22; "i've": 0.23; 'random': 0.24; 'header:User- Agent:1': 0.26; 'used,': 0.27; "doesn't": 0.28; 'header:X -Complaints-To:1': 0.28; 'actual': 0.28; 'run': 0.28; '"in': 0.29; 'behaviour': 0.29; 'comparison': 0.29; "d'aprano": 0.29; 'forces': 0.29; 'hash': 0.29; 'probability': 0.29; 'steven': 0.29; 'strings,': 0.29; 'yes.': 0.29; 'character': 0.29; 'starts': 0.29; 'words': 0.29; "we're": 0.30; 'fri,': 0.30; 'sense': 0.31; 'code': 0.31; 'gets': 0.32; 'getting': 0.33; 'function.': 0.33; 'science.': 0.33; 'strict': 0.33; 'true.': 0.33; 'problem': 0.33; 'to:addr:python-list': 0.33; 'equal': 0.33; 'likely': 0.33; 'another': 0.33; 'that,': 0.34; "can't": 0.34; 'text': 0.34; 'whatever': 0.35; 'ahead': 0.35; 'subject:?': 0.35; 'something': 0.35; 'received:org': 0.36; 'but': 0.36; 'characters': 0.36; 'compare': 0.36; 'depends': 0.36; 'others.': 0.36; "didn't": 0.36; 'useful': 0.36; "i'll": 0.36; 'should': 0.36; 'too': 0.36; 'enough': 0.36; 'possible': 0.37; 'does': 0.37; 'two': 0.37; 'rather': 0.37; 'data': 0.37; 'subject:: ': 0.38; 'some': 0.38; 'talk': 0.38; 'to:addr:python.org': 0.39; 'where': 0.40; 'header:Received:5': 0.40; 'think': 0.40; 'your': 0.60; 'range': 0.60; 'skip:u 10': 0.60; 'real': 0.61; 'back': 0.62; 'time,': 0.62; 'situation': 0.62; 'provide': 0.62; 'world': 0.63; 'skip:n 10': 0.63; 'more': 0.63; 'here': 0.65; 'frequency': 0.65; 'real- world': 0.65; 'surprise': 0.65; 'useful.': 0.65; 'talking': 0.66; 'analysis': 0.70; 'future,': 0.72; 'upper': 0.75; 'heavy': 0.83; 'are)': 0.84; 'bounded': 0.84; 'complexity': 0.84; 'oscar': 0.84; 'apparent': 0.91; 'attitude': 0.91; 'increases': 0.91; 'mistake': 0.91; 'average': 0.93
X-Injected-Via-Gmane http://gmane.org/
To python-list@python.org
From Oscar Benjamin <oscar.j.benjamin@gmail.com>
Subject Re: Comparing strings from the back?
Date Sat, 8 Sep 2012 11:53:13 +0000 (UTC)
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> <mailman.287.1346926087.27098.python-list@python.org> <504972d1$0$29981$c3e8da3$5496439d@news.astraweb.com> <mailman.366.1347045032.27098.python-list@python.org> <504a9785$0$29981$c3e8da3$5496439d@news.astraweb.com>
X-Gmane-NNTP-Posting-Host cpc1-aztw8-0-0-cust1455.18-1.cable.virginmedia.com
User-Agent slrn/pre1.0.0-18 (Linux)
X-BeenThere python-list@python.org
X-Mailman-Version 2.1.15
Precedence list
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.380.1347105208.27098.python-list@python.org> (permalink)
Lines 96
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1347105208 news.xs4all.nl 6966 [2001:888:2000:d::a6]:42641
X-Complaints-To abuse@xs4all.nl
Xref csiph.com comp.lang.python:28720

Show key headers only | View raw

On 2012-09-08, Steven D'Aprano <steve+comp.lang.python@pearwood.info> wrote:
> On Fri, 07 Sep 2012 19:10:16 +0000, Oscar Benjamin wrote:
>
>> On 2012-09-07, Steven D'Aprano <steve+comp.lang.python@pearwood.info>
>> wrote:
>> <snip>
>> 
>> Would you say, then, that dict insertion is O(N)?
>
> Pedantically, yes. 
>
> But since we're allowed to state (or even imply *wink*) whatever 
> assumptions we like, we're allowed to assume "in the absence of 
> significant numbers of hash collisions" and come up with amortized O(1) 
> for dict insertions and lookups.
>
> (Provided, of course, that your computer has an infinite amount of 
> unfragmented memory and the OS never starts paging your dict to disk. 
> Another unstated assumption that gets glossed over when we talk about 
> complexity analysis -- on real world computers, for big enough N, 
> *everything* is O(2**N) or worse.)
>
> Big Oh analysis, despite the formal mathematics used, is not an exact 
> science. Essentially, it is a way of bringing some vague order to hand-
> wavy estimates of complexity, and the apparent mathematical rigour is 
> built on some awfully shaky foundations. But despite that, it actually is 
> useful.
>
> Coming back to strings... given that in any real-world application, you 
> are likely to have some string comparisons on equal strings and some on 
> unequal strings, and more importantly you don't know which are which 
> ahead of time, which attitude is less likely to give you a nasty surprise 
> when you run your code?
>
> "I have many millions of 100K strings to compare against other 100K 
> strings, and string comparisons are O(1) so that will be fast."
>
> "I have many millions of 100K strings to compare against other 100K 
> strings, and string comparisons are O(N) so that will be slow, better 
> find another algorithm."

True. I can't think of a situation where I've used string comparisons
directly in any text heavy code. Rather, I would use a dict or a set (or a
regex) and hash(str) is always O(N).

>
>
> Remember too that "for small enough N, everything is O(1)". Getting hung 
> up on Big Oh is just as much a mistake as ignoring it completely.
>
>

I can't think of a situation in my own work where O(N) vs O(1) string
comparisons would cause a significant problem (except perhaps in libraries
that I use but didn't write). However, I can find a number of cases where I
compare numpy.ndarrays for equality. For example, I found

if np.all(a == b):

in some code that I recently wrote. Although np.all() short-circuits, a==b
does not so that line forces O(N) behaviour onto a situation where the average
case can be better. Unfortunately numpy doesn't seem to provide a
short-circuit equals() function. array_equal() is what I want but it does the
same as the above. In future, I'll consider using something like

def cmparray(a, b):
  return a.shape == b.shape and a.dtype == b.dtype and buffer(a) == buffer(b)

to take advantage of (what I assume are) short-circuit buffer comparisons.

>> Since string comparison is only useful if the strings can be equal or
>> unequal, the average case depends on how often they are equal/unequal as
>> well as the average complexity of both. For random strings the frequency
>> of equal strings decreases very fast as N increases so that the
>> comparison of random strings is O(1).
>
> But that is not an upper bound, and Big Oh analysis is strictly defined 
> in terms of upper bounds.

It is an upper bound, but it is an upper bound on the *expectation value*
assuming a particular distribution of inputs, rather than an upper bound on
all possible inputs.

>>> (I'm talking about the average here -- the actual number of comparisons
>>> can range all the way up to N, but the average is <= 2.)

The average is actually bounded by 1 / (1 - p) where p is the probability that
two characters match. This bound can be arbitrarily large as p approaches 1 as
would be the case if, say, one character was much more likely than others. The
particular assumption that you have made p = 1/M where M is the number of
characters is actually the *smallest* possible value of p. For non-uniform
real data (English words for example) p is significantly greater than 1/M but
in a strict bounds sense we should say that 1/M <= p <= 1.

Oscar

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Comparing strings from the back? Roy Smith <roy@panix.com> - 2012-09-03 21:54 -0400
  Re: Comparing strings from the back? Chris Angelico <rosuav@gmail.com> - 2012-09-04 12:07 +1000
  Re: Comparing strings from the back? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-09-04 02:17 +0000
    Re: Comparing strings from the back? Dan Sommers <dan@tombstonezero.net> - 2012-09-03 21:56 -0700
    Re: Comparing strings from the back? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-09-04 08:50 +0100
    Re: Comparing strings from the back? Johannes Bauer <dfnsonfsduifb@gmx.de> - 2012-09-04 18:32 +0200
      Re: Comparing strings from the back? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-09-04 18:07 +0000
        Re: Comparing strings from the back? Johannes Bauer <dfnsonfsduifb@gmx.de> - 2012-09-05 11:17 +0200
      Re: Comparing strings from the back? Chris Angelico <rosuav@gmail.com> - 2012-09-05 07:59 +1000
        Re: Comparing strings from the back? Johannes Bauer <dfnsonfsduifb@gmx.de> - 2012-09-05 11:24 +0200
          Re: Comparing strings from the back? Johannes Bauer <dfnsonfsduifb@gmx.de> - 2012-09-05 11:43 +0200
            Re: Comparing strings from the back? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-09-05 14:30 +0000
              Re: Comparing strings from the back? Johannes Bauer <dfnsonfsduifb@gmx.de> - 2012-09-05 16:51 +0200
                Re: Comparing strings from the back? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-09-05 16:24 +0000
                Re: Comparing strings from the back? Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2012-09-05 22:47 +0000
                Re: Comparing strings from the back? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-09-06 08:33 +0000
                Re: Comparing strings from the back? Dave Angel <d@davea.name> - 2012-09-06 06:07 -0400
                Re: Comparing strings from the back? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-09-07 04:06 +0000
                Re: Comparing strings from the back? Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2012-09-07 19:10 +0000
                Re: Comparing strings from the back? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-09-08 00:55 +0000
                Re: Comparing strings from the back? Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2012-09-08 11:53 +0000
                RE: Comparing strings from the back? "Prasad, Ramit" <ramit.prasad@jpmorgan.com> - 2012-09-13 18:39 +0000
                Re: Comparing strings from the back? Dwight Hutto <dwightdhutto@gmail.com> - 2012-09-13 15:37 -0400
                Re: Comparing strings from the back? alex23 <wuwei23@gmail.com> - 2012-09-13 20:48 -0700
                Re: Comparing strings from the back? Dwight Hutto <dwightdhutto@gmail.com> - 2012-09-14 00:46 -0400
                Re: Comparing strings from the back? alex23 <wuwei23@gmail.com> - 2012-09-13 21:54 -0700
                Re: Comparing strings from the back? Dwight Hutto <dwightdhutto@gmail.com> - 2012-09-14 01:38 -0400
                Re: Comparing strings from the back? alex23 <wuwei23@gmail.com> - 2012-09-13 23:06 -0700
                Re: Comparing strings from the back? Dwight Hutto <dwightdhutto@gmail.com> - 2012-09-14 04:03 -0400
                Re: Comparing strings from the back? alex23 <wuwei23@gmail.com> - 2012-09-14 01:20 -0700
                Re: Comparing strings from the back? Dwight Hutto <dwightdhutto@gmail.com> - 2012-09-14 04:53 -0400
                Re: Comparing strings from the back? alex23 <wuwei23@gmail.com> - 2012-09-14 03:26 -0700
                Re: Comparing strings from the back? Dwight Hutto <dwightdhutto@gmail.com> - 2012-09-14 07:36 -0400
                Re: Comparing strings from the back? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-09-14 10:16 +0000
                Re: Comparing strings from the back? Dwight Hutto <dwightdhutto@gmail.com> - 2012-09-14 07:43 -0400
                RE: Comparing strings from the back? "Prasad, Ramit" <ramit.prasad@jpmorgan.com> - 2012-09-14 22:43 +0000
                Re: Comparing strings from the back? Dwight Hutto <dwightdhutto@gmail.com> - 2012-09-14 23:10 -0400
                Re: Comparing strings from the back? alex23 <wuwei23@gmail.com> - 2012-09-16 18:11 -0700
                Re: Comparing strings from the back? Chris Angelico <rosuav@gmail.com> - 2012-09-17 14:05 +1000
                Re: Comparing strings from the back? alex23 <wuwei23@gmail.com> - 2012-09-16 23:06 -0700
                Re: Comparing strings from the back? Ethan Furman <ethan@stoneleaf.us> - 2012-09-17 13:35 -0700
                Re: Comparing strings from the back? Neil Hodgson <nhodgson@iinet.net.au> - 2012-09-18 09:14 +1000
                Re: Comparing strings from the back? Ethan Furman <ethan@stoneleaf.us> - 2012-09-18 08:12 -0700
                Re: Comparing strings from the back? Dwight Hutto <dwightdhutto@gmail.com> - 2012-09-18 11:55 -0400
                Re: Comparing strings from the back? Dwight Hutto <dwightdhutto@gmail.com> - 2012-09-18 11:59 -0400
                Re: Comparing strings from the back? Dwight Hutto <dwightdhutto@gmail.com> - 2012-09-18 12:17 -0400
                Re: Comparing strings from the back? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-09-19 00:47 +0000
                Re: Comparing strings from the back? Chris Angelico <rosuav@gmail.com> - 2012-09-19 02:20 +1000
                Re: Comparing strings from the back? Dwight Hutto <dwightdhutto@gmail.com> - 2012-09-18 16:40 -0400
                Re: Comparing strings from the back? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-09-19 00:48 +0100
                Re: Comparing strings from the back? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-09-13 20:53 +0100
                Re: Comparing strings from the back? Dwight Hutto <dwightdhutto@gmail.com> - 2012-09-13 17:06 -0400
                Re: Comparing strings from the back? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-09-14 03:39 +0000
                Re: Comparing strings from the back? Chris Angelico <rosuav@gmail.com> - 2012-09-14 14:15 +1000
                Re: Comparing strings from the back? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-09-13 22:17 +0100
                Re: Comparing strings from the back? Dwight Hutto <dwightdhutto@gmail.com> - 2012-09-13 17:35 -0400
                RE: Comparing strings from the back? "Prasad, Ramit" <ramit.prasad@jpmorgan.com> - 2012-09-14 21:32 +0000
                Re: Comparing strings from the back? Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2012-09-07 19:40 +0000
                Re: Comparing strings from the back? Gelonida N <gelonida@gmail.com> - 2012-09-08 17:52 +0200
                Re: Comparing strings from the back? Duncan Booth <duncan.booth@invalid.invalid> - 2012-09-10 08:59 +0000
                Re: Comparing strings from the back? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-09-10 13:45 +0000
                Re: Comparing strings from the back? Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2012-09-10 14:06 +0000
                Re: Comparing strings from the back? Duncan Booth <duncan.booth@invalid.invalid> - 2012-09-11 09:51 +0000
                Re: Comparing strings from the back? Terry Reedy <tjreedy@udel.edu> - 2012-09-11 11:55 -0400
                Re: Comparing strings from the back? Chris Angelico <rosuav@gmail.com> - 2012-09-11 00:26 +1000
                Re: Comparing strings from the back? Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2012-09-10 14:32 +0000
                Re: Comparing strings from the back? Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2012-09-10 14:43 +0000
                Re: Comparing strings from the back? Chris Angelico <rosuav@gmail.com> - 2012-09-11 00:56 +1000
                Re: Comparing strings from the back? Duncan Booth <duncan.booth@invalid.invalid> - 2012-09-11 09:41 +0000
                Re: Comparing strings from the back? Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2012-09-06 12:04 +0100
                Re: Comparing strings from the back? Steve Howell <showell30@yahoo.com> - 2012-09-14 17:51 -0700
                Re: Comparing strings from the back? Roy Smith <roy@panix.com> - 2012-09-06 08:13 -0400
                Re: Comparing strings from the back? Chris Angelico <rosuav@gmail.com> - 2012-09-06 22:29 +1000
                Re: Comparing strings from the back? Johannes Bauer <dfnsonfsduifb@gmx.de> - 2012-09-06 15:43 +0200
                Re: Comparing strings from the back? Dave Angel <d@davea.name> - 2012-09-06 10:23 -0400
                Re: Comparing strings from the back? Johannes Bauer <dfnsonfsduifb@gmx.de> - 2012-09-06 16:33 +0200
                Re: Comparing strings from the back? Johannes Bauer <dfnsonfsduifb@gmx.de> - 2012-09-06 16:42 +0200
                Re: Comparing strings from the back? Dave Angel <d@davea.name> - 2012-09-06 11:54 -0400
                Re: Comparing strings from the back? Johannes Bauer <dfnsonfsduifb@gmx.de> - 2012-09-06 16:34 +0200
                Re: Comparing strings from the back? Gelonida N <gelonida@gmail.com> - 2012-09-08 17:50 +0200
                Re: Comparing strings from the back? Johannes Bauer <dfnsonfsduifb@gmx.de> - 2012-09-06 15:37 +0200
                Re: Comparing strings from the back? Chris Angelico <rosuav@gmail.com> - 2012-09-07 00:39 +1000
                Re: Comparing strings from the back? Johannes Bauer <dfnsonfsduifb@gmx.de> - 2012-09-06 17:36 +0200
                Re: Comparing strings from the back? Johannes Bauer <dfnsonfsduifb@gmx.de> - 2012-09-06 17:44 +0200
                Re: Comparing strings from the back? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-09-07 04:07 +0000
  Re: Comparing strings from the back? Terry Reedy <tjreedy@udel.edu> - 2012-09-04 01:13 -0400
  Re: Comparing strings from the back? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-09-04 08:56 +0100
  Re: Comparing strings from the back? Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2012-09-04 11:58 +0200
  Re: Comparing strings from the back? Neil Hodgson <nhodgson@iinet.net.au> - 2012-09-05 12:18 +1000
    Re: Comparing strings from the back? MRAB <python@mrabarnett.plus.com> - 2012-09-05 03:39 +0100
    Re: Comparing strings from the back? Roy Smith <roy@panix.com> - 2012-09-04 22:48 -0400
    Re: Comparing strings from the back? Johannes Bauer <dfnsonfsduifb@gmx.de> - 2012-09-05 16:33 +0200
  Re: Comparing strings from the back? Peter Otten <__peter__@web.de> - 2012-09-05 10:29 +0200
  Re: Comparing strings from the back? Chris Angelico <rosuav@gmail.com> - 2012-09-05 18:33 +1000
  Re: Comparing strings from the back? Peter Otten <__peter__@web.de> - 2012-09-05 11:48 +0200
  Re: Comparing strings from the back? Peter Otten <__peter__@web.de> - 2012-09-05 17:45 +0200
  Re: Comparing strings from the back? Dan Goodman <dg.gmane@thesamovar.net> - 2012-09-10 18:07 +0200
  Re: Comparing strings from the back? Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2012-09-10 16:33 +0000
  Re: Comparing strings from the back? Dan Goodman <dg.gmane@thesamovar.net> - 2012-09-10 19:32 +0200
  Re: Comparing strings from the back? Dan Goodman <dg.gmane@thesamovar.net> - 2012-09-10 19:44 +0200
  Re: Comparing strings from the back? Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2012-09-10 21:52 +0000

csiph-web