Optimizing Small Python Code

[jan]

You're right, I was making an academic point.

I think this whole compression question relates to Kolmogorov
complexity <https://en.wikipedia.org/wiki/Kolmogorov_complexity>

"In algorithmic information theory (a subfield of computer science and
mathematics), the Kolmogorov complexity of an object, such as a piece
of text, is the length of a shortest computer program (in a
predetermined programming language) that produces the object as
output".

cheers

jan

On 24/06/2021, Avi Gross via Python-list <python-list at python.org> wrote:
> Jan,
>
> As an academic discussion, yes, many enhancements only pay off when things
> are larger.
>
> And for most purposes, I/O is so much slower that it makes little
> difference. But on a multi-processing machine, extra CPU may impact how much
> else the machine can do at the same time.
>
> Here is an example of what I meant. Given exactly the current output, what
> is the shorter program you can use to cheat and produce an answer.
>
> Recall the original output has a length of 169:
>
> a = """1
>       0
> 2
>       0
>       1
> 3
>       0
>       1
>  2
> 4
> 0
>       1
>       2
>       3
> 5
>       0
>       1
>       2
>       3
> 4
> 6
>       0
>       1
>       2
>       3
>       4
>       5
>       """
>
> len(a)
>
>
> Now if you had already used a compression algorithm on it, you would get
> this:
>
> import zlib
> a = zlib.compress(a.encode("ascii"))
> len(a)
>
> Now a has a length of 53!
>
> It now looks like this:
>
> b'x\x9c3\xe4R\x00\x03\x03.#8\x0bB\x1br\x19c\x88(\x18q\x99p!q\xc1\x00\xa6\xd1\x98\xcb\x14S\x03\x9a\n\x13.3\x82j
> \xb4\t\x94\x86\x99\t\x00\xdc\x87\x14\xb7'
>
> So the shorter cheat program might now be:
>
>>>> print(zlib.decompress(b'x\x9c3\xe4R\x00\x03\x03.#8\x0bB\x1br\x19c\x88(\x18q\x99p!q\xc1\x00\xa6\xd1\x98\xcb\x14S\x03\x9a\n\x13.3\x82j
>>>> \xb4\t\x94\x86\x99\t\x00\xdc\x87\x14\xb7').decode("ASCII"))
> 1
>       0
> 2
>       0
>       1
> 3
>       0
>       1
>  2
> 4
> 0
>       1
>       2
>       3
> 5
>       0
>       1
>       2
>       3
> 4
> 6
>       0
>       1
>       2
>       3
>       4
>       5
>
> Of course, the above has overhead as you have a line to import the library
> as well as the darn function names but for larger amounts of text, those
> stay fixed.
>
> I note again this won't fool humans but some on-line courses that just take
> your program and run it and only compare the output will be fooled.
>
>
> -----Original Message-----
> From: jan <rtm443x at googlemail.com>
> Sent: Thursday, June 24, 2021 3:01 AM
> To: Avi Gross <avigross at verizon.net>
> Cc: python-list at python.org
> Subject: Re: Optimizing Small Python Code
>
> If I'm not mistaken, the original output is O(n^2) in quantity of chars, and
> as output time is proportional to the length of the output, that makes the
> output time also O(n^2) here too.
>
> So I guess this only looks like it's reduced to linear because the output
> here is very small. For large n it would become obvious.
>
> jan
>
> On 24/06/2021, Avi Gross via Python-list <python-list at python.org> wrote:
>> Yes, I agree that if you do not need to show your work to a human,
>> then the problem specified could be solved beforeand and a simple
>> print statement would suffice.
>>
>> Ideally you want to make a problem harder such as by specifying an N
>> that varies then testing it with an arbitrary N.
>>
>> But I suggest the item below is not minimal. You can store the
>> printout more compactly as the only symbols out put are tabs, newlines
>> and seven digits.
>> If your language supported some function that expanded a binary string
>> that used say 4 bytes per symbol so it could be printed, or accepted a
>> compressed form of the string and uncompressed it, you might have code
>> like:
>>
>> print(unzip("n*n&&S!~se"))
>>
>> -----Original Message-----
>> From: Python-list
>> <python-list-bounces+avigross=verizon.net at python.org> On Behalf Of
>> Michael F. Stemper
>> Sent: Wednesday, June 23, 2021 10:23 AM
>> To: python-list at python.org
>> Subject: Re: Optimizing Small Python Code
>>
>> On 23/06/2021 08.17, Stefan Ram wrote:
>>> "Avi Gross" <avigross at verizon.net> writes:
>>>> This can be made a one-liner too! LOL!
>>>
>>> print( '1\n      0\n2\n      0\n      1\n3\n      0\n      1\n
>>> 2\n4\n
>> 0\n      1\n      2\n      3\n5\n      0\n      1\n      2\n      3\n
>> 4\n6\n      0\n      1\n      2\n      3\n      4\n      5\n' )
>>
>> Unless I'm figuring ot wrong, you just took it from O(n^2) to O(1).
>> That deserves a Turing award or something.
>>
>> --
>> Michael F. Stemper
>> You can lead a horse to water, but you can't make him talk like Mr. Ed
>> by rubbing peanut butter on his gums.
>> --
>> https://mail.python.org/mailman/listinfo/python-list
>>
>> --
>> https://mail.python.org/mailman/listinfo/python-list
>>
>
> --
> https://mail.python.org/mailman/listinfo/python-list
>