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 < mafagafogiga...@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/ > mafagafogiga...@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.
_______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
