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

Groups > comp.lang.python > #44089

Re: List Count

Path csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eu.feeder.erje.net!xlned.com!feeder7.xlned.com!news2.euro.net!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.039
X-Spam-Evidence '*H*': 0.92; '*S*': 0.00; 'method.': 0.07; 'sys': 0.07; 'builtin': 0.09; 'cc:addr:python-list': 0.11; '(given': 0.16; '(say': 0.16; 'boolean': 0.16; 'lists).': 0.16; 'numpy': 0.16; 'slice.': 0.16; 'subclass': 0.16; 'elements': 0.16; 'wrote:': 0.18; 'bit': 0.19; 'items.': 0.19; 'seems': 0.21; '>>>': 0.22; 'memory': 0.22; 'import': 0.22; 'cc:addr:python.org': 0.22; 'byte': 0.24; 'decide': 0.24; 'mon,': 0.24; 'regardless': 0.24; 'cc:2**0': 0.24; 'cc:no real name:2**0': 0.24; 'possibly': 0.26; 'values': 0.27; 'header:In-Reply-To:1': 0.27; 'tried': 0.27; 'function': 0.29; 'array': 0.29; 'compared': 0.30; 'fastest': 0.30; 'message-id:@mail.gmail.com': 0.30; '+0100,': 0.31; "d'aprano": 0.31; 'factor': 0.31; 'overhead': 0.31; 'steven': 0.31; 'becomes': 0.33; 'advice': 0.35; 'agree': 0.35; 'received:209.85': 0.35; 'received:209.85.220': 0.35; 'hundreds': 0.35; 'operations': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'add': 0.35; 'grateful': 0.36; 'subject:List': 0.36; 'useful': 0.36; 'list': 0.37; 'list.': 0.37; 'received:209': 0.37; 'issue': 0.38; 'expect': 0.39; 'does': 0.39; 'enough': 0.39; 'system.': 0.39; 'easy': 0.60; 'full': 0.61; 'offer': 0.62; 'high': 0.63; 'believe': 0.68; 'price': 0.69; 'allocation': 0.74; 'lack': 0.78; 'costly': 0.84; 'oscar': 0.84; 'items,': 0.91; 'system:': 0.91; '30%': 0.93; 'suffer': 0.93; '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=HJNZ/uFB+gmRglfAgrtQunl0QNFfOx618Dfj3X2l24s=; b=W5V0LlT/o2WpaVuPaG6QNXTuTFaOAAkgM+M16cXQ9hc/I2pfGsobl5XTg3UqFOae3p tI/FNS1Z05cV6Y0s4XNNik1t1jO+nCxvLX4BOVZmTRGQYf/7+SKjECzINVggHLE3exVM h3g158UuAaeKb5oc1IOpqKZp9+xybTXvY6qzoup1aISnng3N0pxvAPEH2meKKabYte4j uYkJT7xzgoF7kK2R7SuFyA/AMRk5C3ov8BTQpZDepX76d1k+zQmSzzIhr0YpDzIJO6uj fVmlskzoFakkDr08aLlRyNPNvwO8/Mt4yS9iiMaB5ekXTU0ILQ36nMuK5UJfPYbd4tOW 3VPg==
X-Received by 10.52.93.78 with SMTP id cs14mr16883864vdb.17.1366643679962; Mon, 22 Apr 2013 08:14:39 -0700 (PDT)
MIME-Version 1.0
In-Reply-To <517545F7.5090209@nowhere.org>
References <sridnffI6YhxuOjMnZ2dnUVZ7tSdnZ2d@brightview.co.uk> <5175377f$0$29977$c3e8da3$5496439d@news.astraweb.com> <517545F7.5090209@nowhere.org>
From Oscar Benjamin <oscar.j.benjamin@gmail.com>
Date Mon, 22 Apr 2013 16:14:19 +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.927.1366644147.3114.python-list@python.org> (permalink)
Lines 56
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1366644147 news.xs4all.nl 2202 [2001:888:2000:d::a6]:53494
X-Complaints-To abuse@xs4all.nl
Xref csiph.com comp.lang.python:44089

Show key headers only | View raw

On 22 April 2013 15:15, Blind Anagram <blindanagram@nowhere.org> wrote:
> On 22/04/2013 14:13, Steven D'Aprano wrote:
>> On Mon, 22 Apr 2013 12:58:20 +0100, Blind Anagram wrote:
>>
>>> I would be grateful for any advice people can offer on the fastest way
>>> to count items in a sub-sequence of a large list.
>>>
>>> I have a list of boolean values that can contain many hundreds of
>>> millions of elements for which I want to count the number of True values
>>> in a sub-sequence, one from the start up to some value (say hi).
>>>
>>> I am currently using:
>>>
>>>    sieve[:hi].count(True)
>>>
>>> but I believe this may be costly because it copies a possibly large part
>>> of the sieve.
[snip]
>
> 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%.

Have you tried using numpy? I find that it reduces the memory required
to store a list of bools by a factor of 4 on my 32 bit system. I would
expect that to be a factor of 8 on a 64 bit system:

>>> import sys
>>> a = [True] * 1000000
>>> sys.getsizeof(a)
4000036
>>> import numpy
>>> a = numpy.ndarray(1000000, bool)
>>> sys.getsizeof(a)  # This does not include the data buffer
40
>>> a.nbytes
1000000

The numpy array also has the advantage that slicing does not actually
copy the data (as has already been mentioned). On this system slicing
a numpy array has a 40 byte overhead regardless of the size of the
slice.

> I agree that this is not a big issue but it seems to me a high price to
> pay for the lack of a sieve.count(value, limit), which I feel is a
> useful function (given that memoryview operations are not available for
> lists).

It would be very easy to subclass list and add this functionality in
cython if you decide that you do need a builtin method.


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