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

Groups > comp.lang.python > #44171

Re: List Count

Path csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!rt.uk.eu.org!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path <oscar.j.benjamin@gmail.com>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.111
X-Spam-Level *
X-Spam-Evidence '*H*': 0.78; '*S*': 0.00; 'else:': 0.03; 'arrays': 0.09; 'method,': 0.09; 'method:': 0.09; 'cc:addr:python-list': 0.11; 'def': 0.12; 'anyway': 0.14; 'algorithmic': 0.16; 'optimised': 0.16; 'url:cf': 0.16; 'language': 0.16; 'wrote:': 0.18; 'trying': 0.19; 'items.': 0.19; '>>>': 0.22; 'memory': 0.22; 'cc:addr:python.org': 0.22; 'bytes': 0.24; 'choices': 0.24; 'comparing': 0.24; 'mon,': 0.24; 'cc:2**0': 0.24; 'cc:no real name:2**0': 0.24; 'possibly': 0.26; 'asking': 0.27; 'header:In- Reply-To:1': 0.27; 'array': 0.29; 'scale': 0.29; 'compared': 0.30; 'fastest': 0.30; 'message-id:@mail.gmail.com': 0.30; 'url:wiki': 0.31; '+0100,': 0.31; "d'aprano": 0.31; 'factor': 0.31; 'large.': 0.31; 'overhead': 0.31; 'staying': 0.31; 'steven': 0.31; 'url:wikipedia': 0.31; 'lists': 0.32; 'another': 0.32; 'becomes': 0.33; 'copying': 0.34; 'could': 0.34; 'advice': 0.35; 'received:209.85': 0.35; 'received:209.85.220': 0.35; 'skip:s 30': 0.35; 'computing': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'really': 0.36; 'false': 0.36; 'subject:List': 0.36; 'whilst': 0.36; 'doing': 0.36; 'url:org': 0.36; 'should': 0.36; 'list': 0.37; 'list.': 0.37; 'received:209': 0.37; 'performance': 0.37; 'problems': 0.38; 'lists.': 0.38; 'issue': 0.38; 'fact': 0.38; 'rather': 0.38; 'enough': 0.39; 'either': 0.39; 'algorithms': 0.60; 'full': 0.61; 'simply': 0.61; 'simple': 0.61; "you're": 0.61; "you've": 0.63; 'different': 0.65; 'design.': 0.68; 'said:': 0.68; 'overall': 0.69; 'evaluate': 0.72; 'allocation': 0.74; 'obvious': 0.74; 'discover': 0.82; 'choices.': 0.84; 'n):': 0.84; 'oscar': 0.84; 'items,': 0.91; '30%': 0.93; 'suffer': 0.93; 'url:80': 0.93; 'dream': 0.95; '2013': 0.98
DKIM-Signature v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=x-received:mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; bh=vfb8MjHYpwXL57Tmvar4ZsDorlHCaW9zllQFjStB744=; b=hepswYyHLO4/2z0stFkqncJB5Gk7s/6JfaTPQEuzwpDRhfOXtHj9+A1h+z02/DANQ4 e4BuMuELFZMcZhEkNdrfITCfLXNXKbcReTfsIKtdSzF9b+QtWmorcF+Pl4tZtFGqUk4J JvK1cNJS1tlUgOgZ3DKO52cF1X6eG5VMSoK091B0Jq8kMRs2W133UZwSu4CnuaBl0qJh xQKrPIpclstJMGJNhrgA6ffCBToT4yhjkF6zIo2LrVcPICBDqml9uSzKWchPvSEyb0Co a3L7dEjy160YwttYnogVr36I2+/y4A/YdC3Avo6RAy2b+B0pyEYwgtvN77n4Z/oTydLe G3Qg==
X-Received by 10.58.180.196 with SMTP id dq4mr6090550vec.10.1366715333926; Tue, 23 Apr 2013 04:08:53 -0700 (PDT)
MIME-Version 1.0
In-Reply-To <e4KdnXzMesF-r-vMnZ2dnUVZ8rWdnZ2d@brightview.co.uk>
References <sridnffI6YhxuOjMnZ2dnUVZ7tSdnZ2d@brightview.co.uk> <5175377f$0$29977$c3e8da3$5496439d@news.astraweb.com> <517545F7.5090209@nowhere.org> <5175c12f$0$29977$c3e8da3$5496439d@news.astraweb.com> <e4KdnXzMesF-r-vMnZ2dnUVZ8rWdnZ2d@brightview.co.uk>
From Oscar Benjamin <oscar.j.benjamin@gmail.com>
Date Tue, 23 Apr 2013 12:08:32 +0100
Subject Re: List Count
To Blind Anagram <blindanagram@nowhere.org>
Content-Type text/plain; charset=ISO-8859-1
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 <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.967.1366715343.3114.python-list@python.org> (permalink)
Lines 56
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1366715343 news.xs4all.nl 2236 [2001:888:2000:d::a6]:42416
X-Complaints-To abuse@xs4all.nl
Xref csiph.com comp.lang.python:44171

Show key headers only | View raw

On 23 April 2013 08:05, Blind Anagram <blindanagram@nowhere.org> wrote:
> On 23/04/2013 00:01, Steven D'Aprano wrote:
>> On Mon, 22 Apr 2013 15:15:19 +0100, Blind Anagram wrote:
>>
>>> But when using a sub-sequence, I do suffer a significant reduction in
>>> speed for a count when compared with count on the full list.  When the
>>> list is small enough not to cause memory allocation issues this is about
>>> 30% on 100,000,000 items.  But when the list is 1,000,000,000 items, OS
>>> memory allocation becomes an issue and the cost on my system rises to
>>> over 600%.
[snip]
>>
>> Another solution might be to use arrays rather than lists. Since your
>> sieve list is homogeneous, you could possibly use an array of 1 or 0
>> bytes rather than a list of True or False bools. That would reduce the
>> memory overhead by a factor of four, and similarly reduce the overhead of
>> any copying:
>
> I did a lot of work comparing the overall performance of the sieve when
> using either lists or arrays and I found that lists were a lot faster
> for the majority use case when the sieve is not large.

Okay, now I understand. I thought you were trying to optimise for
large lists, but in fact you have already optimised for small lists.
As a result you have made algorithmic choices that don't scale very
well. Since you're still concerned about performance on small lists
you don't want to rethink those choices. Instead you want a
micro-optimisation that would compensate for them.

Elsewhere you said:

> I would not dream of doing this job by copying a slice in any other
> language that I have used so I was simply asking for advice to discover
> whether this copy could be avoided whilst staying with the simple sieve
> design.

So you already knew that there would be problems with this method, but
you've chosen it anyway since it turned out to be fastest for small
lists. You could always just do a different thing when the list is
large:

def pi(self, n):
  if n < 1000000:
    return self.indicator[:n].sum()
  else:
    return sum(itertools.islice(self.indicator, n))

However, if you really want to improve performance in computing pi(n)
for large n you should just use one of the existing algorithms having
sublinear space/time complexity. These also use evaluate pi(n) with
sieves but the sieve only needs to be as big as sqrt(n) rather than n
for the obvious method:
http://en.wikipedia.org/wiki/Prime-counting_function#Algorithms_for_evaluating_.CF.80.28x.29


Oscar

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

Thread

List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 12:58 +0100
  Re: List Count Dave Angel <davea@davea.name> - 2013-04-22 08:51 -0400
    Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 14:03 +0100
    Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 14:03 +0100
  Re: List Count Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-04-22 13:13 +0000
    Re: List Count Skip Montanaro <skip@pobox.com> - 2013-04-22 08:57 -0500
    Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 15:15 +0100
      Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-22 16:14 +0100
        Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 16:50 +0100
          Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-22 17:06 +0100
            Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 17:38 +0100
              Re: List Count Skip Montanaro <skip@pobox.com> - 2013-04-22 12:48 -0500
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 20:22 +0100
              Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-22 21:18 +0100
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 22:25 +0100
                Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-23 00:06 +0100
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-23 07:45 +0100
                Re: List Count Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-04-22 23:28 +0000
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-23 08:00 +0100
              Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-22 22:03 +0100
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 22:32 +0100
                Re: List Count Dave Angel <davea@davea.name> - 2013-04-22 21:47 -0400
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-23 08:02 +0100
            Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 17:38 +0100
        Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 16:50 +0100
      Re: List Count Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-04-22 23:01 +0000
        Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-23 08:05 +0100
          Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-23 12:08 +0100
            Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-23 12:45 +0100
              Re: List Count Terry Jan Reedy <tjreedy@udel.edu> - 2013-04-23 15:01 -0400
          Re: List Count Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-04-23 14:49 +0000
            Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-23 17:57 +0100
              Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-23 18:45 +0100
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-23 19:30 +0100
                Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-23 20:16 +0100
              Re: List Count Terry Jan Reedy <tjreedy@udel.edu> - 2013-04-23 16:00 -0400
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-23 21:41 +0100
              Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-23 21:38 +0100
              Re: List Count Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-04-24 01:59 +0000
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-24 10:01 +0100
  Re: List Count Peter Otten <__peter__@web.de> - 2013-04-22 15:22 +0200
  Re: List Count 88888 Dihedral <dihedral88888@googlemail.com> - 2013-04-22 06:36 -0700

csiph-web