Skip to main content

Weave

Weave is a python module that includes a method of including C and C++ code inline with python. Has a slightly bigger overhead than the swig approach but is a lot easier to implement. And the code can be any dynamically created string. For example this block of python code calculates the fixed point multiplication of var1 and var2. The code is modified from a matlab algorithm worked on during my summer internship at Tait Electronics.

from scipy.weave import inline as inlineC

r = rounding and 1 or 0 # Blatent hack to convert from pythons True/False to 1/0 for C/C++

exp = """
signed int K,result;
signed long int temp;
temp = (long int)var1 * (long int)var2;
signed int sign = temp/abs(temp);
if(r) {
K = 1 << (numBits-1); temp = temp + K; } result = sign*(abs(temp) >> numBits);
if(result > fp_Max){
result = fp_Max;
}
if(result < result =" fp_Min;" return_val =" result;">

result = inlineC(exp,['var1','var2','numBits','fp_Min','fp_Max','r'])

It must be noted the C code is just a string to python, the string is then passed to scipy.weave.inline along with any variables required by the code. The only non standard piece of c is assigning return_val, this is set up by weave and can be assigned with any type to return into python. Also note the commented out printf statement in the C code – was very useful for debugging as it still outputs to standard out.

Weave is a quick and powerful way to include c code or optimize a bottleneck in an algorithm. The above example is probably to simple to get any speed up as its a very trivial problem and the overhead of calling C must be factored in. Weave is pretty awesome for when you have a loop in python you cannot get rid of that MUST go faster.

As with all optimization tho, ask yourself if you really need it?

Here is another example...

The original code:

from numpy import *
def
wastedLoop(n):

"""wastedLoop does alot of looping adding up the numbers 1 + 2 + ... N
wastedLoop(n) loops n times"""
p =
0

for
k in range(n+1):
p = p + k

print
p

Then at an ipython prompt do a quick timing test:

>>> %timeit wastedLoop(1000000)
10
loops, best of 3: 464 ms per loop

Ok so now lets use numpy functions instead of looping:

def numpySumMethod(n):
return
sum(arange(n+1))

>>> %timeit numpySumMethod(1000000)
100
loops, best of 3: 12.9 ms per loop
So we already have achieved a 35 times faster run time than the original. And have clearer code!

from scipy import weave
def
wastedLoop(n):
"""
wastedLoop does alot of looping adding up the numbers 1 + 2 + ... N

wastedLoop(n) loops n times

"""

p = int(0)

exp = """

int i;
for(i=0;i

weave.inline(exp,['p','n'])
return
p

%timeit wastedLoop(1000000)
10
loops, best of 3: 2.8 ms per loop



We see an improvement here but its not amazing... Just one more example, doing the same thing but with the knowledge about the problem. Using the algorithm:

def efficientMethod(n):
"""Return sum of 1+2+3...+N"""

return
n*(n+1)/2.0

>>> timeit efficientMethod(1000000)
1000000
loops, best of 3: 0.00000173 s per loop

And there we have it: 1.73┬Ás There is a lesson in that! A bit of math goes a long way! For the cases where you don't have insider knowledge however, it is clear numpy alone can suffice in most situations.

Stay tuned for a look at python extensions with swig.

P.S: What is with this editor for blogger? It is crap!!!

Comments

Popular posts from this blog

Matplotlib in Django

The official django tutorial is very good, it stops short of displaying
data with matplotlib - which could be very handy for dsp or automated
testing. This is an extension to the tutorial. So first you must do the
official tutorial!
Complete the tutorial (as of writing this up to part 4).

Adding an image to a view

To start with we will take a static image from the hard drive and
display it on the polls index page.
Usually if it really is a static image this would be managed by the
webserver eg apache. For introduction purposes we will get django to
serve the static image. To do this we first need to change the
template.



Change the template
At the moment poll_list.html probably looks something like this:


<h1>Django test app - Polls</h1> {% if object_list %} <ul> {% for object in object_list %} <li><a href="/polls/{{object.id}}">{{ object.question }}</a></li> {% endfor %} </ul> {% else %} <p>No polls are available.</p> …

Homomorphic encryption using RSA

I recently had cause to briefly look into Homomorphic Encryption, the process of carrying out computations on encrypted data. This technique allows for privacy preserving computation. Fully homomorphic encryption (FHE) allows both addition and multiplication, but is (currently) impractically slow.

Partially homomorphic encryption just has to meet one of these criteria and can be much more efficient.
An unintended, but well-known, malleability in the common RSA algorithm means that the multiplication of ciphertexts is equal to the multiplication of the original messages. So unpadded RSA is a partially homomorphic encryption system.

RSA is beautiful in how simple it is. See wikipedia to see how to generate the public (e, m) and private keys (d, m).

Given a message x it is encrypted with the public keys it to get the ciphertext C(x)with:

C(x)=xemodm
To decrypt a ciphertext

Bluetooth with Python 3.3

Since about version 3.3 Python supports Bluetooth sockets natively. To put this to the test I got hold of an iRacer from sparkfun. To send to New Zealand the cost was $60. The toy has an on-board Bluetooth radio that supports the RFCOMM transport protocol.



The drive protocol is dead easy, you send single byte instructions when a direction or speed change is required. The bytes are broken into two nibbles: 0xXY where X is the direction and Y is the speed. For example the byte 0x16 means forwards at mid-speed. I was surprised to note the car continues carrying out the last given demand!

I let pairing get dealt with by the operating system. The code to create a Car object that is drivable over Bluetooth is very straight forward in pure Python:

importsocketimporttimeclassBluetoothCar:def__init__(self,mac_address="00:12:05:09:98:36"):self.socket=socket.socket(socket.AF_BLUETOOTH,socket.SOCK_STREAM,socket.BTPROTO_RFCOMM)self.socket.connect((mac_address,1))def_write(self,data_byte):…