RE: Optimizing Small Python Code
Barry, I am not going to continue replying in this thread. I made my point and it was focused after a while on the size of the CODE. Of course, the code can be made ever smaller using gimmicks and yet run longer or use more memory or CPU. If you have control of a package with a short name like "x" for example, you can write a function y() that builds in the code described or any variant and your program becomes: Import x y() and it would print out whatever you need. If you can get the python interpreter to make that module standard, it can be shorted more! As mentioned, one suggested metric for how complex a program is, or maybe how much information it contains, is the shortest program you can write to generate the info. Something already compressed may not be easy to make smaller. But the above idea does not care if the solution takes forever to run as in if it uses lots of tiny re-usable functions and does lots of recursion. Clearly, as has been pointed out, for many of the one-off programs people write here, optimization is not necessarily worthwhile. The program asked for here actually has minimal purpose as it does one thing that could be done in advance and replaced by a print statement. My "contribution" above does look stupid but consider what it would mean if the program asked you to print the first billion prime numbers. The program that simulated the output would likely read in huge file from disk and print it. The first part of the I/O might be much faster if the data on disk was compressed and if it could be uncompressed as it was being read and printed to the output, might be lots faster and even use less memory. Clearly it would likely use more CPU but far less than finding the first billion primes that hard way. Final note is there is not much in the discussion that is really about Python as much of the argument remains similar in many programming languages. So, I am done and will ignore this thread. From: Barry Scott Sent: Thursday, June 24, 2021 3:12 PM To: Avi Gross Cc: python-list@python.org Subject: Re: Optimizing Small Python Code On 24 Jun 2021, at 16:58, Avi Gross via Python-list mailto:python-list@python.org> > wrote: 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: The data is smaller, but at the cost of the code that knows how to decompress it. I'd expect that by using compression you have increased memory use as this amount of data is far smaller than code to decompress it. Barry -- https://mail.python.org/mailman/listinfo/python-list
Re: Optimizing Small Python Code
> On 24 Jun 2021, at 16:58, Avi Gross via Python-list > wrote: > > 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: The data is smaller, but at the cost of the code that knows how to decompress it. I'd expect that by using compression you have increased memory use as this amount of data is far smaller than code to decompress it. Barry -- https://mail.python.org/mailman/listinfo/python-list
Re: Optimizing Small Python Code
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 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 > Sent: Thursday, June 24, 2021 3:01 AM > To: Avi Gross > Cc: python-list@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 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 >> On Behalf Of >> Michael F. Stemper >> Sent: Wednesday, June 23, 2021 10:23 AM >> To: python-list@python.org >> Subject: Re: Optimizing Small Python Code >> >> On 23/06/2021 08.17, Stefan Ram wrote: >>> "Avi Gross" 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 > -- https://mail.python.org/mailman/listinfo/python-list
RE: Optimizing Small Python Code
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 Sent: Thursday, June 24, 2021 3:01 AM To: Avi Gross Cc: python-list@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 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 > On Behalf Of > Michael F. Stemper > Sent: Wednesday, June 23, 2021 10:23 AM > To: python-list@python.org > Subject: Re: Optimizing Small Python Code > > On 23/06/2021 08.17, Stefan Ram wrote: >> "Avi Gross" 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
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 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 On > Behalf Of Michael F. Stemper > Sent: Wednesday, June 23, 2021 10:23 AM > To: python-list@python.org > Subject: Re: Optimizing Small Python Code > > On 23/06/2021 08.17, Stefan Ram wrote: >> "Avi Gross" 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
RE: Optimizing Small Python Code
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 On Behalf Of Michael F. Stemper Sent: Wednesday, June 23, 2021 10:23 AM To: python-list@python.org Subject: Re: Optimizing Small Python Code On 23/06/2021 08.17, Stefan Ram wrote: > "Avi Gross" 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
Re: Optimizing Small Python Code
On 23/06/2021 08.17, Stefan Ram wrote: "Avi Gross" 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
Re: Optimizing Small Python Code
Kais Ayadi wrote at 2021-6-22 08:03 -0700: >Hi There! >this is a small python code executed in 61 steps > >for n in range(1, 7): >print (n) >for x in range(0, n): >print(" ", x) > >can this code be more optimised? You should proceed as follows: implement a task in the most straightforward way possible. Only if you hit a problem look for optimizations -- to solve the problem. Small pieces of code rarely need optimizations -- unless they are called very often. Optimizations often aim to reduce runtime. In your code, the runtime is dominated by the output. Output speed is mostly outside your control. Do not try to optimize the code above for runtime. -- Dieter -- https://mail.python.org/mailman/listinfo/python-list
RE: Optimizing Small Python Code
I had a similar question, Greg. Optimized for what, indeed. Some might suggest removing a VISIBLE loop is an optimization and some might not. First you need to look at what your code does. It is fairly primitive. Here is a two-line version but is it simpler: for n in range(1, 7): print (n, "\n", ''.join([("\t" + str(x) + "\n") for x in range(0, n)])) It has the same output: 1 0 2 0 1 ... 6 0 1 2 3 4 5 This can be made a one-liner too! LOL! But there are other optimizations as the calculation sort of keeps recalculating what is a simple enough pattern. You can for example in a loop of some kind keep appending to a structure like a list but perhaps simpler is using indexing into a tuple or list made in advance and only once. Here is the code that works for any size by changing the value of "last" without constant recalculation. Is it better? Who knows? last = 7; nl = "\n"; tab = "\t" using = [ tab + str(num) for num in range(0,last)] print(''.join([str(n) + nl + nl.join(using[:n]) + nl for n in range(1, last)])) Now why you want this is beyond me! -Original Message- From: Python-list On Behalf Of Greg Ewing Sent: Tuesday, June 22, 2021 7:05 PM To: python-list@python.org Subject: Re: Optimizing Small Python Code On 23/06/21 3:03 am, Kais Ayadi wrote: > for n in range(1, 7): > print (n) > for x in range(0, n): > print(" ", x) > > can this code be more optimised? Optimised for what? Readability? Execution speed? Code size? Memory usage? -- Greg -- https://mail.python.org/mailman/listinfo/python-list -- https://mail.python.org/mailman/listinfo/python-list
Re: Optimizing Small Python Code
How would you measure the steps that it takes? - Benjamin > On Jun 22, 2021, at 7:04 PM, Greg Ewing wrote: > > On 23/06/21 3:03 am, Kais Ayadi wrote: >> for n in range(1, 7): >> print (n) >> for x in range(0, n): >> print(" ", x) >> can this code be more optimised? > > Optimised for what? Readability? Execution speed? Code size? > Memory usage? > > -- > Greg > -- > https://mail.python.org/mailman/listinfo/python-list -- https://mail.python.org/mailman/listinfo/python-list
Re: Optimizing Small Python Code
On 23/06/21 3:03 am, Kais Ayadi wrote: for n in range(1, 7): print (n) for x in range(0, n): print(" ", x) can this code be more optimised? Optimised for what? Readability? Execution speed? Code size? Memory usage? -- Greg -- https://mail.python.org/mailman/listinfo/python-list