Wow, things are crazy. Classes and the rest of my responsibilities have hit like a tidal wave, and I finally am able to start swimming towards the surface to get some air. I’m only taking 3.5 classes this term, but I’m also working on my awesome UROP 15-20 hours a week, on top of being SIPB Chair, writing a game for the MIT Assassin’s Guild, being pika’s senior house manager, and being pika’s computer chair. I always love being this busy, but sometimes I wonder if I like it a little too much. It’s hard to find a term when I’m not in over my head. But, regardless, things are going well and I’m excited to almost be done with my undergraduate career!
So, what else? I don’t really have the time to compose a full-fledged post (I’ll get to the rest of those security posts soon, I promise…), so I’m going to talk about why Python’s NumPy is awesome.
For my UROP this summer, I created an experiment which involves looking at towers of blocks; I coded the whole interface in Python using Panda3D. One of the first tasks was to create a way to randomly generate towers, with a few constraints: blocks may only be placed within a n by n square in the xy plane, and blocks must be “locally stable” – that is, if you just look at the block you are placing and the block(s) directly beneath it, the block you’re placing needs to be able to sit on the block(s) below it and not fall off. Of course, this guarantees nothing about the overall stability of the tower, but it does guarantee that individual blocks themselves are stable. In order to represent which blocks are where, a “depth map” is maintained, where the value for each grid square is the z value of the highest block at that point.
Unfortunately, having the “locally stable” constraint makes it more difficult to place blocks. You can’t just randomly pick a pair of (x, y) coordinates to place it, because they need to be stable. You want to be able to examine the list of all locally-stable positions, and then choose a coordinate pair from that. So how do you determine if it’s locally stable? The naive approach (which is the one that I initially took) is to iterate through every single point and check to see if it’s locally stable. To see if it’s stable, you need to check every point within the area that the block occupies. If we assume the origin to be at the center of the block, then we need the block to be supported in x, -x, y, and -y, which essentially means that there must be at least two points of the maximum height for that sub-“depth map” that are diagonally across from each other. So, we are looping through every coordinate in the world and then through every coordinate that the block covers. Long story short, it’s slooowwww.
So, where does NumPy come into this? If we use matrix operations instead of for loops, then the whole stability calculation becomes lightning fast. At the start of the program, the depth map is initialized to all zeros, and then a list is created of every possible “slice” – that is, the area where a block could potentially rest. Then, when calculating which spots are valid, we look at each slice, find the maximum, and then compare the slice to the maximum (e.g. numpy.array(slice > numpy.max(slice), dtype=numpy.bool)). Then, you do an element-wise and with a bitmask, which represents whether a given coordinate provides x, -x, y, and/or -y. Finally, you sum over every coordinate in the slice matrix, and if the result has a 1 for every bit, then it is a valid spot to place a block.
It sounds like a lot of these operations require iteration and wouldn’t be much faster than using for loops anyway. In some cases, I’ve glossed over the actual techniques I used to do the calculation (e.g. finding the maximum of each slice can be done with matrix operations, and does not require a loop). In other cases, I am sure that NumPy does use loops, but in a very effective and efficient manner. If I had the time to source dive, I’d take a look and see what the running times for their algorithms are.
Anyway, enough of my sleep-deprived ramblings. I am quite happy with how NumPy enables fast and easy matrix manipulations. Perhaps I am just fascinated by the efficiency of matrix operations themselves. But, in any case, NumPy is another point in Python’s favour – while Python is not my favourite language, when it comes to cases like this, it is certainly the most convenient.