Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.mixmin.net!newsreader4.netcologne.de!news.netcologne.de!xlned.com!feeder1.xlned.com!newsfeed.xs4all.nl!newsfeed4a.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.001 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'else:': 0.03; 'operator': 0.03; '"the': 0.07; 'duplicate': 0.07; 'string': 0.09; '")': 0.09; 'skip:2 30': 0.09; 'slow.': 0.09; 'trailing': 0.09; 'try:': 0.09; 'cc:addr:python-list': 0.11; 'python': 0.11; 'def': 0.12; '"in"': 0.16; 'collections': 0.16; 'repetitions': 0.16; 'space)': 0.16; 'subject:slow': 0.16; 'surprises': 0.16; 'to:addr:python.list': 0.16; 'to:addr:tim.thechases.com': 0.16; 'to:name:tim chase': 0.16; 'variations': 0.16; 'wrote:': 0.18; 'wed,': 0.18; 'seems': 0.21; '>>>': 0.22; 'import': 0.22; 'aug': 0.22; 'cc:addr:gmail.com': 0.22; 'cc:addr:python.org': 0.22; 'cc:2**1': 0.23; '>>>': 0.24; 'switched': 0.24; 'versions': 0.24; 'least': 0.26; 'header:In-Reply-To:1': 0.27; 'chris': 0.29; 'tim': 0.29; 'words': 0.29; 'bigger': 0.30; 'message-id:@mail.gmail.com': 0.30; '"': 0.31; 'chase': 0.31; 'keyerror:': 0.31; 'provided,': 0.31; 'reduced': 0.31; 'option': 0.32; 'running': 0.33; '"the': 0.34; 'received:74.125.82': 0.34; 'except': 0.35; 'received:google.com': 0.35; 'version': 0.36; '8bit%:9': 0.36; 'found.': 0.36; 'words,': 0.36; 'subject:?': 0.36; 'skip:4 10': 0.37; 'two': 0.37; 'skip:& 10': 0.38; 'pm,': 0.38; 'rather': 0.38; 'expect': 0.39; 'received:74.125': 0.39; 'skip:b 40': 0.39; 'skip:n 30': 0.60; 'black': 0.61; 'skip:t 30': 0.61; 'skip:* 10': 0.61; 'times': 0.62; 'skip:6 10': 0.63; 'skip:n 10': 0.64; 'more': 0.64; 'skip:1 20': 0.65; 'here': 0.66; 'presented': 0.69; 'increase': 0.74; 'skip:n 40': 0.81; 'subject:over': 0.84 X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=/vymTEUVSCTB7c/4F+MHUMalPFcF/VJYHhHFl6iOXSc=; b=SK1PpIf5YF3kYLhhC1ad9ry1DBbN3e4SCl+4VzwGeoLv6ODGZhS3d22kwHW+41BAXg UMGY/LrQq3FTBYUMQ8/M3WgsG5DumlWa+9tUrZZRydELuGJ1l/uAMyVqOtsbQPjH7Ril 0P3wMg0bZITk5vf8SdIlJtyeOLuzRg089iJDNTk6ujijy/HRx1ApsHTVd4hslWZddURc VR+sBCoi575jWSwrlv1CVQgX/LRYH5+t/lWjlM47X6ASD+K+0l5Qd2dsDiGSA+8fARGr 6R5/8hltCDfXSdNUrHzUPR6c2q3rfpWI69Lm/86NSXCyJwgRU+/LxYSICVz0KXiAAcmz +r3w== X-Gm-Message-State: ALoCoQlYLe15u1mXdKxHrLYVzRMKEGjAvs56Fp7P+h+KcPGzYlIic2qA5WLpGeeFhn69K+gFHzXZ X-Received: by 10.180.91.70 with SMTP id cc6mr916298wib.66.1409176279465; Wed, 27 Aug 2014 14:51:19 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: <20140827162157.72e20091@bigbox.christie.dr> References: <20140827162157.72e20091@bigbox.christie.dr> From: Chris Kaynor Date: Wed, 27 Aug 2014 14:50:59 -0700 Subject: Re: iterating over strings seems to be really slow? To: Tim Chase Content-Type: multipart/alternative; boundary=f46d0438edd79057be0501a36b35 Cc: "python-list@python.org" X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 262 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1409176281 news.xs4all.nl 2886 [2001:888:2000:d::a6]:46171 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:77163 --f46d0438edd79057be0501a36b35 Content-Type: text/plain; charset=UTF-8 On Wed, Aug 27, 2014 at 1:53 PM, Rodrick Brown wrote: def wc1(): > word="" > m={} > for c in s: > if c != " ": > word += c > else: > if m.has_key(word): > m[word] += 1 > else: > m[word] = 1 > word="" > return(m) > def wc2(): > m={} > for c in s.split(): > if m.has_key(c): > m[c] += 1 > else: > m[c] = 1 > return(m) On Wed, Aug 27, 2014 at 2:21 PM, Tim Chase wrote: > > The thing that surprises me is that using collections.Counter() and > collections.defaultdict(int) are also slower than your wc2(): > > from collections import defaultdict, Counter > > def wc3(): > return Counter(s.split()) > > def wc4(): > m = defaultdict(int) > for c in s.split(): > m[c] += 1 > return m > I ran a couple more experiments, and, at least on my machine, it has to do with the number of duplicate words found. I also added two more variations of my own: def wc5(s): # I expect this one to be slow. m = {} for c in s.split(): m.setdefault(c, 0) m[c] += 1 return m def wc6(s): # This one might be better than any other option presented so far. m = {} for c in s.split(): try: m[c] += 1 except KeyError: m[c] = 1 return m I also switched the OP's versions to use the "in" operator rather than has_key, as I am running Python 3.4.1. With the same dataset (plus a trailing space) the OP provided, here are my times: (s = "The black cat jump over the bigger black cat ") >>> timeit.timeit("wc1(s)", setup=setup, number=1000000) 6.076951338314008 *>>> timeit.timeit("wc2(s)", setup=setup, number=1000000)* *2.451220378346954* >>> timeit.timeit("wc3(s)", setup=setup, number=1000000) 5.249674617410577 >>> timeit.timeit("wc4(s)", setup=setup, number=1000000) 3.531042215121076 >>> timeit.timeit("wc5(s)", setup=setup, number=1000000) 3.4734603842861205 >>> timeit.timeit("wc6(s)", setup=setup, number=1000000) 4.322543365103378 When I increase the data set by multipling the OP's string 1000 times (s = "The black cat jump over the bigger black cat "*1000), here are the times (I reduced the number of repetitions to keep the time reasonable): >>> timeit.timeit("wc1(s)", setup=setup, number=1000) 5.807871555058417 >>> timeit.timeit("wc2(s)", setup=setup, number=1000) 2.3245083748933535 *>>> timeit.timeit("wc3(s)", setup=setup, number=1000)* *1.5722138905703211* >>> timeit.timeit("wc4(s)", setup=setup, number=1000) 1.901478857657942 >>> timeit.timeit("wc5(s)", setup=setup, number=1000) 3.065888476414475 >>> timeit.timeit("wc6(s)", setup=setup, number=1000) 2.0125233934956217 It seems that with a large number of duplicate words, the counter version is the best, however with fewer duplicates, the contains check is better. Chris --f46d0438edd79057be0501a36b35 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
On W= ed, Aug 27, 2014 at 1:53 PM, Rodrick Brown=C2=A0<rodrick.brown@gmail= .com>=C2=A0wrote:


def wc1():
    word=3D""
    m=3D{}
    for c in s:
        if c !=3D " ":=20
            word +=3D c
        else:
            if m.has_key(word):
                m[word] +=3D 1
            else:
                m[word] =3D 1=20
            word=3D""
    return(m)
=C2=A0
def wc2():=20
    m=3D{}
    for c in s.split():
        if m.has_key(c):
            m[c] +=3D 1
        else:
            m[c] =3D 1=20
    return(m)

On Wed, = Aug 27, 2014 at 2:21 PM, Tim Chase <python.list@tim.thechases.= com> wrote:
The thing that surprises me is that using collections.Counter() and
collections.defaultdict(int) are also slower than your wc2():

from collections import defaultdict, Counter

def wc3():
=C2=A0 =C2=A0 return Counter(s.split())

def wc4():
=C2=A0 =C2=A0 m =3D defaultdict(int)
=C2=A0 =C2=A0 for c in s.split():
=C2=A0 =C2=A0 =C2=A0 =C2=A0 m[c] +=3D 1
=C2=A0 =C2=A0 return m

I ran a couple more experi= ments, and, at least on my machine, it has to do with the number of duplica= te words found. I also added two more variations of my own:

def wc5(s):= # I expect this one to be slow.
m =3D {}
for c in s.split(= ):
m.setdefault(c, 0)
m[c] +=3D 1
return m

def wc6(s):= # This one might be better than any other option presented so far.
m =3D {}
for c in s.split():
try:
m[c] +=3D 1
except KeyError:
m[c] =3D 1
<= span class=3D"" style=3D"white-space:pre"> return m

I also swit= ched the OP's versions to use the "in" operator rather than h= as_key, as I am running Python 3.4.1.

With the sam= e dataset (plus a trailing space) the OP provided, here are my times: (s = =3D "The black cat jump over the bigger black cat ")
>>> timeit.timeit("wc1(= s)", setup=3Dsetup, number=3D1000000)
6.076951338314008
>>> timeit.timeit("wc2(s)", setup=3Dsetup, number=3D1= 000000)
2.451220378346954
>>> timei= t.timeit("wc3(s)", setup=3Dsetup, number=3D1000000)
5.2= 49674617410577
>>> timeit.timeit("wc4(s)", setup=3Dsetup, number= =3D1000000)
3.531042215121076
>>> timeit.timei= t("wc5(s)", setup=3Dsetup, number=3D1000000)
3.47346038= 42861205
>>> timeit.timeit("wc6(s)", setup=3Dsetup, number= =3D1000000)
4.322543365103378

W= hen I increase the data set by multipling the OP's string 1000 times (s= =3D "The black cat jump over the bigger black cat "*1000), here = are the times (I reduced the number of repetitions to keep the time reasona= ble):
>>> timeit.timeit("wc1(s)", setup=3Dsetup, num= ber=3D1000)
5.807871555058417
>= ;>> timeit.timeit("wc2(s)", setup=3Dsetup, number=3D1000)
2.3245083748933535
>>> tim= eit.timeit("wc3(s)", setup=3Dsetup, number=3D1000)
1.5722138905703211
>>> time= it.timeit("wc4(s)", setup=3Dsetup, number=3D1000)
1.901478857657942
>>> timeit.= timeit("wc5(s)", setup=3Dsetup, number=3D1000)
3.065888476414475
>>> timeit.timeit("= wc6(s)", setup=3Dsetup, number=3D1000)
2.0125233934956217

It seems that with a large number of d= uplicate words, the counter version is the best, however with fewer duplica= tes, the contains check is better.

Chris
--f46d0438edd79057be0501a36b35--