[Python-ideas] Intermediate Summary: Fast sum() for non-numbers

[Paul Moore]

On 14 July 2013 20:26, Sergey <sergemp at mail.ru> wrote:

> I'm trying to address this particular issue of sum() inconsistency
> being O(N) for numbers, but O(N*N) for many containers. And trying
> to find options that could give sum a chance to be O(N) for most
> use cases.
>

sum is currently simple. It just adds each element of the iterable it's
called with using +. That's it. (OK, it also checks for strings and rejects
them...)

    result = start
    for elem in iterable:
        result = result + elem

The performance complexity follows directly from that definition. It is no
more surprising that numbers are O(N) and containers O(N*N) than it is that
the loop I show above has that complexity. That is to say, it *is*
surprising, if you don't know complexity calculations very well, but it's a
fundamental and trivial result once you do.

Changing the performance of sum() makes reasoning about its complexity
*harder* because you can't refer back to that very basic equivalence above
to inform your assumptions.

The suggestion of using += has merit because it keeps the equivalence
simple, so that people can still reason about complexity in a
straightforward manner. But there are backward compatibility concerns to
review and assess.

Performance is not the only consideration. But this is the underlying
situation around the performance debates, as I see it. (And people saying
"don't change anything" are quite possibly doing so because they view
understandable performance guarantees as more important than the
"attractive nuisance" of something that is often fast, but it's hard to be
sure exactly when.)

Paul
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20130714/aba2bca8/attachment-0001.html>