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

Groups > comp.lang.python > #44132

Re: List Count

Return-Path <davea@davea.name>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.076
X-Spam-Evidence '*H*': 0.85; '*S*': 0.00; 'indicating': 0.07; 'indices': 0.07; 'plenty': 0.07; 'counting': 0.09; 'function,': 0.09; 'integers': 0.09; 'python': 0.11; '(and,': 0.16; 'algorithmic': 0.16; 'arises.': 0.16; 'benjamin': 0.16; 'cached': 0.16; 'count.': 0.16; 'integers,': 0.16; 'interval.': 0.16; 'nonzero': 0.16; 'storing': 0.16; 'trade-offs': 0.16; 'wrote:': 0.18; 'trying': 0.19; '>>>': 0.22; 'memory': 0.22; 'creating': 0.23; 'header:User-Agent:1': 0.23; 'certainly': 0.24; 'replace': 0.24; 'question': 0.24; 'sort': 0.25; 'values': 0.27; 'header:In- Reply-To:1': 0.27; 'function': 0.29; 'correct': 0.29; 'wonder': 0.29; '(maybe': 0.31; '>>>>': 0.31; 'constant': 0.31; 'overhead': 0.31; 'class': 0.32; 'probably': 0.32; 'themselves': 0.32; 'implemented': 0.33; 'not.': 0.33; 'sense': 0.34; 'objects': 0.35; 'but': 0.35; 'there': 0.35; 'false': 0.36; 'subject:List': 0.36; 'doing': 0.36; 'should': 0.36; 'application': 0.37; 'two': 0.37; 'list': 0.37; 'list.': 0.37; 'performance': 0.37; 'to:addr:python- list': 0.38; 'issue': 0.38; 'list,': 0.38; 'fact': 0.38; 'pm,': 0.38; 'realize': 0.39; 'to:addr:python.org': 0.39; 'how': 0.40; 'new': 0.61; 'numbers': 0.61; 'simply': 0.61; 'simple': 0.61; "you're": 0.61; 'first': 0.61; 'save': 0.62; "you'll": 0.62; 'sum': 0.64; 'more': 0.64; 'different': 0.65; 'within': 0.65; 'here': 0.66; 'between': 0.67; 'received:74.208': 0.68; 'obvious': 0.74; 'prime': 0.74; 'increase': 0.74; 'potentially': 0.81; 'discover': 0.82; 'density': 0.84; 'oscar': 0.84; 'quicker': 0.84; 'received:74.208.4.194': 0.84; 'approach.': 0.91; 'indicator': 0.91; '2013': 0.98
Date Mon, 22 Apr 2013 21:47:52 -0400
From Dave Angel <davea@davea.name>
User-Agent Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130329 Thunderbird/17.0.5
MIME-Version 1.0
To python-list@python.org
Subject Re: List Count
References <sridnffI6YhxuOjMnZ2dnUVZ7tSdnZ2d@brightview.co.uk> <5175377f$0$29977$c3e8da3$5496439d@news.astraweb.com> <517545F7.5090209@nowhere.org> <mailman.927.1366644147.3114.python-list@python.org> <51755C38.4000204@nowhere.org> <mailman.929.1366646795.3114.python-list@python.org> <51756769.20206@nowhere.org> <CAHVvXxSVt843jVvoXv1J8zD2Ghgdu2taPnr0vawVPCQR=cePtA@mail.gmail.com> <mailman.938.1366664643.3114.python-list@python.org> <MOmdnVeRh4PiMejMnZ2dnUVZ7t6dnZ2d@brightview.co.uk>
In-Reply-To <MOmdnVeRh4PiMejMnZ2dnUVZ7t6dnZ2d@brightview.co.uk>
Content-Type text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding 7bit
X-Provags-ID V02:K0:Xna/GK2znUl+lW5nJWP0br11OstQ/0d98Rg8CrzhtTY X9j7xLsg5E3MeYP5tYCCZfXIc3JmuVcdH4R4ViyWwk9HSBtilA ETz8+XGMEBkVpWzSoIE5ssA2LtjxZsybpZYlAE3XcXh0K++X9X J6ID8cXroBywiK75j37PHk/ySI4QYMu6CfK7LbobV14n7oZwXy bGBwirKvI59avjBZyicwkcjPPNcqwduAW82ffoOQLnOLgF7cak frkRMR0ELNtKEM3dAervRgUPuxI0xw1ZMbBrk+kSSDcbAAp5cm 8Zthrto/mJM0anJ2X5Z6R1C8wY/DWm55LkUCGFZvQQBISUT8g= =
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.946.1366681733.3114.python-list@python.org> (permalink)
Lines 49
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1366681733 news.xs4all.nl 2213 [2001:888:2000:d::a6]:53776
X-Complaints-To abuse@xs4all.nl
Path csiph.com!usenet.pasdenom.info!news.stben.net!border3.nntp.ams.giganews.com!border1.nntp.ams.giganews.com!nntp.giganews.com!xlned.com!feeder5.xlned.com!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Xref csiph.com comp.lang.python:44132

Show key headers only | View raw

On 04/22/2013 05:32 PM, Blind Anagram wrote:
> On 22/04/2013 22:03, Oscar Benjamin wrote:
>> On 22 April 2013 21:18, Oscar Benjamin <oscar.j.benjamin@gmail.com> wrote:
>>> On 22 April 2013 17:38, Blind Anagram <blindanagram@nowhere.org> wrote:
>>>> On 22/04/2013 17:06, Oscar Benjamin wrote:
>>>>
>>>>> I don't know what your application is but I would say that my first
>>>>> port of call here would be to consider a different algorithmic
>>>>> approach. An obvious question would be about the sparsity of this data
>>>>> structure. How frequent are the values that you are trying to count?
>>>>> Would it make more sense to store a list of their indices?
>>>>
>>>> Actually it is no more than a simple prime sieve implemented as a Python
>>>> class (and, yes, I realize that there are plenty of these around).
>>>
>>> If I understand correctly, you have a list of roughly a billion
>>> True/False values indicating which integers are prime and which are
>>> not. You would like to discover how many prime numbers there are
>>> between two numbers a and b. You currently do this by counting the
>>> number of True values in your list between the indices a and b.
>>>
>>> If my description is correct then I would definitely consider using a
>>> different algorithmic approach. The density of primes from 1 to 1
>>> billlion is about 5%. Storing the prime numbers themselves in a sorted
>>> list would save memory and allow a potentially more efficient way of
>>> counting the number of primes within some interval.
>>
>> In fact it is probably quicker if you don't mind using all that memory
>> to just store the cumulative sum of your prime True/False indicator
>> list. This would be the prime counting function pi(n). You can then
>> count the primes between a and b in constant time with pi[b] - pi[a].
>
> I did wonder whether, after creating the sieve, I should simply go
> through the list and replace the True values with a count.  This would
> certainly speed up the prime count function, which is where the issue
> arises.  I will try this and see what sort of performance trade-offs
> this involves.
>

By doing that replacement, you'd increase memory usage manyfold (maybe 
3:1, I don't know).  As long as you're only using bools in the list, you 
only have the list overhead to consider, because all the objects 
involved are already cached (True and False exist only once each).  If 
you have integers, you'll need a new object for each nonzero count.



-- 
DaveA

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