14.6.2008

Messing around with Python 2D arrays

So I wrote a simple script to render some Perlin noise. It's a fast hack, lot's of redundant code. It works and also shows that Python is kinda slow when dealing with large 2-dimensional arrays. Of course using linked lists as arrays is a bad idea. (I later learned that access by index for Python lists is O(1)). So what I'm going to do here is to try out Numpy to optimize my code.

Update: Some benchmarking of my original script and Manu's numpy version. Thanks, Manu!
Original script: 42.360 seconds



import random
import math

import pygame
from pygame.locals import *

class GFX():
def __init__(self):
pygame.init()

self.display_flags = DOUBLEBUF
rect = self.width, self.height = 640, 480

if pygame.display.mode_ok(rect, self.display_flags):
self.screen = pygame.display.set_mode(rect, self.display_flags)


def linear_interp(a, b, x):
return a * (1 - x) + b * x

def cosine_interp(a, b, x):
f = (1 - math.cos(x * math.pi)) * 0.5
return a * (1 - f) + b * f

def cubic_interp(v0, v1, v2, v3, x):
p = (v3 - v2) - (v0 - v1)
Q = (v0 - v1) - p
R = v2 - v0
S = v1

return P * x ** 3 + Q * x ** 2 + R * x + S


class Arr:
def __init__(self):
self.arr = None

def size(self, w, h):
# Sanity checks
if w > 400 or h > 400:
raise Exception("Array size too large.")

self.arr = [[0] * w for i in range(h)]

def noise(self, w, h):
# Sanity checks
if w > 400 or h > 400:
raise Exception("Array size too large.")

print "noise"

# Create 2D array
self.arr = [[0] * w for i in range(h)]

# Fill it with noise
for i in range(h):
for j in range(w):
r = random.random()
self.arr[i][j] = r

def smooth(self, ite):
print "smooth"

h = len(self.arr)
w = len(self.arr[0])

for ps in range(ite):
x, y = 0, 0

for i in self.arr:
for j in i:
lp = self.arr[(x - 1) % w][y]
rp = self.arr[(x + 1) % h][y]
up = self.arr[x][(y - 1) % h]
dp = self.arr[x][(y + 1) % h]
mp = self.arr[x][y]

self.arr[x][y] = (lp + rp + up + dp + mp) / 5

x += 1
x = 0
y += 1

def normalize(self):
print "normalize"

h = len(self.arr)
w = len(self.arr[0])
x, y = 0, 0

max = 0
min = 1
# Find min and max
for i in self.arr:
for j in i:
val = self.arr[x][y]
if val > max:
max = val
if val < min:
min = val

x += 1
x = 0
y += 1

x, y = 0, 0
mult = 1 / (max - min)
for i in self.arr:
for j in i:
self.arr[x][y] -= min
self.arr[x][y] *= mult
x += 1
x = 0
y += 1

return self.arr


def add(self, arr2):
w = len(self.arr)
h = len(self.arr[0])

x, y = 0, 0
for j in self.arr:
for i in j:
self.arr[x][y] += arr2.arr[x][y]

x += 1
x = 0
y += 1

def div(self, val):
x, y = 0, 0
for j in self.arr:
for i in j:
self.arr[x][y] /= val

x += 1
x = 0
y += 1

def cosine_resize(self, mult):
# Sanity checks
if len(self.arr) * mult > 400:
raise Exception("Array size too large (tried resizing).")

print "linear resize"

h = len(self.arr)
w = len(self.arr[0])

w2 = w * mult
h2 = h * mult

arr_new = [[0] * w2 for i in range(h2)]

x, y = 0, 0
for i in self.arr:
for j in i:
p0 = self.arr[x][y]
p1 = self.arr[(x + 1) % w][y]
p2 = self.arr[x][(y + 1) % h]
p3 = self.arr[(x + 1) % w][(y + 1) % h]

for ny in range(mult):
for nx in range(mult):
v0 = cosine_interp(p0, p1, float(nx) / mult)
v1 = cosine_interp(p2, p3, float(nx) / mult)
arr_new[x * mult + nx][y * mult + ny] = cosine_interp(v0, v1, float(ny) / mult)

x += 1
x = 0
y += 1

self.arr = arr_new


def render_arr(screen, arc):
print "render"
x, y = 0, 0

arr = arc.arr

size = len(arr)
for i in range(screen.get_height()):
for j in range(screen.get_width()):
val = arr[x % size][y % size]

if val > 1:
val = 1
if val < 0:
val = 0

val = int(val * 255)
val = val % 256

color = (val, val, val)
screen.set_at((x, y), color)

x += 1
x = 0
y += 1


gfx = GFX()

run = 1
clock = pygame.time.Clock()

pw, ph = 256, 256
depth = 5

arr = []
farr = Arr()
farr.size(pw, ph)

# Generate perlin noise
for i in range(depth):
arr.append(Arr())

d = 2 ** i

arr[-1].noise(pw / d, ph / d)
arr[-1].smooth(3)
arr[-1].cosine_resize(d)
arr[-1].div(2 ** (depth - i))

farr.add(arr[-1])

farr.normalize()
render_arr(gfx.screen, farr)

while run:
events = pygame.event.get()

for event in events:
if event.type == QUIT:
run = 0

pygame.display.flip()

clock.tick(60)

Numpy: 00.639 seconds!


import random
import math
import time
import numpy

import pygame
from pygame.locals import *

class GFX():
def __init__(self):
pygame.init()

self.display_flags = DOUBLEBUF
rect = self.width, self.height = 256, 256

if pygame.display.mode_ok(rect, self.display_flags):
self.screen = pygame.display.set_mode(rect, self.display_flags)


def linear_interp(a, b, x):
return a * (1 - x) + b * x

def cosine_interp(a, b, x):
f = (1 - math.cos(x * math.pi)) * 0.5
return a * (1 - f) + b * f

def cubic_interp(v0, v1, v2, v3, x):
p = (v3 - v2) - (v0 - v1)
Q = (v0 - v1) - p
R = v2 - v0
S = v1

return P * x ** 3 + Q * x ** 2 + R * x + S


class Arr:
def __init__(self, w, h):
self.arr = numpy.zeros((w, h), float)

def size(self, w, h):
# Sanity checks
if w > 400 or h > 400:
raise Exception("Array size too large.")

self.arr = [[0] * w for i in range(h)]

def noise(self, w, h):
# Sanity checks
if w > 400 or h > 400:
raise Exception("Array size too large.")

print "noise"

# Create 2D array
self.arr = numpy.random.random_sample((w, h))

def smooth(self, ite):
print "smooth"

for i in range(ite):
soften = numpy.array(self.arr)

soften[1:,:] += self.arr[:-1,:]
soften[0,:] += self.arr[-1,:]

soften[:-1,:] += self.arr[1:,:]
soften[-1,:] += self.arr[0,:]

soften[:,1:] += self.arr[:,:-1]
soften[:,0] += self.arr[:,-1]

soften[:,:-1] += self.arr[:,1:]
soften[:,-1] += self.arr[:,0]

self.arr = soften / 5

def normalize(self):
print "normalize"

self.arr = (self.arr - self.arr.min()) / (self.arr.max() - self.arr.min())

return self.arr


def add(self, arr2):
self.arr += arr2.arr

def div(self, val):
self.arr /= val

def cosine_resize(self, mult):
# Sanity checks
if len(self.arr) * mult > 400:
raise Exception("Array size too large (tried resizing).")

print "linear resize"
w, h = self.arr.shape
w2, h2 = w*mult, h*mult

arr_new = numpy.zeros((w2, h2), float)
p0 = numpy.copy(self.arr)

p1 = numpy.zeros((w, h), float)
p1[:-1, :] = self.arr[1:, :]
p1[-1, :] = self.arr[0, :]

p2 = numpy.zeros((w, h), float)
p2[:, :-1] = self.arr[:, 1:]
p2[:, -1] = self.arr[:, 0]

p3 = numpy.zeros((w, h), float)
p3[:-1, :-1] = self.arr[1:, 1:]
p3[-1, :] = self.arr[0, :]

p3[:, -1] = self.arr[:, 0]

for nx in range(mult):
v0 = linear_interp(p0, p1, float(nx)/mult)
v1 = linear_interp(p2, p3, float(nx)/mult)
for ny in range(mult):
arr_new[nx::mult, ny::mult] = linear_interp(v0, v1, float(ny)/mult)

self.arr = arr_new

gfx = GFX()

run = 1
clock = pygame.time.Clock()

# run through 10 times for benchmarking purposes
t0 = pygame.time.get_ticks()
for it in xrange(10):
pw, ph = 256, 256
depth = 5

farr = Arr(pw, ph)

# Generate perlin noise
for i in range(depth):
d = 2 ** i

arr = Arr(pw,ph)
arr.noise(pw/d, ph/d)
arr.smooth(3)
arr.cosine_resize(d)
arr.div(2.**(depth-i))

farr.add(arr)

farr.normalize()

pygame.surfarray.use_arraytype("numpy")
print farr.arr.shape

tarr = numpy.zeros((256,256,3))
tarr[:,:,0] = farr.arr
tarr[:,:,1] = farr.arr
tarr[:,:,2] = farr.arr

pygame.surfarray.blit_array(gfx.screen, (tarr *256).astype(int))

print "elapsed: ",pygame.time.get_ticks()-t0

while run:
events = pygame.event.get()

for event in events:
if event.type == QUIT:
run = 0

pygame.display.flip()
clock.tick(60)

1 comments:

Manu kirjoitti...

Hello,

I found your code and made a numpy version of it. Rendering should be really faster with it:

#!/usr/bin/python



import math

import pygame

from pygame.locals import *

import numpy



def linear_interp(a, b, x):

return a*(1-x) + b*x



def cosine_interp(a, b, x):

f = (1 - math.cos(x * math.pi)) * 0.5

return a*(1-f) + b*f



def cubic_interp(v0, v1, v2, v3, x):

p = (v3 - v2) - (v0 - v1)

Q = (v0 - v1) - p

R = v2 - v0

S = v1

return P*x**3 + Q*x**2 + R*x + S





class Arr:

def __init__(self, w, h):

self.arr = numpy.zeros((w, h), float)



def noise(self, w, h):

print "noise"

self.arr = numpy.random.random_sample((w, h))



def smooth(self, ite):

print "smooth"

for i in range(ite):

soften = numpy.array(self.arr)



soften[1:,:] += self.arr[:-1,:]

soften[0,:] += self.arr[-1,:]



soften[:-1,:] += self.arr[1:,:]

soften[-1,:] += self.arr[0,:]



soften[:,1:] += self.arr[:,:-1]

soften[:,0] += self.arr[:,-1]



soften[:,:-1] += self.arr[:,1:]

soften[:,-1] += self.arr[:,0]



self.arr = soften / 5



def normalize(self):

print "normalize"

self.arr = (self.arr - self.arr.min()) / (self.arr.max() - self.arr.min())



def add(self, arr2):

self.arr += arr2.arr



def div(self, val):

self.arr /= val





def linear_resize(self, mult):

print "linear resize"



w, h = self.arr.shape

w2, h2 = w*mult, h*mult



arr_new = numpy.zeros((w2, h2), float)


p0 = numpy.copy(self.arr)



p1 = numpy.zeros((w, h), float)

p1[:-1, :] = self.arr[1:, :]

p1[-1, :] = self.arr[0, :]



p2 = numpy.zeros((w, h), float)

p2[:, :-1] = self.arr[:, 1:]

p2[:, -1] = self.arr[:, 0]



p3 = numpy.zeros((w, h), float)

p3[:-1, :-1] = self.arr[1:, 1:]

p3[-1, :] = self.arr[0, :]

p3[:, -1] = self.arr[:, 0]

for nx in range(mult):
v0 = linear_interp(p0, p1, float(nx)/mult)
v1 = linear_interp(p2, p3, float(nx)/mult)
for ny in range(mult):
arr_new[nx::mult, ny::mult] = linear_interp(v0, v1, float(ny)/mult)

self.arr = arr_new





pw,ph = 512, 512

depth = 5



farr = Arr(pw,ph)



# Generate perlin noise

for i in range(depth):



d = 2**i



arr = Arr(pw,ph)

arr.noise(pw/d, ph/d)

arr.smooth(3)

arr.linear_resize(d)

arr.div(2.**(depth-i))



farr.add(arr)



farr.smooth(4)

farr.normalize()



pygame.init()

if pygame.display.mode_ok((pw, ph)):

screen = pygame.display.set_mode((pw, ph))



pygame.surfarray.use_arraytype("numpy")

pygame.surfarray.blit_array(screen, (farr.arr * 256).astype(int))

pygame.display.flip()

run = True

while run:

for event in pygame.event.get():

if event.type == QUIT:

run = False