Wednesday, 30 January 2013

Quick Delivery for Mobile

I have signed up for my friend Sam's Mobile Development Class, in the past I have built and run backends for mobile sites but have never had too much to do with the device side and his course seemed like a good chance to fill in the knowledge pothole. One of the assignments for week 1 was to write a 'contractual obligation' blog post -which is why you're suffering this; a second, more interesting, assignment was to watch this mobile dev introduction on Udemy.

Although it was for managers, shouldn't scoff I am one (sometimes),the set of lectures gave a good overview of some of the options for delivering mobile sites and apps.

Back in the day I was Head of Development for a company called Cantos, and made a now defunct mobile site for them, it broke when we put up the current web site , we did do a second version for the new Drupal site but it was never given the green light to go live, which is why I don't give a link to it.

When we were developing the mobile sites we did a lot of googling around looking for tools, guides and advice and I wish the Udemy video and the options it mentions were around then -we might have saved a lot of time and we would have been much more future proofed.

Tools like Cordova / PhoneGap offer a quick, cross-platform, entry to the market and Titanium a short cut to the native app experience. For the sites we built jQuery Mobile would have allowed us to offer a richer user experience to our customers. The video lectures discuss the pros and cons of each technology and makes suggestions about what to use when, including when you should go fully native. All in all 50 minutes well spent and I look forward to playing with all of them.

Wednesday, 16 January 2013

The power of the Matrix

Do you want to make your code run 100 times faster, at least in python? Try rewriting it in matrix form using numpy.

I came across this when implementing the Floyd Warshall Algorithm for finding all shortest paths in a graph as part of th Algorithms 2 course at Coursera. The guts of Floyd Warshall are 3 nested for loops that iterate over all the nodes, here's the Python code :

# v_sz = number of vertices
for k in range(1,v_sz) :
  for i in range(0,v_sz) :
    for j in range(0,v_sz) :
      new_len = A[k-1][i][k] + A[k-1][k][j]
      old_len = A[k-1][i][j]
      if new_len < old_len :
        A[k][i][j] = new_len
      else :
        A[k][i][j] = old_len

This takes around 30 minutes to run on my PC for the supplied graph of 1000 vertices.

Other people were getting much better times and the hint was given to try rewriting this in matrix form -took me a while but I had used Octave as part of the Machine Learning and Neural Nets courses, and together with the Numpy for Matlab Users page I got to :

for k in range(1,v_sz) :
  #tile() is the equivalent to repmat -copies a vector repeatedly into a matrix
  i2k = np.tile(M[0:v_sz][:,k],(1,v_sz))
  k2j = np.tile(M[k][:],(v_sz,1))
  M = np.minimum(M, i2k + k2j)

This runs in ~10 seconds, a good chunk of which will be loading in the data! Pretty impressive and there would be more to go as I think I can shave time off the data load.

What it shows is that numpy is heavily optimised, probably through use of underlying C libraries, for matrix computation and that it is always going to be worth looking to see if a set of for loops can be recast into vector and matrix manipulations instead.