You are right.  I made a thinko.  

List construction from an iterator is O(N) just as is `sum(1 for _ in it)`.  Both of them need to march through every element.  But as a constant multiplier, just constructing the list should be faster than needing an addition (Python append is O(1) because of smart dynamic memory pre-allocation).

So the "just read the iterator" is about 2-3 times faster than read-then-accumulate).  Of course, it the run-lengths are LARGE, we can start worrying about the extra memory allocation needed as a tradeoff.  Your sum uses constant memory.

On Sat, Jun 10, 2017 at 8:26 PM, Bernardo Sulzbach <mafagafogigante@gmail.com> wrote:
On 2017-06-11 00:13, David Mertz wrote:
Bernardo Sulzbach posted a much prettier version than mine that is a bit shorter.  But his is also somewhat slower (and I believe asymptotically so as the number of equal elements in subsequence goes up).  He needs to sum up a bunch of 1's repeatedly rather than do the O(1) `len()` function.


Constructing a list from an iterator of size N is in O(N).

Summing N elements is in O(N).

I don't think it is asymptotically slower, just slower because of implementation details.

--
Bernardo Sulzbach
http://www.mafagafogigante.org/
mafagafogigante@gmail.com
_______________________________________________
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/



--
Keeping medicines from the bloodstreams of the sick; food
from the bellies of the hungry; books from the hands of the
uneducated; technology from the underdeveloped; and putting
advocates of freedom in prisons.  Intellectual property is
to the 21st century what the slave trade was to the 16th.