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

[Sergey]

On Jul 4, 2013 Andrew Barnert wrote:

> Right on some points, but you're making unwarranted assumptions
> for these two:
>> * sum() can *always* be fast! (patch and tests)
>> * linked list is O(n) where n is number of lists to add

> It's not two other types, it's every type anyone ever has built or
> will build that doesn't have a fast __iadd__. If I create a new
> type, I can very easily make it addable, iterable, displayable,
> pickleable, etc., with simple Python code. But I can't make it
> summable without patching the builtin C function and recompiling
> the interpreter.

Yes, you can! You just need to implement a fast __iadd__ or __add__
for your type to make it O(n) summable. And you can always do that,
can't you?

If that is not obvious we can make it explicit in sum() description.
E.g.:
  """
  function:: sum(iterable[, start])

  Sums *start* and the items of an *iterable* from left to right and
  returns the total. *start* defaults to ``0``.

  To make advantage of faster __iadd__ implementation sum() uses it
  if possible. sum() has linear time complexity for built-in types
  and all types providing constant-time `__iadd__` or `__add__`.

  For some use cases, there are good alternatives to sum(). [...]
  """
Of course that's assuming that patches making sum O(n) are accepted.

> A cons is a single-linked list with no tail pointer and an O(N)
> __iadd__. The node type is the list type; it's just a head value and
> a next pointer to another list. This data structure various kinds of
> O(1) operations (including mutating operations) that other types do
> not. For a trivial example:
>     >>> a = linkedlist([0, 1, 2])
>     >>> b = a.next
>     >>> b.next = linkedlist([10, 20])
>     >>> a
>     linkedlist([0, 1, 10, 20])

Thank you for detailed explanation, now I understand what you mean.

Personally I don't think such implementation would be very useful.
(It's certainly unusual for python's “batteries included” philosophy).
What I would call a linked-list is a separate type where your nodes
are just its internal representation. Something like (second link
from google "python linked list"):
  http://alextrle.blogspot.com/2011/05/write-linked-list-in-python.html
(I would also add 'length' to 'head' and 'tail' to have O(1) len).

> There is no way to make this work is a holds a tail pointer.

There is. You just need to separate the nodes from the list object,
and turn nodes into internal details, invisible outside.

So that your sample would turn into:
    >>> a = linkedlist([0, 1, 2])
    >>> a.replacefrom(2, linkedlist([10, 20]))
    >>> a
    linkedlist([0, 1, 10, 20])

Or maybe even:
    >>> a = linkedlist([0, 1, 2])
    >>> b = a[1:]
    >>> b[1:] = linkedlist([10, 20])
    >>> a
    linkedlist([0, 1, 2])
    >>> b
    linkedlist([1, 10, 20])

I don't like the idea that `a` implicitly changes when I change `b`.
And yes, b=a[1:] would be O(N) since it would have to copy all the
elements to make sure that change to one list won't affect another
one. But that's my vision.

> Making a.next be a copying operation gives the wrong answer (and,
> more generally, breaks every mutating operation on cons-lists) and
> makes almost everything O(N) instead of O(1).

Yes, you're right, this turns copy into O(N). But you can still
keep other operations fast. For example to implement:
  a += b
you only need to walk over the items of `b`. So a simple loop
(and my patched sum):
  for x in manylists:
    a += x
would still be O(N) where N is a total number of elements.

Again, that's how *I* would implement that.

But you CAN have a fast __iadd__ even for your simple a.next case!
You only need to initialize `tail` before calling sum() and update
it inside __iadd__, this way you get O(N) sum() where N is a total
number of elements in all lists. Such __iadd__ implementation would
be destructive, since it would modify all other lists pointing to
those elements, but I guess this is how you wanted it do be.

> If people really do need to concatenate a bunch of tuples this
> often, maybe the answer is to move chain to builtins.

Yes, I understand that we can restrict sum(), for example it can
throw an error for non-numbers as it currently does for strings.
What I can't understand is why we should restrict it if instead
we can make it fast?

>> Seriously, I miss add for set(). I needed it when I had a dictionary
>> like {x:set(...), ...} and needed a set of all the values from it.
>> I wanted to use sum(dict.values()), that would be easy and obvious,
>> but I couldn't, because set() does not support __add__. So I had
>> to write a few lines of loop instead of a few characters. :(
> 
> So what you really want is to be able to combine things using any
> arbitrary operation, instead of just addition? 

No! I only want to make python code simple. Simple is better than
complex, right? And sum() makes code simple. But sometimes it's too
slow, and cannot be used. So I wanted to make sum() faster, to make
even more code simple. That's all.

It's just someone said, that "+" should not be used in the first
place, so I answered, that missing "+" makes code complex, and
provided an example about sets.