3
\$\begingroup\$

The code below generates a query with the product of possibilities that may vary from 'abc' to 'abc ... z'

import itertools
import time

res = itertools.product('abcdefgh', repeat=8)
fileObj = open("txt_abcdefgh.txt","w") 
timestamp1 = time.time()

for i in res:   
    print (i) #this only to check the progress of the process
    fileObj.write(i[0] + i[1] + i[2] + i[3] + i[4] + i[5] + i[6] + i[7] + '\n')

timestamp2 = time.time()
fileObj.write('This took %.2f seconds' % (timestamp2 - timestamp1))
fileObj.close()

However, I have an entry of only 8 items and the runtime is unsatisfactory.

Input      Time             Possibilities
abc        0.01 seconds     27
abcd       0.29 seconds     256
abcde      4.28 seconds     3,125
abcdef     31.59 seconds    46.656
abcdefg    542.44 seconds   823,543
abcdefgh   4806.84 seconds  16,777,216

Is there any other way to better this code, maybe with some other language, or with another programming technique?

\$\endgroup\$
1
  • 3
    \$\begingroup\$ It's not the language, it's file I/O. Reduce I/O, you'll reduce execution time. Consider collecting the results in one step, and writing them all at once to a file as another step. \$\endgroup\$ Commented May 17, 2017 at 19:27

1 Answer 1

5
\$\begingroup\$

1. Speeding up the code

Here's the initial measurement:

$ python ./cr163578.py
('a', 'a', 'a', 'a', 'a', 'a', 'a', 'a')
('a', 'a', 'a', 'a', 'a', 'a', 'a', 'b')
('a', 'a', 'a', 'a', 'a', 'a', 'a', 'c')
... much output deleted ...
('h', 'h', 'h', 'h', 'h', 'h', 'h', 'h')
$ tail -1 txt_abcdefgh.txt
This took 122.10 seconds

Let's make some improvements:

  1. Omit the print statement, which generates lots of useless output that is just slowing us down.

  2. Use the with statement to open and close the file.

  3. Omit the time measurement — we can use the time program to do the measurement.

Here's version 2:

import itertools
with open('txt_abcdefgh.txt', 'w') as f:
    for i in itertools.product('abcdefgh', repeat=8):
        f.write(i[0] + i[1] + i[2] + i[3] + i[4] + i[5] + i[6] + i[7] + '\n')

This is about 8 times as fast as the original:

$ /usr/bin/time python cr163578.py
       16.73 real        16.45 user         0.23 sys

Now let's use the join method to build the output instead of lots of + operations. Here's version 3:

import itertools
with open('txt_abcdefgh.txt', 'w') as f:
    for i in itertools.product('abcdefgh', repeat=8):
        f.write(''.join(i) + '\n')

This is about 16 times as fast as the original:

$ /usr/bin/time python cr163578.py
        8.25 real         8.01 user         0.21 sys

And finally, let's avoid the need to append the newline to each line of output by using the writelines method of the file. Here's version 4:

import itertools
with open('txt_abcdefgh.txt', 'w') as f:
    f.writelines(map(''.join, itertools.product('abcdefgh', repeat=8)))

This is about 20 times as fast as the original:

$ /usr/bin/time python cr163578.py
        5.87 real         5.73 user         0.12 sys

2. Runtime complexity

If there are \$k\$ letters in your alphabet, and \$n\$ characters in the strings you are constructing, then there are \$k^n\$ strings altogther. Here \$k=8\$ and \$n=8\$ so there are \$8^8 = 16,777,216\$ possibilities, which take \$9 \times 8^8 = 150,994,944\$ bytes to store on disk.

Your aim is to have \$k=26\$ and \$n=26\$. But then there will be $$26^{26} = 6,156,119,580,207,157,310,796,674,288,400,203,776$$ possibilities, which can't possibly be generated or stored.

Whatever you are trying to do, you will have to find some other way to do it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.