how to effectively loop over matrix elements?

Question

I have to loop over a 800 000* 800 000 matrix. I tried to do that by simple loops but it take me so huge time. How can I loop fastly ?

for in in xrange(800000):
   for j in xrange(800000):
      print i,j

Typically, I am reading an image using OpenCV, then I need to loop over every pixel in order to perform some calculations and comparisons with the values of certain characteristics of the neighbors of the pixel. When I run a loop, I feel it needs more than 2 days to be finished.

In fact, I want to implement my own version of GrowCut algorithm. The authors claim to execute the algorithm in less than 4 minutes using a computer like mine. However, looping over 1200*1100 matrix takes so much time (I tested that). How can I read them quickly ?

Answer 1

For performant array looping, you can use Cython. You can use most of the syntax of Python, with a lot of the performance gains of using C. It is also compatible with NumPy.

Iterating over arrays with Cython.

Answer 2

You may consider using the built in bytearray type instead of python lists.

You can create a bytearray of size 1200 * 1300 * 4 to represent your matrix. Element i, j will be at i * 1200 * 4 + j * 4 (assuming a 4 byte pixel size)

Looking further, I found that you can use arrays in python to efficiently store pretty much anything efficiently. You can easily calculate the index as explained above.

"The Numeric Python extension (NumPy) defines another array type; see http://www.numpy.org/ for further information about Numerical Python."

Answer 3

Here's a possible optimization, however as again this will be dependent on the system and other currently running processes etc... and the calculations which you did inside.

import time
import numpy as np
test = np.ones((1200, 1100))

Test 1:

def loops():
    start = time.clock()
    for i in range(1200):
        for j in range(1100):
            a = test[i,j]
    print(time.clock()-start)
    return a

>>> loops()
1.433313120652599
1.0

so you see it's only 1.5 seconds for the loops. Adding calculations inside will stretch this time out significantly, but your loops are the least of that worry. Without providing your code I can't say much more about that.

Alternate approach would be:

def loops():
    start = time.clock()
    for row in test:
        for element in row:
            a = element
    print(time.clock()-start)
    return a

>>> loops()
0.714938339920252
1.0

Do notice how small this sample is (just 1 test) however half the time is indicative of possible enhancements? also you avoid the need to use the a= and can skip allocation of a new variable which should shave off few microseconds.

Show your code, I'm sure there's something else that can be done.

This is win7 Intel i5 Dual Core Python3.4