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
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 email@example.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)
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/ firstname.lastname@example.org
Python-ideas mailing list Pythonemail@example.com 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.