RLE? That’s so yesterday!

Before writing my RLE implementation, a friend sent me a link to the blist package for Python.

I didn’t see anything amazing on the front page. Makes a 5M size list. Sure, whatever.

What the front page fails to say is that creating that 5M size blist is insanely fast. Because it doesn’t blindly allocate memory like a normal Python list would.

The “blist” list type is faster to add / remove than a Python list, and it supports copy-on-write semantics.

So I’m actually going to remove my cryptic RLE encoding and return to normal 3D array semantics using blists!

Another reason to not use RLE, at least my implementation:

import time

size = 2048
print "Length: %s" % str(size)
setValues = size / 2
print "Setting %s values" % str(setValues)

print "PARLE"
import PARLE
parle = []
PARLE.fill( parle, 0, size )

startTime = time.time()
for i in xrange( setValues ):
    PARLE.setValueAt( parle, i * 2, 1 )
endTime = time.time()
print "Time: %s" % str(endTime - startTime)
parle = None

time.sleep( 1 )

print "blist"
import blist
bl = blist.blist([0])
bl *= size

startTime = time.time()
for i in xrange( setValues ):
    bl[ i * 2 ] = 1
endTime = time.time()
print "Time: %s" % str(endTime - startTime)
parle = None

Outputs the following:

Length: 2048
Setting 1024 values
PARLE
Time: 0.210000038147
blist
Time: 0.000999927520752
A BList with 2048 values is over 200 times faster.
Advertisements

One Response to “RLE? That’s so yesterday!”

  1. While blist on its own is fast I cannot seem to find a fast one to initialize a 3d array of blist arrays. I much be missing something anyone have any tips? Every time i try and make a fast 3d initializer as you indicate is possible and better using blist i either end up making the whole 3d array a reference of the first blist array or it takes ages while creating each array for each of the dimensions.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: