Optimizing Small Python Code

[Avi Gross]

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
>