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.