python - Boosting time for multiple for loops in list comprehensions -

i looking method lower execution time python 3.5 takes 2 for-loops in list comprehension looks this:

[[(k1-k2)**power k2 in range(m,n)] k1 in range(m,n)] 

so, started off current approach , found while work, quite slow. first attempt involved transforming list comprehension suitable approach numpy arrays. 3 times faster original approach, that's when noticed quite beautiful: symmetric toeplitz matrix. wiki page:

in linear algebra, toeplitz matrix or diagonal-constant matrix, named after otto toeplitz, matrix in each descending diagonal left right constant.

i first used default scipy implementation of toeplitz matrix, approach unnecessary slow problem. wrote myself similar approach, third attempt below.

methodology

i ran 10 tests each approach, each individual test comprising 1000 runs. set parameters m = 10, n = 100. results can found in table below:

    approach       numpy #1     numpy #2     numpy #3 1        4.573965       1.432406     1.060242     0.186767 2        4.341466       1.432237     1.060404     0.186872 3        4.442438       1.434460     1.144850     0.183120 4        4.318919       1.456928     1.072072     0.185626 5        4.249392       1.450684     1.072217     0.183273 6        4.202730       1.508863     1.070299     0.183019 7        4.224226       1.457543     1.065354     0.183591 8        4.234505       1.432971     1.082438     0.185711 9        4.256538       1.431828     1.080051     0.184290 10       4.241055       1.557204     1.083070     0.185845  avg      4.308523       1.459512     1.079100     0.184811 std      0.117433       0.041693     0.024538     0.001521 

the scipy toeplitz approach (numpy #2 in table) 4 times faster current approach, these results dwarfed third , final approach: whopping 23 times speed on initial implementation!

now, since interested in time complexity, let n vary, keeping m = 10. results each approach can found in figure below:

clearly, third approach way go!

code

full code:

import timeit import numpy np scipy.linalg import toeplitz   def your_approach(m, n):     print("\n\tlist comprehension")     k = range(m, n)     in range(1, 11):         start = timeit.default_timer()         j in range(1, 1001):             data_list_comp = [[(k1 - k2) ** 2 k2 in k] k1 in k]         print("\t{}".format(timeit.default_timer() - start))     return data_list_comp   def numpy1(m, n):     print("\n\tnumpy")     k_n = np.array(range(m, n))     in range(1, 11):         start = timeit.default_timer()         j in range(1, 1001):             data_numpy = [list((k_n - x) ** 2) x in k_n]         print("\t{}".format(timeit.default_timer() - start))     return data_numpy   def numpy2(m, n):     print("\n\ttoeplitz")     k_n = np.array(range(0, n - m)) ** 2     toep = toeplitz(k_n)     in range(1, 11):         start = timeit.default_timer()         j in range(1, 1001):             data_numpy = [list(toep[:, i]) in range(n - m)]         print("\t{}".format(timeit.default_timer() - start))     return data_numpy  def numpy3(m, n):     print("\n\ttoeplitz2")     k_n = list(np.array(range(0, n - m)) ** 2)  # can done without numpy, bit lazy. :)     in range(1, 11):         start = timeit.default_timer()         j in range(1, 1001):             data_numpy = [(k_n[i::-1] + k_n[1:-i]) if != 0 else k_n in range(0, n - m)]         print("\t{}".format(timeit.default_timer() - start))     return data_numpy  m = 10  n in [25, 50, 100, 150, 200]:     assert your_approach(m, n) == numpy1(m, n) == numpy2(m, n) == numpy3(m, n)