Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder2.hal-mli.net!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Date: Mon, 22 Apr 2013 17:38:01 +0100
From: Blind Anagram <blindanagram@nowhere.org>
User-Agent: Mozilla/5.0 (Windows NT 6.2; WOW64; rv:17.0) Gecko/20130328 Thunderbird/17.0.5
MIME-Version: 1.0
Newsgroups: comp.lang.python
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>
In-Reply-To: <mailman.929.1366646795.3114.python-list@python.org>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Precedence: list
Message-ID: <mailman.931.1366648708.3114.python-list@python.org>
Lines: 48
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:44096

On 22/04/2013 17:06, Oscar Benjamin wrote:
> On 22 April 2013 16:50, Blind Anagram <blindanagram@nowhere.org> wrote:
>>>
>>> It would be very easy to subclass list and add this functionality in
>>> cython if you decide that you do need a builtin method.
> [snip]
>>
>> But I was really wondering if there was a simple solution that worked
>> without people having to add libraries to their basic Python installations.
> 
> There are simple solutions and some have already been listed. You are
> attempting to push your program to the limit of your hardware
> capabilities and it's natural that in a high-level language you'll
> often want special libraries for that.

Hi Oscar

Yes, but it is a tribute to Python that I can do this quite fast for
huge lists provided that I only count on the full list.

And, unless I have completely misunderstood Python internals, it would
probably be just as fast on a sub-sequence if I had a list.count(value,
limit) function (however, I admit that I could be wrong here since the
fact that count on lists does not offer this may mean that it is not as
easy to implement as it might seem).

> 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 the problem needs to be solved the way that you are currently doing
> it and the available methods are not fast enough then you will need to
> consider additional libraries.
>>
>> As I have never tried building an extension with cython, I am inclined
>> to try this as a learning exercise if nothing else.
> 
> I definitely recommend this over writing a C extension directly.

Thanks again - I will definitely look at this.

   Brian