List Count
Blind Anagram
blindanagram at nowhere.org
Wed Apr 24 05:01:36 EDT 2013
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.
More information about the Python-list
mailing list