Wednesday, 29 October 2014

A Fuzzy Sublime-like String Matching Algorithm

Those of you who pay attention to what I'm up to, will know that one of my long running projects is to write my own code editor.

One of the features that's been implemented for a while was a basic filename search via a popup search box. This approach is seen in other editors like Sublime Text, and it's an efficient way to quickly navigate between files.

I wasn't happy with my search matching though, it used a hacky Levenshtein distance algorithm for ordering. It was slow, and to keep it usable I had to disregard many matches that the user might have been looking for.

After much thought I've come up with a much better algorithm for fuzzy matches, I'm going to call it the Kazade Ranking Algorithm, because I can.

Tuesday, 21 October 2014

On Google App Engine, Ancestor Queries are Almost Never What You Need

Recently, the company where I work announced the alpha release of Djangae, a compatibility layer that allows your Django application to work on App Engine, and to store your data in the App Engine Datastore. One of the things missing from the alpha was support for the Datastore's so called "Ancestor queries".

The App Engine Datastore is a remarkable feat of engineering. It's a non-relational database, which can scale to store mind-boggling amounts of data and deal with crazy high amounts of traffic. Of course, the sacrifice is that it's non-relational - so there are no joins, aggregate queries or the like. And if you want to count things then expect it to take some time!