How to speed up python loop

Not the prettiest coding style, but desperate times call for desperate coding. Try turning your nested nested loops into one big generator expression:

try:    i,j,i2,j2 = ((i,j,i2,j2)        for i in xrange(m)          for j in xrange(n)            for i2 in xrange(i + 1, m)              for j2 in xrange(j + 1, n)                if myarray[i][j] == myarray[i2][j2] and                     myarray[i2][j] == myarray[i][j2]).next()    return [i,j],[i2,j2]except StopIteration:    return None

Updated to use builtins next and product, and Py3 range instead of xrange:

from itertools import productmatch = next(((i,j,i2,j2)    for i, j in product(range(m), range(n))        for i2, j2 in product(range(i+1, m), range(j+1, n))            if myarray[i][j] == myarray[i2][j2] and                 myarray[i2][j] == myarray[i][j2]), None)if match is not None:    i,j,i2,j2 = match    return [i,j],[i2,j2]else:    return None

You can still use the python notation, and have the speed of C, using the Cython project.A first step would be to convert the loop in C loop: it's automatically done by typing all the variables used in the loop:

cdef int m = 100cdef int n = 100cdef int i, j, i2, j2for i in xrange(m):  for j in xrange(n):    for i2 in xrange(i + 1, m):      for j2 in xrange(j + 1, n):

For The next part, it would be even better if that myarray would be pure C array, then no rich python comparaison nor array access. With your python array, you can remove the rich comparaison by doing native comparaison (if you have double in your array):

        cdef double a, b, c, d        a = myarray[i][j]        b = myarray[i2][j2]        c = myarray[i2][j]        d = myarray[i][j2]        if a == b and c == d:          return [i, j], [i2, j2]

You can see how optimization are going by running cython -a yourfile.pyx, then open the yourfile.html generate. You'll see how Cython have optimized your code, and removed Python overhead.

Sorry to tell you, but it's not a matter of optimization. No matter which language or implementation you choose, this algorithm is not O(n*log n) in the worst- and average case. You might want to read up on how the Big-O notation works and develop a better algorithm.