[Python-ideas] Run length encoding

[David Mertz]

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 at 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 at gmail.com
> _______________________________________________
> Python-ideas mailing list
> Python-ideas at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20170610/7d887efa/attachment.html>