How to increase speed of access element in 2 dimension array?

[Diver]

Hi there.
How to increase speed of access element in 2 dimension array?

with matrix size 1000x1000 
each creation of sum matrix take about 1 second.
I find the problem is in slow access to the element of list of list
what is occur in this line 

matrix2[y][x] = min(matrix2[upperm][x-1], matrix2[upperm][x], matrix2[upperm][x+1]) + matrix1[y][x]

complete example below the message
I tried use array from numpy with same speed.

--- calcCMS took 0.975945949554 ---
--- calcCMS took 0.898028850555 ---

How to increase speed of access element in 2 dimension array?

import time
from mypkg.mytimer import timer
import random
TIMERS = True

m = 1000
n = 1000
seam = 100

matrix1 = [[0 for x in range(n)] for y in range(m)] # E
matrix2 = [[0 for x in range(n)] for y in range(m)] # CMS

for i in range(seam):
   for y in range(m):
       for x in range(n):
           matrix1[y][x] = random.randint(1,100)

   for x in range(n):
       matrix2[0][x] = matrix1[0][x]

   if TIMERS:
       starttimer = time.time()
   for y in range(1,m):
       upperm = y-1
       matrix2[y][0]   = min(matrix2[upperm][0], matrix2[upperm][1]) + matrix1[y][0]
       matrix2[y][n-1] = min(matrix2[upperm][n-2], matrix2[upperm][n-1]) + matrix1[y][n-1]
       for x in range(1,n-1):
           matrix2[y][x] = min(matrix2[upperm][x-1], matrix2[upperm][x], matrix2[upperm][x+1]) + matrix1[y][x]
   if TIMERS:
       timer(starttimer,"calcCMS")

---

the code is unreadable.
how to remove it and past normal code?

[Larz60+]

Need to use ctrl-shift-v when posting code to remove html

[Diver]

in "view printable version" the original message showed correctly.

---

slow code in this line:

matrix2[y][x] = min(matrix2[upperm][x-1], matrix2[upperm][x], matrix2[upperm][x+1]) + matrix1[y][x]

import time
from mypkg.mytimer import timer
import random
TIMERS = True

m = 1000
n = 1000
seam = 100

matrix1 = [[0 for x in range(n)] for y in range(m)] # E
matrix2 = [[0 for x in range(n)] for y in range(m)] # CMS

for i in range(seam):
   for y in range(m):
       for x in range(n):
           matrix1[y][x] = random.randint(1,100)

   for x in range(n):
       matrix2[0][x] = matrix1[0][x]

   if TIMERS:
       starttimer = time.time()
   for y in range(1,m):
       upperm = y-1
       matrix2[y][0]   = min(matrix2[upperm][0], matrix2[upperm][1]) + matrix1[y][0]
       matrix2[y][n-1] = min(matrix2[upperm][n-2], matrix2[upperm][n-1]) + matrix1[y][n-1]
       for x in range(1,n-1):
           matrix2[y][x] = min(matrix2[upperm][x-1], matrix2[upperm][x], matrix2[upperm][x+1]) + matrix1[y][x]
   if TIMERS:
       timer(starttimer,"calcCMS")

---

I'm very sorry for unreadable code in my first message

[Mekire]

I believe this does the same thing and is quite a bit faster:  

import numpy as np
from scipy import ndimage


m = 1000
n = 1000

matrix1 = np.random.randint(1, 101, (m,n))
matrix2 = np.zeros((m,n))

for y in range(m):
   matrix2[y] = ndimage.grey_erosion(matrix2[y-1], size=3) + matrix1[y]

The thing about numpy is, if you loop as normal, it won't help at all.  You need to try to use vectorized operations whenever possible.

In your case this is hard as the results of the next row depend on the one we just generated.

[Diver]

I believe this does the same thing and is quite a bit faster:

import numpy as np from scipy import ndimage m = 1000 n = 1000 matrix1 = np.random.randint(1, 101, (m,n)) matrix2 = np.zeros((m,n)) for y in range(m):    matrix2[y] = ndimage.grey_erosion(matrix2[y-1], size=3) + matrix1[y]

The thing about numpy is, if you loop as normal, it won't help at all. You need to try to use vectorized operations whenever possible. In your case this is hard as the results of the next row depend on the one we just generated.

Thank you very much for this code.
I'm happy, app become faster and I don't need wait 110 seconds till it calculate 100 seams
--- calcCMS took 0.0981049537659 ---

However now I'm in stack what write in report.
What is running time of this code how it depend on n and m?

[Mekire]

Well, unless grey_erosion is magic the runtime should be O(mn).  Though if you don't understand why, that might be a problem.  Also no clue if your teacher will approve of using a minimum filter rather than implementing it yourself.

[Diver]

My code what is slow doing it in O(nm) because there is 2 for loop and other operation just take constant time.
I didn't get clear how vectorised operations work.
With your answer it is clear me now there is no such magic to turn O(nm) to O(m).

Can you improve me if I have mistake in sentence below?
Vectorised operation decrease the access time to the matrix by factor 0.1 in sample input because they use some optimized code what decrease constant time of access to the data structure (array).