List Count
Blind Anagram
blindanagram at nowhere.org
Tue Apr 23 02:45:58 EDT 2013
On 23/04/2013 00:06, Oscar Benjamin wrote:
> On 22 April 2013 22:25, Blind Anagram <blindanagram at nowhere.org> wrote:
>> On 22/04/2013 21:18, Oscar Benjamin wrote:
>>> On 22 April 2013 17:38, Blind Anagram <blindanagram at nowhere.org> wrote:
>>
>> I also wondered whether I had missed any obvious way of avoiding the
>> slicing cost (intellectually it seemed wrong to me to have to copy the
>> list in order to count items within it).
> [snip]
>>
>> I have looked at solutions based on listing primes and here I have found
>> that they are very much slower than my existing solution when the sieve
>> is not large (which is the majority use case).
>
> What matters is not so much the size of the sieve but the size of the
> interval you want to query. You say that slicing cost is somehow
> significant which suggests to me that it's not a small interval. An
> approach using a sorted list of primes and bisect would have a cost
> that is independent of the size of the interval (and depends only
> logarithmically on the size of the sieve).
The issue here is that the prime number count is only one of the
features of the class so I would have to essentially rewrite it to use
the technique you suggest.
And I found in my experiments that creating the sieve in the form of a
list of primes (either directly or by converting a linear sieve) is a
great deal slower than a simple sieve for the majority use cases where
the sieve is not huge.
I don't want to take up peoples time but I am willing to expose the code
to anyone who has an interest as I am sure that it has wrinkles that
others with more experience with Python would find.
But I would also be interested to discover whether there is a rationale
for not offering list.count(value, limit) as this seems to me a useful
function which I have found myself wanting more than once now.
Thank you again for your input, which I appreciate.
Brian
More information about the Python-list
mailing list