Alex Bowe

Failing at Google Interviews

Tue, 06 Sep 2011 02:32:00 -0700

I’ve participated in about four sets of interviews (of about 3 interviews each) for various Google positions. I’m still not a Googler though, which I guess indicates that I’m not the best person to give this advice. However, I think it’s about time I put in my 0.002372757892 bitcoins. I recently did exactly this to help my brother prepare for his interviews and the guy kicked ass. If he gets the job I’m going to take as much credit for it as I can ;)

During my interviews I didn’t sign a NDA, but I do respect the effort that interviewers put into preparing their questions so I’m not going to discuss them. That doesn’t matter though, because you probably won’t get the same questions anyway :) and the algorithm stuff is far from the whole story.

This post is mainly about the rituals I perform during preparation for the interviews, and the lessons I have learned from them. I am of the strong opinion that everyone should apply for a job at Google.

Why Should I?!

Not everyone wants to work for Google, but there are valuable side effects to a Google interview. Even if you don’t think you want a job there, or think that you are under-qualified, it is a great idea to just try for one. The absolute worst thing that could happen is that you have fun and learn something.

A couple of the things I learned are algorithms for (weighted) random sampling, queueing, vector calculus, and some cool applications of bloom filters.

The people you will talk to are smart, and it’s a fun experience to be able to solve problems with smart and passionate people. One of my interviews was just a discussion about the good and bad parts (in our opinions) of a bunch of programming languages (Scheme, Python, C, C++, Java, Erlang). We discussed SICP and the current state of education, and he recommended some research papers for me to read. All the intriguing questions and back-and-forth made me feel like I was being taught by a modern Socrates (perhaps Google should consider offering a Computer Science degree taught entirely with interviews :P).

Sadly, a subsequent interview stumped me because I didn’t understand the requirements. Even the stumping interviews have given me a great chance to realise some gaps in my knowledge and refine my approach. I knew that it was important to get the requirements right, but this really drove it home.

I hope I’ve got you curious about what you could learn from a Google interview. If you are worried about the possible rejection, treat it as a win in a game of Rejection Therapy. You can re-apply as many times as you like, so you could also think of it as TDD for your skills, and you like TDD, right?

How To Prepare – Technical

When you are accepted for a phone interview, Google sends you an email giving you tips on how to prepare. Interestingly, this has been a different list each time. I’ll discuss the one I liked the most. They only give advice on the technical side. I will also discuss what I think are some other important aspects to be mindful of.

First of all, you are going to want to practice. Even if you have been coding every day for years, you might not be used to the short question style. Project Euler is the bomb for this. You will learn some maths too, which will come in handy, and it builds confidence. Do at least one of these every day until your interview.

You will also want some reading material. Google recommended this post by Steve Yegge, which does a good job of calming you. They also recommended another post by Steve Yegge where he covers some styles of questions that are likely to be asked. Yegge recommends a particular book very highly – The Algorithm Design Manual.

More than any other book it helped me understand just how astonishingly commonplace (and important) graph problems are – they should be part of every working programmer’s toolkit. The book also covers basic data structures and sorting algorithms, which is a nice bonus. But the gold mine is the second half of the book, which is a sort of encyclopedia of 1-pagers on zillions of useful problems and various ways to solve them, without too much detail. Almost every 1-pager has a simple picture, making it easy to remember. This is a great way to learn how to identify hundreds of problem types.

I haven’t read the whole thing, but what I have read of it is eye and mind opening. This wasn’t recommended to me directly by Google recruiting staff, but one of my interviewers emailed me a bunch of links after, including a link to the page for this book. There was a recent review of this book featured on Hacker News. It is very good. The author, Steve Skiena, also offers his lecture videos and slides – kick back and watch them with a beer after work/uni.

If the size of The Algorithm Design Manual is daunting and you want a short book to conquer quickly (for morale reasons), give Programming Pearls a read. Answer as many questions in it as you can.

The phone interviews usually are accompanied by a Google doc for you to program into. I usually nominate Python as my preferred language, but usually they make me use C or C++ (they often say I can use Java too). I was rusty with my C++ syntax, but they didn’t seem to mind. I just explained things like using templates, even though I can never remember the syntax for the tricks.

Speaking of tricks, you get style points for using features of the language that are less well known. I had an interviewer say he was impressed because I used Pythons pattern matching (simple example: (a, b) = (b, a)), list comprehensions, map/reduce, generators, lambdas, and I guess decorators could help make you look cool, too. Only use them if they are useful though!

How To Prepare – Non-Technical

There will also be a few non-technical questions. When I did my first one, a friend recommended that I have answers ready for cookie-cutter questions like “Where do you see yourself in ten years?” and “Why do you want to work for Google?”. Don’t bother with that! Do you really think one of the biggest companies in the world will waste their time asking questions like that? Everyone candidate would say the same answer, something about leading a team and how Google would let you contribute to society, or whatever (great, but everyone wants that).

They will ask you about your previous work and education, though, and pretty much always ask about a technical challenge you overcame. I like to talk about a fun iterative A* search I did at my first job (and why we needed it to be iterative). You can probably think of something, don’t stress, but better to think of it before the interview.

And have a question ready for when they let you have your turn. Don’t search for “good questions to ask in technical interviews”, because if it isn’t your question, you might be uninterested if the interviewer talks about it for a long time. Think of something that you could have a discussion about, something you are opinionated about. Think of something you hated at a previous job (but don’t come across as bitter), how you would improve that, and then ask them if they do that. For me, I was interested in the code review process at Google, and what sort of project they would start a beginner be assigned to.

I know someone who asked questions from The Joel Test. The interviewer might recognise these questions and either congratulate you on reading blogs about your field, or quietly yawn to themselves. It’s up if you want to take that risk. I definitely think it’s better to ask about something that has the potential to annoy you on a personal level if they don’t give you the answer you want ;) it’s subtle but people can detect your healthy arrogance and passion.

If you have a tech blog, refer to it. I’ve had interviewers discuss my posts with me (which they found from my resume). Blogs aren’t hard to write, and even a few posts on an otherwise barren blog will make you look more thoughtful.

Finally, the absolute best way to prepare for a Google interview is to do more Google interviews, so if you fail, good for you! ;)

Just Before the Interview

Here are a few things that help me handle the pressure before an interview.

One time I was walking to an interview in the city (not a Google interview) and I was really nervous, even though I didn’t care either way if I got the job. I thought about how the nerves wouldn’t be an issue after the interview, because I’d have already done the scary thing by then. I couldn’t time travel, but I instead wondered if there is a way to use up the nerves on something else. There was a girl walking next to me, so I turned to her and said she was dressed very nicely. She said a timid “thank you” and picked up pace to get away from me. I laughed at my failure, but suddenly I didn’t feel so scared about the interview. I think this is a great example of why Rejection Therapy is worthwhile.

So yeah, talk to a stranger. If you are waiting at home for a phone call though, another thing I do is jack jumps, dancing, or jogging on the spot just to make myself forget the other reason my heart is pounding so fast.

During the Interview

If you are doing a phone interview, answer it standing up (you can sit down after) and pace around a little bit. Smile as you talk, as well. You should also take down their name on paper ready to use a few times casually. These are tricks from the infamous How to Win Friends and Influence People. Maybe these alone wont make you likeable, but I think it causes you to think about the other person and stop being so self conscious, which helps you to relax. You’ll be one charming motherfucking pig.

Take some time to think before answering, and especially to seek clarification on the questions. Ask what the data representation is. I’ve found that they tend to say “whatever you want”. In a graph question, I said “Okay, then it’s an adjacency matrix”, which made the question over and done with in ten seconds. The interviewer seemed to like that, so don’t be afraid to be a (humble) smart ass.

You might recognise the adjacency matrix as potentially being a very poor choice, depending on the nature of the graph. I did discuss when this might not be a good option. In fact, for every question, I start off by describing a naive approach, and then refine it. This helps to verify the question requirements, and gives you an easy starting point.

One last thing! Google schedules the interview to be from 45 minutes to an hour. I have had awkward moments at the end of interviews where the interviewer mentions that our time is nearly up, and then asks another question, or asks if I have any questions. It made me feel like he was in a rush, so I didn’t feel like expanding on things much. Now, I recommend taking as much time as they will give you. Keep talking until they hang up on you if you have to :) Although it might help to say “I don’t mind if we go over, as long as I’m not keeping you from something” when the interviewer mentions the time.

Reflect

Steve Yegge says there are lots of smart Googlers who didn’t get in until their third attempt (I still haven’t gotten in after my fourth, and I don’t think I’m stupid). As I mentioned, I’m writing this post because I found the process of doing a Google interview at all to be very rewarding.

It is important to reflect afterwards in order to reap the full benefits of interviewing at Google. If you did well, why? But more importantly, if you feel you did poorly, why? Google won’t give feedback, which can be a bit depressing at times. After each interview write notes about what you felt went well and what didn’t – this way you can look back if you don’t get the job, and decide what you need to work on. This post is the culmination of my reflections and the notes – if you decide to write a blog post, I’d enjoy reading it and will link it here.

If you want more blog posts to read about how to get better at Computer Science, I recently found this post by Matt Might to be a good target to aim for. Check out Ten Things Every Computer Science Major Should Learn as well, and my previous post Advice to CS Undergrads (the links at the end in particular).

Have you really read this far? Consider adding me to Twitter and telling me what you thought :)

Permalink | Leave a comment »

FM-Indexes and Backwards Search

Tue, 23 Aug 2011 07:02:00 -0700

Last time (way back in June! I have got to start blogging consistently again) I discussed a gorgeous data structure called the Wavelet Tree. When a Wavelet Tree is stored using RRR sequences, it can answer rank and select operations in O(log A) time, where A is the size of the alphabet. If the size of the alphabet is 2, we could just use RRR by itself, which answers rank and select in O(1) time for binary strings. RRR also compresses the binary strings, and hence compresses a Wavelet Tree which is stored using RRR.

So far so good, but I suspect rank and select queries seem to be of limited use right now (although once you are familiar with the available structures, applications show up often). One of the neatest uses of rank that I’ve seen is in substring search, which is certainly a wide reaching problem (for a very recent application to genome assembly, see Jared Simpson’s paper from 2010 called Efficient construction of an assembly string graph using the FM-index)

Also, my apologies but I am using 1-basing instead of 0-basing, because that is how I did my diagrams a year ago :) (and bear with my lack of nicely typeset math, I am migrating to GitHub pages where I will be allowed to use Mathjax soon)

Suffix Arrays

There is a variety of Suffix Array construction algorithms, including some O(N) ones (Puglisi et al. 2007). However, I will explain it from the most common (and intuitive) angle.

In its simplest form, a suffix array can be constructed for a string S[1..N] like so:

Construct an array of pointers to all suffixes S[1..N], S[2..N], …, S[N..N].
Sort these pointers by the lexicographical (i.e. alphabetical) ordering of their associated suffixes.

For example, the sorting of the string ‘mississippi’ with terminating character $ would look like this:

Burrows-Wheeler Transform

The Burrows-Wheeler Transform (BWT) is a was developed by Burrows and Wheeler to reversibly permute a string in such a way that characters from repeated substrings would be clustered together. It was useful for compression schemes such as run-length encoding.

It is not the point of this blog to explain how it works, but it is closely linked to Suffix Arrays: BWT[i] = S[SA[i] – 1, BWT[1] = $ (it wraps around) for the original string S, Suffix Array SA, and Burrows-Wheeler Transform string BWT. In other words, the ith symbol of the BWT is the symbol just before the ith suffix. See the image below:

In particular, BWT[1] = S[SA[1] – 1] = S[12 – 1] = S[11] = ‘i’ (or the 11th symbol from the original string ‘mississippi’)

Ferragina and Manzini (Ferragina et al. 2000) recommended that a BWT be paired with a Suffix Array, creating the so-called FM-Index, which enables backward search. The BWT also lets us reconstruct the original string S (not covered in this blog), allowing us to discard the original document – indexes with this property are known as self indexes.

Backward Search

This is where rank comes in. If it is hard to follow (it is certainly not easy to explain) then hang in there until the example, which should clear things up.

Since any pattern P in S (the original string) is a prefix of a suffix (our Suffix Array stores suffixes), and because the suffixes are lexicographically ordered, all occurrences of a search pattern P lie in a contiguous portion of the Suffix Array. One way to hone in on our search term is to use successive binary searches. Storing the BWT lets us use a cooler way, though…

Backward search instead utilises the BWT in a series of paired rank queries (which can be answered with a Wavelet Tree, for example), improving the query performance considerably. Backward search issues p pairs of rank queries, where p denotes the length of the pattern P. The paired rank queries are:

Where s denotes the start of the range and e is the end of the range. Initially s = 1 and e = N. If at any stage e < s, then P doesn’t exist in S.

As for C… C is a lookup table containing the count of all symbols in our alphabet which sort lexicographically before P[i]. What does this mean? Well, C would look like this:

Which means that there aren’t any characters in S that sort before ‘$’, one that sorts before ‘i’ (the ‘$’), five that sort before m (the ‘$’ and the ‘i’s) and so on. In the example I store it in a less compact way as the column F (which contains the first symbol for each suffix – essentially the same information, since each suffix is sorted), so it might be easier to follow (wishful thinking).

Why is this called backwards search? Well, our index variable i actually starts at |P| (the last character of our search pattern), and decreases to 1. This maintains the invariant that SA[s..e] contains all the suffixes of which P[i..|P|] is a prefix, and hence all locations of P[i..|P|] in S.

Example

Let’s practice this magic spell… Let our search pattern P be ‘iss’, and our string S be ‘mississippi’. Starting with i = 3, c = P[i] = ’s'. The working for each rank query is shown below each figure. I’m representing the current symbol as c to avoid confusion between ‘s’ and s and s′.

Here (above) we are at the first stage of backwards search for ‘iss’ on ‘mississippi’ string – before any rank queries have been made. Note: we do not store the document anymore – the gray text – and we don’t store F, but instead store C – see section on Backward Search.

Starting from s=1 and e=12 (as above) and c = P[i] = ’s' where i = 3, we make our first two rank queries:

After the above, we are now at the second stage of backwards search for ‘iss’ on ‘mississippi’ string. All the occurrences of ’s' lie in SA[9..12].

From s = 9 and e = 11, and c = P[i] = ’s' where i = 2, our next two rank queries are:

We are now at the third stage of backwards search for ‘iss’ on ‘mississippi’ string. All the occurrences of ‘ss’ lie in SA[11..12].

From s = 11 and e = 12, and c = P[i] = ‘i’ where i = 1, our final two rank queries are:

This is the fourth and final stage of our backwards search for ‘iss’ in the string ‘mississippi’. All the occurrences of ‘iss’ lie in SA[4..5].

It impresses me every time…

Play Time

No doubt you want to get your hands dirty. I have played around with libdivsufsort before, although I think you may have to implement backward search yourself (it’d be a good exercise), since it doesn’t appear to come with fast rank query providers. For rank structures for your BWT you might want to check out libcds. In fact there are heaps out there, but I haven’t used any others. Hopefully someone will comment below with a good recommendation of this.

Also, please comment here if you develop something cool with it :) and as always, if you have journeyed this far, consider following me on Twitter: @alexbowe.

Bibliography

Ferragina, P. and Manzini, G. (2000). Opportunistic data structures with applications. Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, pages 390–398.

S. J. Puglisi, W. F. Smyth, and A. Turpin. A taxonomy of suffix array construction algorithms. ACM Computing Surveys, 39(2):1–31, 2007. Jared Simpson’s paper from 2010 called *Efficient construction of an assembly string graph using the FM-index.

Simpson, J. T. and Durbin, R. (2010). Efficient construction of an assembly string graph using the FM-index. Bioinformatics, 26(12):i367–i373.

Permalink | Leave a comment »

Wavelet Trees

Tue, 28 Jun 2011 06:35:00 -0700

In my last post I introduced a data structure called RRR, which is used to quickly answer rank queries on binary sequences, and provide implicit compression.

Today I will talk about an elegant way of answering rank queries on sequences over larger alphabets. The structure is called the Wavelet Tree, which organises a string into a hierarchy of bit vectors. A rank query has time complexity is O(log_2 A), where A is the size of the alphabet. It was introduced by Grossi, Gupta and Vitter in their 2003 paper High-order entropy-compressed text indexes [4] (see the Further Reading section for more papers). It has since been featured in many papers [1, 2, 3, 5, 6].

If you store the bit vectors in RRR sequences, it may take less space than the original sequence. Alternatively, you could store the bit vectors in the rank indexes proposed by Sadakane and Okonohara [7]. It has a different approach to compression. I will talk about it another time ;) – fortunately, I will be studying under Sadakane-san at a later date.

In a different future post, I will show how Suffix Arrays can be used to find arbitrary patterns of length P, by issuing 2P rank queries. If using a Wavelet Tree, this means a pattern search has O(P log_2 A) time complexity, that is, the size of size of the ‘haystack’ doesn’t matter, it instead depends on the size of the ‘needle’ and size of the alphabet.

Construction

A Wavelet Tree converts a string into a balanced binary-tree of bit vectors, where a 0 replaces half of the symbols, and a 1 replaces the other half. This creates ambiguity, but at each level this alphabet is filtered and re-encoded, so the ambiguity lessens, until there is no ambiguity at all.

The tree is defined recursively as follows:

Take the alphabet of the string, and encode the first half as 0, the 2nd half as 1: { a, b, c, d } would become { 0, 0, 1, 1 }
Group each 0-encoded symbol, { a, b }, as a sub-tree;
Group each 1-encoded symbol, { c, d }, as a sub-tree;
Reapply this to each subtree recursively until there is only one or two symbols left (when a 0 or 1 can only mean one thing).

For the string “Peter Piper picked a peck of pickled peppers” (spaces and a string terminator have been represented as _ and $ respectively, due to convention in the literature) the Wavelet Tree would look like this:

note: the strings aren’t actually stored, but are shown here for convenience

It has the alphabet { $, P, _, a, c, d, e, f, i, k, l, o, p, r, s, t }, which would be mapped to { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1 }. So, for example, $ would map to 0, and r would map to 1.

The left subtree is created by taking just the 0-encoded symbols { $, P, _, a, c, d, e, f } and then re-encoding them by dividing this new alphabet: { 0, 0, 0, 0, 1, 1, 1, 1 }. Note that on the first level an e would be encoded as a 0, but now it is encoded as a 1 (it becomes a 0 again at a leaf node).

We can store the bit vectors in RRR structures for fast binary rank queries (which are needed, as described below), and compression :) In fact, since it is a balanced tree, we can concatenate each of the levels and store it as one single bit vector.

Querying

Recall from my last post that a rank query is the count of 1-bits up to a specified position. Rank queries over larger alphabets are analogous – instead of a 1, it may be any other symbol:

After the tree is constructed, a rank query can be done with log A (A = alphabet size) binary rank queries on the bit vectors – O(1) if you store them in RRR or another binary rank index. The encoding at each internal node may be ambiguous, but of course it isn’t useless – we use the ambiguous encoding to guide us to the appropriate sub-tree, and keep doing so until we have our answer.

For example, if we wanted to know rank(5, e), we use the following procedure which is illustrated below. We know that e is encoded as 0 at this level, so we take the binary rank query of 0 at position 5:

Which is 4, which we then use to indicate where to rank in the 0-child: the 4th bit (or the bit at position 3, due to 0-basing). We know to query the 0-child, since that is what e was encoded as at the parent level. We then repeat this recursively:

At a leaf node we have our answer. I would love to explain why this works, but it is fun and rewarding to think about it yourself ;)

There are also ways to provide fast select queries, but once again I will leave that up to you to research. The curious among you might also be interested in the Huffman-Shaped Wavelet Tree described by Mäkinen and Navarro [5].

Using Your New Powers for Good

Feel free to implement this yourself, but if you want to get your hands dirty right away, all-around-clever-guy Francisco Claude has made an implementation available in his Compressed Data Structure Library (libcds). If you create something neat with it be sure to report back ;)

And if you read this far, consider following me on Twitter: @alexbowe.

YaRRR Me Hearties - a post about a succinct data structure (not pirates, sorry)

Tue, 31 May 2011 22:12:00 -0700

This blog post will give an overview of a static bitsequence data structure known as RRR, which answers arbitrary length rank queries in O(1) time, and provides implicit compression.

As my blog is informal, I give an introduction to this structure from a birds eye view. If you want, read my thesis for a version with better markup, and follow the citations for proofs by people smarter than myself :)

My intended future posts will cover the other aspects of my thesis, including generalising RRR (for sequences over small alphabets), Wavelet Trees (which answer rank queries over bigger alphabets), and Suffix Arrays (a text index which – when combined with the above structures – can answer queries in O(P log A) time, when P is the length of the search pattern, and A is the alphabet size).

Update: I have now posted about Wavelet Trees! Check it out here.

Example Problem

Cracking the Oyster, the first column of Programming Pearls, opens with a programmer asking for advice when sorting around ten million unique seven-digit integers – phone numbers.

After some discussion, the author concludes that a bitmap should be used. If we wanted to store ten million integers, we could use an array of 32-bit integers, consuming 38 MB, or we could represent our numbers as positions on a number line.

All of these phone numbers will be within the range [0000000, 9999999]. To represent the presence of these numbers, we only need a bitmap 10⁷ bits long, about 1 MB, which would represent our number line. Then, for a bitmap M, if we want to store phone number p, we set the bit M[p] to 1. Sorting would involve setting the numbers that are present to 1, then iterating over the bitmap, printing the positions of the 1-bits – O(N) time.

In the following sections, I will detail operations that can be done on bitmaps, named rank and select, and explain how to answer rank queries in O(1) time, and implicitly compress the bitmap. Using rank and select, a compressed bitmap can be a very powerful way to store sets. This isn’t limited to just sets of numbers, all sorts of things, such as sets of graph nodes for example; A friend of mine is using succinct bitmaps to represent De Bruijn graphs, which are used in genome assembly.

Extension: Rank

Allow me to extend the problem. I want to query our simple phone number database to see how many phone numbers are allocated within the range $[0005000, 0080000]$. I could iterate over that range and update a counter whenever I encounter a 1-bit. Actually, this operation is what is known as a rank operation.

The operation rank(i) is defined as the number of set bits (1s) in the range [0, i] (or [0, i) in some papers). In the bitstring above, the answer to rank(5) is 3… This is a generalisation of the popcount operation which counts all set bits, which I have discussed before. rank(i) can be implemented by left-shifting L - i bits (where L is the length of the datatype you are using, int, long, etc) to remove the unwanted bits, then calling popcount on the resulting value. This could be done iteratively over an array if you want, but I will discuss a much faster way below.

Then, the above question can be answered as: rank(0080000) - rank(0005000 - 1). This will give us just the number of 1s between 0005000 and 0080000.

This isn’t the only place we would use a popcounts; it happens that popcounts are common enough that we want to optimise them. Check out this blog post at valuedlessons.com for a discussion and empirical comparison of several fast approaches.

RRR

As it happens, we can build a data structure for static bitmaps that answers rank queries in O(1) time, and provides implicit compression. It is what is known as a succinct data structure, which means that even though it is compressed, we don’t need to decompress the whole thing t operate on it efficiently. Sadakane (a big name in succinct data structures) gives a nice analogy in his introduction of the field, likening it to forcing dehydrated noodles apart with your chopsticks (decompression) as you are rehydrating them, but before the whole thing is fully cooked and separated. This allows you to keep some of the noodles compressed while you eat the decompressed fragment.

Since it is static it isn’t well suited for a bitmap which you want to update (although work has been done toward this), it is still really cool :)

The structure I’m referring to is named RRR. It sounds like a radio station, but it is named after its creators: Raman, Raman, Rao, from their 2002 paper Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. Its a data structure I had to become intimately involved with for my honours thesis, where I extended it for sequences of larger (but still small) alphabets. If you want to answer rank queries on large alphabets, a wavelet tree might be what you are after, but that will be covered in a different blog post (or you could read my thesis!).

In my last post (Generating Binary Permutations in Popcount Order) I discussed how to compress a bitstring by replacing blocks of a certain blocksize with their corresponding pop number, and (variable length) offset into a lookup table. I briefly mentioned building an index over it to improve lookup as well.

RRR: Construction

To construct a RRR sequence we divide our bitmap into blocks, as I mentioned in my previous blog post. These are grouped in superblocks, too, which allows us to construct an index to enable O(1) rank queries. In the following image, I have fragmented the bitmap using a blocksize of b = 5, and grouped them with a superblock factor of f = 3 – so each superblock is three blocks.

First we replace the blocks with a pair of values, a class value C and offset value O, which are used together as a lookup key into a table of precomputed (small – for each possible block only) ranks – this is demonstrated in the figure below. This is the same as the previous blog post, although in that I called the “class” P. This is because the class of a block is defined as the popcount – the number of set bits – in the block: class(B) = popcount(B) for block B.

The table is shared among all your RRR sequences, and is in fact a table of tables, where C points to the first element for the ranks of a given popcount:

For this table (let’s call it G), for a given class C, the sub-table at G[C] has b Choose C entries, which correspond to all possible permutations that have a popcount of C. This means that while our C values will always be log(b + 1) (the number of bits to represent values 0, 1, 2… b – these are all possible popcount values for the blocksize), but our O values will vary in size, requiring log(b Choose C) bits (oh yeah, and of course I’m using log_2 here :)). During a query, we can use our C values to work out how many bits will follow for the O values.

Using this approach alone we get the compression, but not O(1) ranks. C is fixed width, the compression comes from O being varied width.

In order to get the O(1) ranks we use a method discussed by Munro in Tables, 1996. This is where the superblocks come in to play:

For each superblock boundary we store the global rank up to that position. We also store a prefix sum of the bits, which gives us the address to the first block in the next superblock (since it is variable length!). This allows us to not require iterating over the whole RRR sequence, but instead going straight to the required superblock. We will only need to iterate over the blocks within a superblock, so it is now bound by whatever your superblock factor is.

RRR: Querying

To calculate rank(i):

Calculate which block our index is in as i_b = i/b. (i_b is the global index of the block)
Calculate which superblock our block resides in as i_s = i_b/f. (i_s is the index of the superblock)
Set result to the sum of previous ranks at is boundary (which is pre- calculated).
Using each blocks class-offset pair (c,o) after the boundary at is, add the rank for that entire block to result. 5. Repeat previous step until we reach i_b. We then add rank(j,c) (from i_b, not the global rank) to our result,where j = i mod b, and is the position we are querying local to i_b. Our final answer is result.

Select

Select is the inverse operation to rank; it answers the question “at which position is the ith set bit?”. To tie this in with the phone numbers example, maybe we want to find out the fiftieth phone number in the set (excluding unassigned numbers). This is a way we can index just the present elements of a bitmap. It turns out select can be answered in O(1) time as well. I won’t cover select here, as my future posts (and thesis) will mainly use rank. You can read about it in the RRR paper.

Go Forth and…

Feel free to implement this (somewhat complicated) data structure yourself, or you can use a pre-rolled one by my friend Francisco Claude in his LIBCDS – Compressed Data Structure Library.

If you read this far, consider adding me to twitter :) or you may enjoy reading my post on Wavelet Trees.

Permalink | Leave a comment »

Generating Binary Permutations in Popcount Order

Sun, 08 May 2011 07:11:00 -0700

I’ve been keeping an eye on the search terms that land people at my site, and although I get the occasional “alex bowe: fact or fiction” and “alex bowe bad ass phd student” queries (the frequency strangely increased when I mentioned this on Twitter) I also get some queries that relate to the actual content.

One query I received recently was “generating integers in popcount order”, I guess because I mentioned popcounts (the number of 1-bits in a binary string) in a previous post, but the post wasn’t able to answer that visitors question.

What would this be used for? Among other applications, I have used it for generating a table of numbers ordered by popcount, which I used in a compression algorithm: by breaking a bitstring into fixed-length chunks (of B bits) and replacing them with a (P, O) pair, where P is the block’s popcount which can be used to point to the table where each entry has the popcount P, and O is the offset in that subtable. Then P can be stored with log2(B + 1) bits – we need to represent all possible P values from 0 to B – and O can be stored with log2(binomial(B, P)) bits.

Note that the bit-length of P varies; binomial represents the binomial coefficient, which can be seen in Pascal’s triangle expanded to row 5:

So binomial(5, x) for x = 0, 1, … , 5 yields the sequence 1, 5, 10, 10, 5, 1 – some things take more bits than others. Once you know the P value, you will know how many bits the O value is, so you can read it that way. This means access is O(N) (since each values position relies on the previous P values), but you can build an index on top of that to allow O(1) lookup. But all this is a story for another time ;) [1].

Here is the code:

def next_perm(v):
    """
    Generates next permutation with a given amount of set bits,
    given the previous lexicographical value.
    Taken from http://graphics.stanford.edu/~seander/bithacks.html
    """
    t = (v | ( v - 1)) + 1
    w = t | ((((t & -t) / (v&-v)) >> 1) - 1)
    return w

This will take a number with a certain popcount, and generate the next number with the same popcount. For example, if you feed it 7, which is 111 in binary, you will get 1011 back – or 11 – the next number with the same popcount (lexicographically speaking).

To find the first number of a given popcount, you can use this:

def element_0(c):
    """Generates first permutation with a given amount
       of set bits, which is used to generate the rest."""
    return (1 << c) - 1

I should clear up what lexicographically means in the context of numbers. Well, it’s actually the same as any other symbols (such as an alphabet), 0 is the symbol that comes before 1 (if it helps, you can picture 0 as a and 1 as b):

00111 aabbb
01011 ababb
01101 abbab
01110 abbba
10011 baabb
10101 babab
10110 babba
11001 bbaab
11010 bbaba
11100 bbbaa

Psuedocode

Looking at the above pattern, here is some loose pseudocode that may help us understand how the above bithacks work:

Set i to the position of the rightmost bit
Stop if there are no set bits, or if we have looked at all the bits (i >= length of bitstring)
If the i+1th bit (one place to the left) is 0: move the ith bit left
Otherwise, if the i+1th bit (one place to the left) is 1: set i to i + 1 and repeat from 2.
Shift the bits on the range [0, i] right so that the rightmost bit is in position 0

Explanation

Understanding element_0() is pretty easy. 1 << c is the same as moving a 1 to position c, then -1 sets all the bits from 0 to c – 1, giving c set bits:

c = 4
1 << c = 10000
10000 - 1 = 01111

next_perm() is a bit more complicated. The v | (v -1) in t = (v | (v - 1)) + 1 right-propagates the rightmost bit. Allow me to show an example: 01110 | 01101 = 01111

In the case of 0, this isn’t quite correct: 00000 | 11111 = 11111 But it’s okay because we proceed to add 1 to this value (which returns it to zero). This increment, combined with the right-propagation, will do step 2, 3, and part of step 5 above. For example, 10100 -> 10111 -> 11000.

We are on our way to generating integers by popcount in lexicographical order.

Now let’s break down the next line, w = t | ((((t & -t) / (v&-v)) >> 1) - 1). Bitwise equations of the form (x & -x) isolate the rightmost bit: 01110 & 10010 (two's complement) = 00010

If you take the two’s complement, you invert a numbers bits and then add 1. If you think about it, this means there are 0s where there were 1s, and 1s where there were 0s, and adding 1 bumps the rightmost 1 left and sets the subsequent right bits to 0. This means that the only position that will remain set in both numbers is the the rightmost 1-bit.

So let R(x) denote the isolated rightmost bit of x, then for x = 01110 we calculate t = 10000, R(x) = 00010 and R(t) = 10000.

Following the calculation of w, we need to divide them: R(t) / R(x) = 10000 / 00010 = 01000

Shift to the right by 1: 00100

Subtract 1: 00011

Then we bitwise-or them to stick them together: 10000 | 00011 = 10011. This corresponds to our table above :)

So w = t | ((((t & -t) / (v&-v)) >> 1) - 1) corresponds to the rest of step 5 (the moving part, t was the zeroing part of moving the sub-range) in our pseudocode. Well, kind of anyway, there are a few steps happening in parallel, but the pseudocode was only loosely explaining what was happening :)

Testing it out

def gen_blocks(p, b):
    """
    Generates all blocks of a given popcount and blocksize
    """
    v = initial = element_0(p)
    block_mask = element_0(b)

    while (v >= initial):
        yield v
        v = next_perm(v) & block_mask



>>> for x in gen_blocks(3, 5): print bin(x, 5)
... 
00111
01011
01101
01110
10011
10101
10110
11001
11010
11100

Note: bin is just a function I found online for printing binay numbers and isn’t important to this post, but you can find it here if you need one.

Then of course you can loop through all values of P from 0 to B to build the complete table.

Questions? Comments? Flames? I wanna hear em :)

[1] – Check out Tables by Munro, 1996, and Succinct indexable dictionaries with applications to encoding k-ary trees and multisets by Raman et al, 2002 for a first step into this stuff. Also check out my honours thesis, 2010 for a recent look at succinct data structures. I will write a blog post about this stuff sooner or later :P

Permalink | Leave a comment »

Some Lazy Fun

Sat, 23 Apr 2011 12:17:00 -0700

Image taken from http://ian.umces.edu/

Update: fellow algorithms researcher Francisco Claude just posted a great article about using lazy evaluation to solve Tic Tac Toe games in Common Lisp. Niki (my brother) also wrote a post using generators with asynchronous prefetching to hide IO latency. Worth a read I say!

I’ve recently been obsessing over this programming idea called streams (also known as infinite lists or generators), which I learned about from the Structure and Interpretation of Computer Programs book. It is kind of like an iterator that creates its own data as you go along, and it can lead to performance increases and wonderfully readable code when you utilise them with higher order functions such as map and reduce (which many things can be rewritten in). It also allows you to express infinitely large data structures.

When regular lists are processed with higher order functions, you need to compute the entire list at each stage; if you have 100 elements, and you map a function to them, then filter them, then partially reduce them, you may be doing up to 300 operations, but what if you only want to take the first 5 elements of the result? That would be a waste, hence streams are sometimes a better choice.

Although SICP details how to do it in Scheme, in this blog post I will show some languages that have it built in - Haskell and Python - and how to implement streams yourself if you ever find yourself in a language without it1.

Haskell

Haskell is a lazy language. It didn’t earn this reputation from not doing the dishes when you ask it to (although that is another reason it is lazy). What it means in the context of formal languages is that evaluation is postponed until absolutely necessary (Here is a cute (illustrated) blog post describing this lazy evaluation stuff). Take this code for example:

Prelude> let x = [1..10]

At this stage you might be tempted to say that x is the list of numbers from 1 to 10. Actually it only represents a promise that when you need that list, x is your guy. The above code that creates a list from 1 to 10 still hasn’t been executed until I finally ask it to be (by referring to x):

Prelude> x
[1,2,3,4,5,6,7,8,9,10]

It is kind of like telling your mum you’ll do the dishes, but waiting until she shouts your name out again before you put down your DS. Actually, it is sliiiiightly different - if I instead wrote:

Prelude> let x = [1..10]
Prelude> let y = x ++ [11..20]

I have referred to x again when I declared y, but x still hasn’t evaluated. Only after I shout y’s name will y shout x’s name and give me back my whole list:

Prelude> y
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]

Here you ask your robot to wash half the dishes, but he is too busy playing DS too (stupid robot). Finally when your mum shouts, you shout at the robot, and he does his set of dishes, and you do yours. But what is the benefit here? It isn’t that I can get more DS time in…

Take for example a list of positive integers from 1. Yes, all of them. In other languages it might be hard to express this, but in Haskell it is as simple as [1..]. This means we have a list of infinite integers, but we will only calculate as far as we need:

Prelude> let z = [1..]
Prelude> head z
1
Prelude> take 5 z
[1,2,3,4,5]

The syntax here is amazingly terse, and it may make your code more efficient. But even if we don’t have the syntax for it in another language, we can provide it ourselves very easily.

Python

Python has a similar concept called generators, which are made using the yield keyword in place of return, more than one time (or in a loop) in a function:

def integers_from(N):
     while(1):
         yield N
         N += 1

>>> z = integers_from(1)
>>> z.next()
1
>>> z.next()
2

Note: Python generators are stateful and are hence slightly different to an infinite list in Haskell. For example z.next() returns different values in two places, and thus is time sensitive - we cannot get z to ‘rewind’ like we could in Haskell, where z is stateless. Statelessness can lead to easier to understand code, among other benefits.

Rolling Our Own

Let’s reinvent this wheel in Python (but in a stateless manner), so if we ever find ourselves craving infinite lists we can easily roll our own in pretty much any language with Lambdas.

I have chosen Python to implement this, even though it already supports infinite lists through generators, simply because its syntax is more accessible. Indeed, the below can already be done with Python’s built-in-functions (although with state). It is probably not a great idea to do it this way in Python, as it doesn’t have tail call optimisation (unless you use this hack using decorators and exceptions).

First we’ll look at adding lazy evaluation, however the syntax requires it to be explicit:

>>> x = lambda: 5
>>> y = lambda: 2 + x()

Here, x is not 5, and y is not 7, they are both functions that will evaluate to that when we finally run them; the expression inside the lambda won’t be evaluated until we do so explicitly:

>>> x()
5
>>> y()
7

And that’s pretty much all the heavy lifting. To make an infinite list, we basically make a linked list where we generate each node as we need it:

def integers_from(N): return (N, lambda: integers_from(N+1))

def head((H, _)): return H

def tail((_, T)): return T()

And there is our infinite list. To access it use head() and tail() (recursively if necessary):

>>> z = integers_from(1)
>>> head(z)
1
>>> head(tail(z))
2

Helper Functions

First we should make a way for us to look at our streams:

def to_array(stream):
    return reduce(lambda a, x: a + [x], [], stream)

Which is a reduce operation that puts each head element into an array (which is carried along as a parameter to reduce()). Here is reduce() (map() can be found in this gist):

null_stream = (None, None)
def reduce(f, result, stream):
    if stream is null_stream: return result
    return reduce(f, f(result, head(stream)), tail(stream))

We needed some way to tell if we had reached the end of a stream - not all streams are infinitely long. Meet our next function, which will help us terminate a stream:

def take(N, stream):
    if N <= 0 or stream is null_stream: return null_stream
    return (head(stream), lambda: take(N-1, tail(stream)))

This will take the first N elements from the specified stream. So now we can inspect the first N elements:

>>> to_array(take(10, integers_from(1)))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

For our upcoming example, we also need a filter() method, which will filter out elements that meet a provided predicate:

def filter(pred, stream):
    if pred(head(stream)):
        return (head(stream), lambda: filter(pred, tail(stream)))
    return filter(pred, tail(stream))

Now onto our example :)

Textbook Example

Here is the standard example to demonstrate the terseness of streams:

def sieve(stream):
    h = head(stream)
    return (h, lambda: sieve(
        filter(lambda x: x%h != 0, tail(stream))))

Here is a function which recursively filters anything which is divisible by any number we have previously seen in our stream. Math aficionados will notice that this is the Sieve of Eratosthenes algorithm.

>>> primes = sieve(integers_from(2))
>>> to_array(take(10, primes))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Recursively defined data, and only as much of it as we want - pretty neat.

And Now For Something Almost Completely Different

When I first saw this, I wondered what application there might be to have a stream of functions. Here I have defined a stream which recursively applies a function to itself:

def rec_stream(f):
    return (f, lambda: rec_stream(lambda x: f(f(x))))

When might this be useful? It might yield speed improvements if you commonly want to recursively apply a function a certain amount of times, but have costly branching (so the condition check at each level is slow). It could also be used as a abstraction for recursive iteration 2, which gives you back the function 'already recursed' so to speak (although lazily).

One such recursive process I can think of is Newton’s method for approximating roots, defined recursively as:

When f(x) = 0.

The more iterations you do the more accurate the solution becomes. One use of Newton’s method is to use it until you have reached a certain error tolerance. Another way, which I learned about recently when reading about the fast inverse square root algorithm, which uses just one step of Newton’s method as a cheap way to improve it’s (already pretty good) initial guess. There is a really great article here which explains it very well.

After reading that, I wondered about a stream that would consist of functions of increasing accuracy of Newton’s method.

def newton(f, fdash):
    return lambda x: x - f(x)/float(fdash(x))

The newton() function accepts f(x) and f'(x), and returns a function that accepts a first guess.

def newton_solver(iters, f, fdash):
    def solve(v):
        n = newton(lambda x: f(x) - v, fdash)
        stream = rec_stream(n)
        return to_array(take(iters, stream))[-1]
    return solve

This one is a little more complicated. In order to have it solve for a value other than zero, I needed to either define it in f(x), since f(x) must equal zero, but I didn’t want the user to have to iterate over the stream each time they wanted to compute the square root of a different number, say. To allow it to return a function that solved for square roots in the general case, I had to make the internal function solve(), which would bind for the value the caller specifies, hence solving f(x) = v for x. Hopefully this becomes clearer with an example:

>>> sqrt = newton_solver(1, lambda x: x**2, lambda x: 2*x) # 1 iter
>>> sqrt(64)(4) # Sqrt of 64 with initial guess of 4
10.0
>>> sqrt = newton_solver(3, lambda x: x**2, lambda x: 2*x) # 3 iters
>>> sqrt(64)(4)
8.000000371689179

Now we can pass around this square root function and it will always do 3 iterations of Newton's method.

This may not be practical unless compilers can optimise the resulting function (or if there is a way to do the reduction myself easily), but it was fun to do :) As always comments and suggestions are appreciated. If anyone who reads this is good with compilers, advice would be great :D

What you can do now is read SICP for more cool things like streams and functional programming, or check out Sean Anderson’s bit hacks page for more cool hacks like the fast inverse square root. Or refactor your code to use map, reduce and streams :)

The reason I have chosen Python for this exercise is for reasons of accessibility. Here is a post about implementing streams in Ruby, and here is one for Erlang :) but of course it’s all pretty much the same deal. ↩
If a compiler could optimise this, simplifying the reapplied function, but keeping the generality, that’d be really cool :) I don’t think many compilers would/could do that for lambdas though. Any information would be great. ↩

Permalink | Leave a comment »

Design Pattern Flash Cards

Sun, 17 Apr 2011 05:03:00 -0700

Last year I studied a subject which required me to memorise design patterns. I tried online flash card web sites, but I was irritated that I didn't own the data I put up (they had no export option). So I wrote a something in Python to generate flash cards for me using LaTeX and the Cheetah templating library. The repository is hosted here, although it could do with a refactor.

If you don't want to generate your own, you can download the pre-generated design pattern intent flash cards here which contains the 23 original design patterns from the Gang Of Four.

To generate your own flash cards, create an input text file with this structure:

Front text (such as pattern name):
Definition line 1.
Definition line 2.

For example:

Abstract Factory:
Provides an interface for creating families of related or
dependent objects without specifying their concrete classes.

Currently the front text is single-line only. The regex could be updated of course (if you do, feel free to send a pull request!).

To compile this:

./cardgen.py -i inputfile -o outputfile
pdflatex outputfile

Then just print it out on a double side printer (or glue the two sheets together). I carried these around with me all the time during the lead-up to the exam, and I was scay-fast when it came to recalling which design pattern did what. Just flick through them (shuffle first) in forward or reverse order when you are on the train next :)

Permalink | Leave a comment »

Metaprogramming Erlang the Easy Way

Mon, 04 Apr 2011 00:49:00 -0700

I’ve recently taken Erlang back up1, and I wanted to use this blog post to talk about something cool I learned over the weekend.

I am implementing a data structure. Reimplementing actually, as it is the structure from my thesis - a succinct text index (I will post a blog on this soon).

Why am I reimplementing it in Erlang? The structure involves many bit-level operations, and I wanted to try out Erlang’s primitive Binary type, which seems to be allow efficient splitting and concatenation (which I require). Erlang’s approach to concurrency will hopefully assist me to experiment with distributing the structure, too. As a bonus, the functional approach has lent itself well to this math-centric data structure, and my code is much, MUCH cleaner because of it (I love reduce and other higher order functions).

One function I needed to implement was popcount (the sum of set set bits in a bitvector). For example, if b = 1010 then pop(b) is 2.

There are many methods listed on this blog. One of them is the table method, which precomputes all popcounts for 16 bit integers (or any length you have space for):

POPCOUNT_TABLE16 = [0] * 2**16
for index in xrange(len(POPCOUNT_TABLE16)):
    POPCOUNT_TABLE16[index] = (index & 1)
    + POPCOUNT_TABLE16[index >> 1]

I translated this to Erlang:

-module(popcount_table).
-export([gen_table/1]).

gen_table(Bits) -> gen_table(1, 2 bsl (Bits - 1), {0}).
gen_table(Stop, Stop, Table) -> Table;
gen_table(Value, Stop, Table) ->
    New = (Value band 1) + erlang:element((Value bsr 1) + 1, Table),
    NewTable = erlang:append_element(Table, New),
    gen_table(Value + 1, Stop, NewTable).

So now gen_table(Bits) will generate a tuple for me with all popcounts from 0 to $2^Bits$. However, we may gain performance2 from knowing how big we want the table to be at compile time. If we know the amount of bits we want our popcount table to work for, we could type the table directly into the source. But that would impede our flexibility, and make our code ugly.

Enter ct_expand. We can use ct_expand:term( <code to execute> ) to run gen_table() for us at compile time! Now we only run gen_table() whenever we compile the module - after that the table is embedded in the binary.

First, check out ct_expand (git clone https://github.com/esl/parse_trans.git), and compile it with make3. Then just move the .beam files into your project directory. Now we’re ready for some metaprogramming :)

I created a new module for generating our table at compile time:

-module(popcount).
-compile({parse_transform, ct_expand}).
-compile({popcount_table}).
-export([popcount16/1, popcount32/1]).

-define(TABLE(B), ct_expand:term( popcount_table:gen_table(B) )).
-define(TABLE16, ct_expand:term( ?TABLE(16) )).

popcount16(V) -> erlang:element(V+1, ?TABLE16).
popcount32(V) -> popcount16( V band 16#ffff )
    + popcount16( (V bsr 16) band 16#ffff).

The reason we must be in a new module is because ct_expand:term() requires it’s parameter to be something it will know about at compile time. This could be an inline fun (which I tried, but it wasn’t pretty), or it can be something you compile before ct_expand:term() is executed (see line 3). Note on line 2 that we also need to compile parse_transform and ct_expand with our module.

Let’s test it out:

1> c(popcount).
{ok,popcount}
2> popcount:popcount16(2#1010).
2
3> popcount:popcount16(2#101011).
4

Nice! Thanks to Ulf Wiger for making that so easy :)

( Image stolen from http://improvisazn.wordpress.com/2010/02/22/meta/ )

My only other encounter with it was when I wrote an essay on the rationale of Erlang, which is something I will convert to blog format and post later if anyone is interested. ↩
The compiler may be able to apply further optimisations, so table access might be faster itself, but the main benefit comes from not having to generate the table while your code is running. Note that I haven’t experimented with it. I will try to run some tests this week and update the blog post. ↩
If rebar gives you an error about crypto being undefined, you will need the erlang-crypto package. On Mac OS X: sudo port install erlang +ssl. (I had this issue) ↩

Permalink | Leave a comment »

Au Naturale

Sat, 19 Mar 2011 21:44:00 -0700

This blog post is an introduction on how to make a key phrase extractor in Python, using the Natural Language Toolkit (NLTK).

But how will a search engine know what it is about? How will this document be indexed correctly? A human can read it and tell that it is about programming, but no search engine company has the money to pay thousands of people to classify the entire Internet for them. Instead they must reasonably predict what a human may decide to be the key points of a document. And they must automate this.

Remember how proper sentences need to be structured with a subject and a predicate? A subject could be a noun, or a adjective followed by a noun, or a pronoun… A predicate may be or include a verb… We can take a similar approach by defining our key phrases in terms of what types of words (or parts-of-speech) they are, and the pattern in which they occur.

But how do we know what words are nouns or verbs in an automated fashion?

Throughout this post I will use an excerpt from Zen and the Art of Motorcycle Maintenance as an example:

The Buddha, the Godhead, resides quite as comfortably in the circuits of a digital computer or the gears of a cycle transmission as he does at the top of a mountain or in the petals of a flower. To think otherwise is to demean the Buddha…which is to demean oneself.

Before proceeding, make a (mental) note of the key phrases here. What is the document about?

Tokenizing

In a program, text is represented as a string of characters. How can we go about moving one level of abstraction up, to the level of words, or tokens? To tokenize a sentence you may be tempted to use Python’s .split() method, but this means you will need to code additional rules to remove hyphens, newlines and punctuation when appropriate.

Thankfully the Natural Language Toolkit (NLTK) for Python provides a regular expression tokenizer. There is an example of it (including how it fares against Pythons regular expression tokenization method) in Chapter 3 of the NLTK book. It also allows you to have comments:

#Word Tokenization Regex adapted from NLTK book
sentence_re = r'''(?x)      # set flag to allow comments in regexps
# abbreviations, e.g. U.S.A. (with optional last period)
([A-Z])(\.[A-Z])+\.?
# words with optional internal hyphens
| \w+(-\w+)*
# currency and percentages, e.g. $12.40, 82%
| \$?\d+(\.\d+)?%?
# ellipsis
| \.\.\.
# these are separate tokens
| [][.,;"'?():-_`]
'''

Once we have constructed our regex for defining what sort of format our words should be in, we call it like so:

import nltk
#doc is a string containing our document
toks = nltk.regexp_tokenize(doc, sentence_re)

>>> toks
['The', 'Buddha', ',', 'the', 'Godhead', ',', 'resides', ...

Tagging

The next step is tagging. This uses statistical data to apply a Part-of-speech tag to each token, e.g. ADJ, NN (Noun), and so on. Since it is statistical, we need to either train our model or use a pre-trained model. NLTK comes with a pretty good one for general use, but if you are looking at a certain kind of document you may want to train your own tagger, since it may greatly affect the accuracy (think about very vocabulary-dense fields such as biology).

Note that to train your own tagger you will need a pre-tagged corpus (NLTK comes with some) or use a bootstrapped method (which can take a long time). Check out Streamhacker and Chapter 5 of the NLTK book for a good discussion on training your own (and how to test it empirically).

For the sake of this introduction, we will use the default one. The result is a list of token-tag pairs:

>>> postoks = nltk.tag.pos_tag(toks)
>>> postoks
[('The', 'DT'), ('Buddha', 'NNP'), (',', ','), ('the', 'DT'), ...

Chunking

Now we can use the part-of-speech tags to lift out noun phrases (NP) based on patterns of tags.

Note: All diagrams have been stolen from the NLTK book (which is available under the Creative Commons Attribution Noncommercial No Derivative Works 3.0 US License).

This is called chunking. We can define the form of our chunks using a regular expression, and build a chunker from that:

# This grammar is described in the paper by S. N. Kim,
# T. Baldwin, and M.-Y. Kan.
# Evaluating n-gram based evaluation metrics for automatic
# keyphrase extraction.
# Technical report, University of Melbourne, Melbourne 2010.
grammar = r"""
    NBAR:
        # Nouns and Adjectives, terminated with Nouns
        {<NN.*|JJ>*<NN.*>}

    NP:
        {<NBAR>}
        # Above, connected with in/of/etc...
        {<NBAR><IN><NBAR>}
"""

chunker = nltk.RegexpParser(grammar)
tree = chunker.parse(postoks)

It is also possible to describe a Context Free Grammar (CFG) to do this, and help deal with ambiguity – information can be found in Chapter 8 of the NLTK book. Chunk regexes can be much more complicated if needed, and support chinking, which allows you to specify patterns in terms what you don’t want – see Chapter 7 of the NLTK book.

The output of chunking is a tree, where the noun phrase nodes are located just one level before the leaves, which are the words that constitute the noun phrase:

To access the leaves, we can use this code:

def leaves(tree):
    """Finds NP (nounphrase) leaf nodes of a chunk tree."""
    for subtree in tree.subtrees(filter = lambda t: t.node=='NP'):
        yield subtree.leaves()

Walking the tree and Normalisation

We can now walk the tree to get the terms, applying normalisation if we want to:

def get_terms(tree):
    for leaf in leaves(tree):
        term = [ normalise(word) for word, tag in leaf
            if acceptable_word(word) ]
        yield term

Normalisation may consist of lower-casing words, removing stop-words which appear in many documents (i.e. if, the, a…), stemming (i.e. cars –> car), and lemmatizing (i.e. drove, drives, rode –> drive). We normalise so that at later stages we can compare similar key phrases to be the same; 'the man drove the truck' should be comparable to 'The man drives the truck'. This will allow us to better rank our key phrases :)

Functions for normalising and checking for stop-words are described below:

lemmatizer = nltk.WordNetLemmatizer()
stemmer = nltk.stem.porter.PorterStemmer()

def normalise(word):
    """Normalises words to lowercase and stems and lemmatizes it."""
    word = word.lower()
    word = stemmer.stem_word(word)
    word = lemmatizer.lemmatize(word)
    return word

def acceptable_word(word):
    """Checks conditions for acceptable word: length, stopword."""
    from nltk.corpus import stopwords
    stopwords = stopwords.words('english')

    accepted = bool(2 <= len(word) <= 40
        and word.lower() not in stopwords)
    return accepted

And the result is:

>>> terms = get_terms(tree)
>>> for term in terms:
...    for word in term:
...        print word,
...    print
buddha
godhead
circuit
digit comput
gear
cycl transmiss
mountain
petal
flower
buddha
demean oneself

Are these similar to the key phrases you chose? There are lots of areas above that can be tweaked. Let me know what you come up with :) (the code can be found in this gist).

In future posts I will talk about how to rank key phrases. I will also discuss how to scale this to process many documents at once using MapReduce.

In the mean time check out the demos on Streamhacker, solve the problems in the NLTK book, or read the NLTK Cookbook :)

Permalink | Leave a comment »

Avian Autopilot

Sat, 05 Mar 2011 05:44:00 -0800

In this post I will detail how to remove yourself from your social life. Well, just the link sharing part on Twitter.

At an event held last September, Twitter released some usage stats, including this: around 25% of Tweets contain links.

One must wonder if Twitter spammers have skewed this data. How would my own account compare against this? Using SnapBird to search my tweets for http, I have calculated that about 34% of my activity on Twitter is link sharing...

I don't think my tweets are that spammy, but please correct me if I'm wrong. Most of the enjoyment I get from Twitter is from useful and interesting link exchange, and having questions answered by people who write popular programming books and blogs.

On to the focus of this blog post, which will either reduce the friction of doing what may be a significant chunk of your Twitter workflow, or may just serve to drive these stats up...

Once upon a time in an attempt at clever laziness, I set my Delicious bookmarks to post a weekly blog aggregating the new links I added. People don't go to a blog to see a list of links plastered there by a cron job.

But what if you could take this idea and deliver the links in limited chunks (i.e. one link at a time, with a maximum of three per thirty minutes) on a platform where linking is accepted? If it is any indicator, none of my followers complained. Just make sure you keep the human touch by manually Tweeting thoughts, engaging people with questions, and the occasional Retweet.

The idea is simple: gather your Instapaper and Google Reader starred items into a RSS feed, and set it to post new items to your Twitter (or Facebook).

Instapaper

Right click the RSS link and copy the address into a text file (for later use).

Reader

Now go to your Google Reader account and open the Google Reader settings,

Open the Folders and Tags tab, and select Your Starred Items,

Change the sharing settings to Public,

Click View Public Page and right click the Atom feed link and copy the address into your text file.

Pipes

With Yahoo Pipes we create a master feed. Sign up there and create a new pipe. Add a Fetch Feed module to it,

Fill in the feed addresses that you copied down before, and connect the Fetch Feed module to the Pipe Output,

Save it and right click Get as RSS, copy the address down too :) (Note: Not the Pipe Web Address)

TwitterFeed

TwitterFeed is used to take your master feed and update Twitter, or Facebook, or Ping.fm which can subsequently update many more services. Sign up and create a new feed with the master feed URL you copied from Pipes,

Follow the next steps to connect it to your desired service (and Tweak how many posts per 30 minutes or whatever...).

There you go. Time to test it out:

You may also want to add your Last.fm loved tracks, Flickr photostream or WeHeartIt account. Unfortunately Pinboard (a great alternative to Delicious), while providing RSS feeds for certain tags, and supporting "starring", does not allow you to get an RSS feed of the starred items. I get around this by using a tag called highlight. I have requested this feature, I hope it gets added :)

Pipes actually allows a lot more than simple combination. Have a play and let us know in the comments what you come up with.

Permalink | Leave a comment »

Stop Force-Feeding Your Brain

Mon, 21 Feb 2011 03:58:00 -0800

I used to read less than one book per year. According to Code Complete, this is the same as the average programmer.

That was while I was at uni though. I sort of expected to learn slowly at uni, and anticipated rapid, mind-blowing learning when I entered the industry. My first job had me working under some of the smartest people I have ever met - it was at a game company. Unfortunately they ran out of money and I had to find a job at a slower-paced place, where I didn't have the luxury of mentorship.

My mind was going stale, I had to do something. I looked up recommended reading lists online and the first programming book I picked up (that wasn't for a uni course) was The Pragmatic Programmer. Are you sick of me mentioning this book in every post yet? ;)

PragProg recommends that you treat your learning as investment, and your knowledge as a portfolio; you should invest regularly, diversify, balance it between high-risk and conservative, buy low and sell high (i.e. take interest in emerging technologies). It recommends several goals, such as reading a technical book each quarter, and when you've developed the habit, one per month. It also recommends reading non-technical books too. I totally fell in love with this idea, and have been reading like a mofo since.

There is a slight problem though...

The final point PragProg gives is to review and rebalance. The point it makes is that you need to stop learning things that aren't providing value, and revise things you have forgotten occasionally. I want to focus on the STOP part of this. For the love of God, take it easy! It takes years to learn all this stuff - you don't have to do it all at once.

I am guilty of bingeing on blogs and books. I picture learning like a tree-traversal, with each (sub)topic having a different branch. The problem is, I keep getting excited about new books or programming languages I find, and never reach the leaves. I really need to learn focus, because I'm swinging from branch to branch like a monkey.

During my reading, I have realised that other smart people are with me on this. In The 4-Hour Workweek, Tim Ferris mentions that you should only ever read one factual book concurrently, along with one fictional book. You aren't productive if you are reading more than one factual book - context switches are expensive.

The current non-tech book that I'm reading is Zen and the Art of Motorcycle Maintenance - this may be a bit of a cheat, because it is recommended on some programmer reading lists. The narrator talks about his coming to enjoy the journey more than the actual arrival. The process of learning is itself something to be enjoyed, and isn't just yak shaving.

Rob Walling says in his startup book Start Small, Stay Small that entrepreneurs should stop reading so much. He says "Information Consumption is Only Good When it Produces Something", although it can be done for pure enjoyment too - as long as you pay attention to when you NEED TO DO IT and when you just want to (which is more often than you think).

How do we know what input will produce good output? We can use heuristics when choosing (which is what we all do anyway) - such as author name - but you can't know for sure unless you've read it. Swinging from branch to branch is a necessary evil, then. We need to work out a balance between input and output, or that which Monkey sees and that which Monkey Does.

Here are some of my own tips for curing this information-eating-disorder:

Allow yourself to quit. Sometimes projects just aren't worth your effort.
Only read two books - one technical, one non-technical - at a time. As above, you can quit a book at any time, but avoid constant interleaved reading.
Install RescueTime. It passively monitors and graphs your activity breakdown. This will awaken you to how much useless crap you do in a day.

What gets measured gets managed - Peter Drucker

Instapaper. Use it (on your computer and phone), love it. If you aren't reading this blog post during down-time (e.g. during a train commute) then I'm looking at you in particular. I won't read a blog post unless it goes through my instapaper account first.
Periodically cull your RSS feeds. Eddie Smith of Practically Efficient suggests eliminating feeds that produce more than ten posts per day. I recommend scheduling reminders to cull your feeds on a regular basis. Hacker News should come to mind - give one of these popularity-sensitive feeds a try instead, to make use of human filtering.
Write todo lists. You probably do this anyway, except this time I want you to write two of them side by side... let's call this the "twodolist" method. The first is for things that you absolutely have to finish - maybe you are obligated to do it for work, maybe it counts toward your primary objective, like writing a thesis or starting a startup. The second list is
for the things you want to do that seems important enough to put on a list. This may include reading a certain book.

The act of applying this mental scalpel really helps me. When I am "busy", it is often the case that I am working off the second list, which means I'm avoiding the first.
Turn off push notifications for your phone. This is just another unnecessary context switch - you don't really need to know the exact moment you get an email.

Now it's your turn! Please leave any advice (big or small) in the comments.

Permalink | Leave a comment »

Advice to CS Undergrads

Mon, 07 Feb 2011 02:35:00 -0800

Since I’m starting my PhD this year, I have been reflecting on how I would be different if I went back in time and started my degree all over again. I am also continuing tutoring, in my 4th year, and I have been occasionally approached by students and asked for general advice with their studies.

I repeat the same advice to most students, so I’ll attempt to distill it into the points below. Bear in mind that I am writing from a Computer Science perspective, although some of the advice can be applied to any field.

I didn’t do most of this stuff during my undergrad years. I still did well, but I think I would have had more fun if I followed this advice. If you’re not doing all the stuff on this list, that’s okay. Come back and try again later.

Here’s the advice in no particular order:

Decide to get Good. I know a lot of students who aren’t sure if they are in the right degree. Computer Science isn’t for everyone, but if you are far enough in (> 1 year) I recommend riding it out. I even had my own doubts; While programming was a hobby for me prior to uni, most subjects at uni left me disappointed. When I started searching for parts of it that interested me, I found it much more creative and fun.

After your degree, you can do Masters in something else, and it will only take 1.5 or 2 years. Or you can study other things in your spare time. Don’t bite off too much though…

Supposedly it takes 10,000 hours to become an expert at anything, but after that I bet it is faster to become an expert at other things; many of the 10,000 hours you spend will be self-learning that can be applied to the next.

Learn More Languages. Everyone gives this advice, but they usually suggest it because it will give you a perspective on different ways to do things. I think you should learn Python (or Ruby) in order to remove the friction from learning (try the book Learn Python The Hard Way by Zed Shaw).

Python has been dubbed “executable pseudocode”, so this will help you when reading algorithm books. They are both dynamically typed, which means you don’t have to tell the computer when you are talking about a number vs a string. They also come with an interactive shell where you can test ideas and easily enter/modify examples from books.

Since their syntaxes are C-like, you can start your assignments in one of these languages, and easily translate it by hand to Java or C. Build one to throw away (thanks, Fred Brooks) so you can learn about the pitfalls of the problem before you have to deal with pointers or boiler-plate code.

Lisp is also recommended. It can be daunting to choose a dialect when you know nothing about it… Just learn Scheme (you can learn Common Lisp or Clojure later). There is really amazing free material that you’ll probably want to read or watch at some point anyway. It will be less practical for your uni years, but will give you a depth of knowledge that will carry you through your entire career.

Oh yeah, and learn and use regular expressions the next time you need to process text.

Manage Your Time. Okay, this is a no-brainer, but I still didn’t do it that well. The day you get an assignment, put it on your calendar and set a reminder. After you’ve done that, start working on it right away.

Remember, you aren’t committed to whatever you write down, until you hand it in; once again, build one to throw away. Even a mind-map or just writing headings can help a lot. Inevitably you’ll rush it at the last minute, but having previous work to reference rather than a blank page is so much more comforting. I’ll write more productivity advice in a later post, so keep checking back.

Read! I don’t mean the prescribed text-book - I only read a few of those, and sometimes they are only recommended because the lecturer is somehow invested in it (don’t get me wrong, some are great, but you’ll find out about those books anyway).

I recommend starting with The Pragmatic Programmer; It’s nice and small, very practical, acclaimed, and it will point you in the direction of other good books to read when you’ve finished.

Other than that, check out some recommended reading lists 1, and subscribe to blogs 2. I’ll also discuss my reading workflow at a later date, as you have to be careful of information-glut.

Sharpen Your Tools. Here are some tools that will help you make learning an enjoyable process:

Get a laptop. I feel bad saying that coz it will cost you money, but it really helps to have your coding environment ready to go.
Use Unix. I only did this after I switched to Mac OS X, but there are free alternatives. It’s just a nicer environment for coding. It will also reduce the amount of time you spend on games.
Use Git and GitHub. Often, I would try to fix a bug in an assignment only to introduce more. Sometimes I would make backups of the project folder, but this was usually confusing and has led to me losing major chunks of work. Every project you do should be on GitHub to help you manage this, enable you to have pride in your work (by displaying it publicly), and having an off-site backup.
Start learning Vim during a break. It has a steep learning curve, but will make you faster in the end.

Start Your Career Early. Another thing I didn’t do. Here are some things you can do to help you hit the ground running when you finish uni:

Contribute to open source. It looks good on your resume, and (as japerk commented) will help you learn about real world programming and software in the wild. You can find beginner-level bugs on openhatch.
Maintain a resume and apply for jobs (even if they are out of your league). Worst-case, you don’t get it, but it will may help you spot holes in your knowledge and experience (failing a Google interview was a big reality check for me). Best-case, you get relevant work while at uni.
Tutor people. Studies have shown that we learn best when we are teaching.

Don’t Forget: People Matter! It’s easy for a geek to forget this, but I think it’s the lynchpin to good education.

The friends you make, even if less intelligent, will drive you to do Computer Science for fun. They will either show you the cool stuff they learn, or challenge you to do better than them. But it doesn’t stop with your classmates.

Write a blog. This will refine your communication skills, but I still get emails from people thanking me for my (simple) nanosecond time wrapper. It’s fun and rewarding. If you are having trouble maintaining it persistently, email me and I’ll tell you about a relevant project of mine that might help…
Tweet about your programming interests. This will build a network outside of uni, that will remind you why you like doing this. Follow me on twitter: @alexbowe :)
Email your idols. It can be really helpful and exciting to get a response from someone whose blog you read, or who has written a book or paper you read. This really helped me with my thesis last year. It might also give you something to blog about ;)

To me, these are the most important pieces of advice to take while studying (or as soon as you are ready). Criticism, suggestions, and comments of any other type are welcome, as always. It’d also be cool to hear about things you think paint CS in a cool light for students (The game of life is one example).

For more blog posts on similar matters by much better writers and programmers than me, check out:

After The Pragmatic Programmer, try The Passionate Programmer. If you want a good book to help you with your people skills, try How To Win Friends And Influence People. Coding Horror and Stack Overflow have great book recommendations too. And a list of FREE books. ↩
Too many great blogs to list. Start at Hacker News and you’ll soon find some great blogs to follow. Theres also a recommendations thread there already. ↩

Permalink | Leave a comment »

Awesome is Better than Good

Sat, 27 Nov 2010 21:00:00 -0800

I am currently reading Edward De Bono's Thinking Course (Author of Six Thinking Hats), which has an anecdote from one of his seminars; he describes a problem involving two pieces of wood, and the task of crossing a room without touching the ground. He accompanies this with a discussion of three approaches, one very inefficient, and one seemingly good. The third approach is much faster, but everyone settles on the second solution, because it seems good enough...

The 'shuffle' solution seems so obvious and so adequate that there never seems any need to set out to look for an alternative. Contentment with an 'adequate' solution or approach is the biggest block there is to any search for a better alternative... It is only through realisation of this and an act of will that we can set out to look for alternatives - knowing that in most cases we shall not find anything better, but still being willing to invest that thinking time.

I feel that this advice should be taken in reverse too. If you have a new idea for how to do something, don't dismiss it because people are already happy with the current methodology; they could be ecstatic with yours. Maybe a solution you think is too obvious isn't so clear to them.

I think many people sell their good ideas short, and become too attached to ideas that maybe aren't all that great. Regardless of the perceived value of your idea (within reason), you should test the waters. Run it by some non-friends (they don't mind hurting your feelings). It may be better, or worse, than you think.

Permalink | Leave a comment »

Regularly Divisible

Tue, 23 Nov 2010 12:26:00 -0800

Update: read the comments at Hacker News to see some succinct approaches to this, as discussed by gjm11, qntm and patio11. Thanks to Robin for providing this demonstration that can find a regex for testing divisibility of any number, in any base (he also made the code available, nice).

Earlier this year, at the advice (once more) of Chad Fowler, I took to the idea of practicing programming every day. Perhaps this appealed to me because it echoed the rituals of my better musician friends, and allowed me to draw parallels between programming and my fading dream of becoming a famous rockstar.

Possibly because of my failed interview at Google (hey, I wouldn't have hired the back-then me either, so no hard feelings!), I was also interested in job-interview styled problems [1]. Not FizzBuzz though, more like the computer science 'riddles' found on this page [2].

At the time I was teaching Computing Theory [3], 80% of which was formal languages: regular expressions, context free and context sensitive grammars, Turing machines and other automata, and their locations in the Chomsky Hierarchy. So, this problem appealed to me:

Construct a finite state machine (or equivalently, write a regular expression) which accepts all strings over the alphabet {0,1} which are divisible by 3 when interpreted in binary.

It is pretty interesting that languages can be defined to communicate patterns in binary sequences that are divisible by 3. Let's solve it in more detail than necessary :)...

We will be developing this regex incrementally. I will update the regex at each stage. Since it is easier to construct this regex using a finite state machine (which is how I worked this out the first time), I'll also include a few diagrams along the way. You can test your regexes using the Ruby code here.

To get an idea for the pattern, I started by listing out a few multiples of 3 and their binary representations. You can use the following Ruby code if you want.

class Fixnum
  def to_bin_s
    return '0' if self == 0
    s = ''
    n = self

    while n > 0
      s = (n % 2).to_s << s
      n = n >> 1
    end
    s
  end
end

>> 30.times {|n| puts "#{n}: #{n.to_bin_s}" if n%3 == 0}
0: 0
3: 11
6: 110
9: 1001
12: 1100
15: 1111
18: 10010
21: 10101
24: 11000
27: 11011

Observe that the binary representations for 3, 6, 12 and 24 have something in common: they have the same sequence, with a little bit of zero-padding to the right. If X is a binary string divisible by 3, then the binary string X0 is divisible by 3 as well. This makes sense, as adding zeros to the right is equivalent to multiplying by 2, and we know that n * 3 * 2 is divisible by 3 for any integer n. This gives us:

r = A0*

A will represent the leftover regex at each stage.

This can trivially be applied to left zero-padding as well, because a binary string X is numerically equivalent to the binary string 0X (issues of endianness aside):

r = 0*A0*

Since we already covered even multiples, to work out A we just need to look at odd multiples of 3. Here are a few:

>> 50.times {|n| puts "#{n}: #{n.to_bin_s}" if n%3 == 0 and n%2 != 0}
3: 11
9: 1001
15: 1111
21: 10101
27: 11011
33: 100001
39: 100111
45: 101101

You might have noticed that 1111 (15) is just 11 (3) concatenated with itself. That's the same as saying 15 = 3 * 2 * 2 + 3. If you add two multiples of three, you will of course get another multiple of 3 (it's the same for any multiplier), and concatenating just involves doubling the first number a few times pre-addition. Hence, you will always get another multiple of 3 by concatenating two.

r = (0*A0*)+

From observation, here are the above numbers that are not concatenations:

Take note that it always starts and ends with a 1. It should definitely end with a 1 to be odd, and start with a different 1 to be greater than 1. Our updated regex becomes:

r = (0*1A10*)+

It also appears that we can optionally insert an even number of zeros between the end 1s. A proof of this is attached at the end, if you're into that sort of thing.

r = (0*1(0A0)*10*)+

So what about those 1s in the middle then? It appears that we're allowed to have 0, 1 or 2... maybe more consecutive 1s? Maybe we can say our regex is r = (0*1(01*0)*10*)+. I'll test the regex for the first 5000 integers:

False Negatives:
  0

Oops! I forgot about 0 being evenly divisible by 3 exactly 0 times. Our regex should account for this:

r = 0|(0*1(01*0)*10*)+

Running the test again we get this output:

Pass =]

So there you have it, the regex works for the first 5000 integers. I'll leave a proof of this for all multiples of 3 as an exercise to the reader ;)

[1] I'm not sure I want to work for someone else anymore - I'd rather chase my own stupid dreams. Probably not the rockstar one though. I'll write about these later.

[2] Other good sources of practice questions are Programming Pearls, Project Euler, or you could take a paper from ACM Transactions on Algorithms
(for example) and implement the algorithm/data structure. While you're at it, why not learn Erlang (or any other programming language guaranteed to make you more appealing to the opposite sex) and implement it in that?

[3] Recently, a past student of mine told me that they have never found Computing Theory to be of any use. I said "What about regular expressions?" and they shook their head. This was a smart student too, but I find that regular expressions are so damn useful (perhaps a hammer I swing too often). Ironically, Computing Theory was the most practically useful subject in my (watered down) degree. In the near future I intend on climbing on my high-horse and writing a blog post about my ideal CS degree.

Appendix

Here is a proof that shows we can optionally insert an even number of zeros between two 1s to get an odd multiple of 3. This is equivalent to saying that our left-most 1 has to be in an odd position index (if 0 is the rightmost...).

RTP: 2^(2i + 1) + 1 = 3m, for m odd integer and i positive integer or 0

Let i = 0, then
LHS = 2^1 + 1
    = 2 + 1
    = 3 * 1
    = 3m (1 is an odd integer)
    = RHS
    => it holds for i = 0

Let i = k for any integer k, then assume
2^(2k + 1) + 1 = 3m

Let i = k + 1, then
LHS = 2^[2(k + 1) + 1] + 1
    = 2^(2k + 1 + 2) + 1
    = 4 * 2^(2k + 1) + 1
    = 3 * 2^(2k + 1) + 3m'
    = 3[ 2^(2k + 1) + m']
    = 3[ 2^(2k + 1) + 1 + (m' - 1)]
    = 3[3m' + (m' - 1)]
    = 3(4m' - 1)
    = 3m (an even number minus 1 will be odd)
    = RHS
QED

Yes, 2^n + 1 always yields an odd multiple of 3, for n odd. I should really set up a math plugin...

Permalink | Leave a comment »

Hero Typing

Sun, 08 Aug 2010 15:19:00 -0700

"Who is your hero?" is a question I've been asked, but never had an answer for. Why is this a question that people are compelled to ask? Are we expected to have a hero, like a favourite colour or number?

In his book The Passionate Programmer, Chad Fowler quotes jazz musician Pat Metheny when he writes this advice to aspiring developers: "Be the worst guy [or girl] in every band you’re in" (an excerpt is available here). Chad argues that being in proximity of more talented programmers can make you "better via osmosis".

As programmers, we have many opportunities to find a better band (e.g. open source) - however, I think that this advice can be reapplied to nearly any domain, and the benefit gained remotely. In general, if it is against your current nature to be as awesome as X, consider X your hero. This is why we should have heroes; not to be in awe of them, but to hypnotise ourselves to want to quack like a duck.

I'm writing this at the risk of quacking like a motivational speaker. I'm not a fan of people who try to motivate you by saying obvious, non-actionable things like "believe in yourself". How the fuck am I meant to do that? No, I'm talking about heroes who can actually stir some change of behaviour in you, for the better. Teachers, if you will.

One of the reasons I found it hard to answer "Who is your hero?" is because I didn't know what a hero was. Take Superman for example: Superman is not a hero in my sense of the word, because he only saved us from the baddies. He didn't improve the human race, he didn't encourage our evolution. He didn't teach mankind to fish, so we only ate for a day.

In case you want to know who my heroes are, I like the way Paul Graham quacks. If you know me then I have probably mentioned him to you before. The guy has ideas and he knows how to write.

Then there's Galois. His legend says that he stayed up all night writing everything he knew about group theory before dying in a gun duel the next day. He was 20 and the duel was over a girl. I like that someone who contributed so much to mathematics was also crazy enough to die for a girl. It's chivalry, it's destructive and it's rock and roll.

I didn't have to choose these heroes, they are just people who I admire. I think that choosing to admire someone is a strong commitment, one that forces you to consider what you care about (tip #1 in The Pragmatic Programmer). Think about who your hero is; if it doesn't make you more awesome, then at least you'll have an answer when people ask you "Who is your hero?"

So, who is your hero?

Permalink | Leave a comment »

Things Smarter People Said

Sun, 27 Jun 2010 13:40:00 -0700

I am currently reading Code Complete 2 as per Jeff Atwood's Recommended Reading for Developers list, where I came across this interesting quote by Glenford Myers:

We try to solve the problem by rushing through the design process so that enough time is left at the end of the project to uncover the errors that were made because we rushed through the design process"

I think it succinctly illustrates the need for balance in software design; it is just vague enough to communicate exactly what you need to hear.

I'm interested in hearing any other cool quotes, or book recommendations if you've got some =]

Permalink | Leave a comment »

I don't know what the F*** I'm doing

Tue, 25 May 2010 14:08:00 -0700

This is a nice article I read back in February which discusses why it's a good thing when you realize how very little you know. I feel just like that right now, and I'm enjoying it because there is so much territory left to explore...

No One Knows What the F*** They're Doing (or "The 3 Types of Knowledge")

Permalink | Leave a comment »

How to Win Friends and Generate People

Sun, 28 Mar 2010 11:47:00 -0700

I'm doing a project for a subject at RMIT which needs to manage thousands of patient records for a hospital. We haven't been given any sample data though, so I wanted to write a generator (so we can test it with small or large data sets whenever needed).

I started with the name generator (in Python), which selected a random male/female/last name from a file [1]. I then realised an address generator would behave similarly (street, city, country lists), so I decided to make a Generator base class. You can get the source code for these here.

I wanted the Generator base class to create methods dynamically; It would be instantiated with a bunch of methodname-filename pairs and have the methods for randomly selecting an entry from each file made dynamically. Exactly how to do this wasn't easy to find, as it wasn't well documented... the solution ended up being:

def add_method(obj, f, fname):
    """Adds the instance method from function f to the object obj, callable by fname (i.e. obj.fname())
    example:

    def func(self):
        print 'test'

    add_method(myObject, func, 'newmethodname')

    myObject.newmethodname()
    """
    from new import instancemethod
    obj.__dict__[fname] = instancemethod(f, obj, obj.__class__)

Niki (my brother) helped me get 70% of the way there... (after lots of scope and decorator issues) thanks man :)

[1] The name lists were taken from this census data, which actually provides percentages for each name too, if you wanted to make the name distribution more realistic...

Permalink | Leave a comment »

Amorphism

Fri, 12 Mar 2010 10:51:09 -0800

This guy, Alberto Seveso, made this by dropping varnish into a fishbowl. I like how such a simple idea can yield such complex results :)

Permalink | Leave a comment »

Nanosecond Timing

Tue, 23 Feb 2010 01:37:00 -0800

My Uni (RMIT) uses a mixture of Solaris, Mac OS X, Linux, and Windows computer labs. Our programs are nearly always tested on Solaris, though. Sometimes we are required to provide nanosecond timings in our experiments using the (real-time) POSIX function gethrtime().

Depending on which lab I work in, or if I’m working from home, I might need to comment out (or add compile guards) into my code to compile it correctly. This can make the code less readable, and can make its behavior (particularly output) on Solaris less obvious while testing on a foreign system.

Although the granularity, accuracy and any possible side effects (such as function overhead, or being affected by changing the system clock) may be different for each function, I find it helps to at least give a ball-park figure. Experiments should still be done on Solaris. If you want to use or modify my nanosecond function call wrapper, get it on GitHub.

Note: Not thoroughly tested on all target operating systems or compilers. It is only intended as a convenience.

Permalink | Leave a comment »