A timeline view in Django

One thing a lot of people want to do in Django is to have a timeline view, that shows all the objects of a given set of models ordered by a common key. Unfortunately the Django ORM doesn't have a way of representing this type of query. There are a few techniques people use to solve this. One is to have all of the models inherit from a common baseclass that stores all the common information, and has a method to get the actual object. The problem with this is that it could execute either O(N) or O(N*k) queries, where N is the number of items and k is the number of models. It's N if your baseclass has the subtype it is stored on it, in which case you can directly grab it, else it's N*k since you have to try each type. Another approach is to use a generic relation, this will also need O(N) queries since you need to get the related object for each generic one. However, there's a better solution.

What we can do is use get a queryset for each of the models we want to display(O(k) queries), sorted on the correct key, and then use a simple merge to combine all of these querysets into a single list, comparing on a given key. While this technically may do more operations than the other methods, it does fewer database queries, and this is often the most difficult portion of your application to scale.

Let's say we have 3 models, new tickets, changesets, and wikipage edits(what you see in a typical Trac install). We can get our querysets and then merge them like so:

def my_view(request):
   tickets = Ticket.objects.order_by('create_date')
   wikis = WikiEdit.objects.order_by('create_date')
   changesets = Changeset.objects.order_by('create_date')
   objs = merge(tickets, wikis, changesets, field='create_date')
   return render_to_response('my_app/template.html', {'objects': objs})

Now we just need to write our merge function:

def merge_lists(left, right, field=None):
    i, j = 0, 0
    result = []
    while (i < len(left) and j < len(right)):
        if getattr(left[i], field) <= getattr(right[j], field):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def merge(*querysets, **kwargs):
    field = kwargs.pop('field')
    if field is None:
        raise TypeError('you need to provide a key to do comparisons on')
    if len(querysets) == 1:
        return querysets[0]
    
    qs = [list(x) for x in querysets]
    q1, q2 = qs.pop(), qs.pop()
    result = merge_lists(q1, q2, field)
    for q in qs:
        result = merge_lists(result, q)
    return result

There might be a more efficient way to write our merge function, but for now it merges together an arbitrary number of querysets on a given key.

And that's all their is too it. If you see a good way to make the merge function more efficient let me know, I would have liked to use Python's included heapq module, but it doesn't have a way to use a custom comparison function that I saw.

Python Things

I wasn't really sure what to name today's post, but it's basically going to be nifty things you can do in Python, and general tips.

• SystemExit, sys.exit() raises SystemExit, if you actually want to keep going, you can just catch this exception, nothing special about it.
• iter(callable, terminal), basically if you use iter in this way, it will keep calling the callable until the callable returns terminal, than it beaks.
• a < x < b , in Python you can chain comparison operators like this. That's the same as writing a < x and x < b.
  
• dict(), amongst the other ways to instantiate a dictionary in Python, you can give it a list of two tuples, so for example, [('a', 2), ('b', 3')] becomes {'a': 2, 'b': 3}.
• open(filename), is an iterable, each iteration yields another line.
• If you don't need ordering, use set() instead of list(). set() has better runtime for just about every operation, so if you don't need the ordering, use it.
• Python comes with turtle graphics. This probably doesn't matter to most people, but if you want to help get a kid into programming, import turtle can be a great way.
• pdb, the Python debugger is simply invaluable, try: code that isn't working, except ExceptionThatGetsRaised: import pdb; pdb.set_trace() is all it takes to get started with the itneractive debugger.
• webbrowser.open(url), this module is just cool, it opens up the users browser to the desired URL.

And those are my tips! Please share yours.