List Count

[Blind Anagram]

On 24/04/2013 02:59, Steven D'Aprano wrote:
> On Tue, 23 Apr 2013 17:57:17 +0100, Blind Anagram wrote:

[snip]

> In my opinion, it is more important to be efficient for large sieves, not 
> small. As they say, for small N, everything is fast. Nobody is going to 
> care about the difference between small-N taking 1ms or 10ms, but they 
> will care about the difference between big-N taking 1 minute or 1 hour. 
> So, as a general rule, optimize the expensive cases, and if the cheap 
> cases are a little less cheap than they otherwise would have been, nobody 
> will care or notice.

I agree in general but it is often the case that more sophisticated
algorithms only gain traction over simpler ones at much higher points
than might be expected from a simple analysis.  In my experience a naive
sieve is an efficient solution for a general purpose sieve class
primarily intended for situations where the sieve length can be large
but not huge.

As I think you have pointed out, memory is cheap and the memory
operations needed to do copying and counting operations are fast. So
using up memory is not normally an issue.  I have just found a situation
where a copy can have a serious impact on performance in an admittedly
limiting, minority use case.   It the fact that this copy is not, in
principle, necessary, that I find disappointing.

[snip]
> In this case, I would say that adding a limit argument to list.count is 
> *absolutely not* worthwhile, because it is insufficiently general. To be 
> general enough to be worthwhile, you would have to add three arguments:
> 
> list.count(value, start=0, end=None, step=1)
> 
> But even there I don't think it's general enough to cover the costs. I 
> believe that a better solution would be to create list views to offer a 
> subset of the list without actually copying.

I don't know a great deal about Python internals but I suspect that
these solutions would offer more but also cost more.  So where the
balance of advantages would lie is unclear.  But I am not pushing for a
particular (or, indeed, any) solution.