Django-filter is a reusable Django application I have been working on for a few weeks, individuals who follow me on Github may have noticed me working on it. Django-filter is basically an application that creates a generic interface for creating pages like the Django admin changelist page. It has support for defining vairous filters(including custom ones), filtering a queryset based on the user selections, and displaying an HTML form for the filter options. It has a design based around Django's ModelForm.
You can get the code, as well as tests and docs over at Github. For all bug reports, comments, and other feedback you can send me a message on Github(or message me on IRC) until I figure out a proper bug tracking system.
Enjoy.
Saturday, February 14, 2009
Tuesday, February 10, 2009
A Second Look at Inheritance and Polymorphism with Django
Previously I wrote about ways to handle polymorphism with inheritance in Django's ORM in a way that didn't require any changes to your model at all(besides adding in a mixin), today we're going to look at a way to do this that is a little more invasive and involved, but also can provide much better performance. As we saw previously with no other information we could get the correct subclass for a given object in O(k) queries, where k is the number of subclasses. This means for a queryset with n items, we would need to do O(nk) queries, not great performance, for a queryset with 10 items, and 3 subclasses we'd need to do 30 queries, which isn't really acceptable for most websites. The major problem here is that for each object we simply guess as to which subclass a given object is. However, that's a piece of information we could know concretely if we cached it for later usage, so let's start off there, we're going to be building a mixin class just like we did last time:
So now we have a simple abstract model that the base of our inheritance trees can subclass that has a field for caching which subclass we are. Now let's add a method to actually cache it and retrieve the subclass:
Our save method is where all the magic really happens. First, we make sure we're only doing this caching if it's the first time a model is being saved. Then we get the first parent class we have (this means this probably won't play nicely with multiple inheritance, that's unfortunate, but not as common a usecase), then we get all the related objects this class has(this includes the reverse relationship the subclasses have). Then for each of the subclasses, if it is a RelatedObject, and it is a primary key on it's model, and the class it points to is the same as us then we cache the accessor name on the model, break out, and do the normal save procedure.
Our get_object function is pretty simple, if we have our class cached, and the model we are cached as isn't of the same type as ourselves we get the attribute with the subclass and return it, otherwise we are the last descendent and just return ourselves. There is one(possible quite large) caveat here, if our inheritance chain is more than one level deep(that is to say our subclasses have subclasses) then this won't return those objects correctly. The class is actually cached correctly, but since the top level object doesn't have an attribute by the name of the 2nd level subclass it doesn't return anything. I believe this can be worked around, but I haven't found a way yet. One idea would be to actually store the full ancestor chain in the CharField, comma separated, and then just traverse it.
There is one thing we can do to make this even easier, which is to have instances automatically become the correct subclass when they are pulled in from the DB. This does have an overhead, pulling in a queryset with n items guarantees O(n) queries. This can be improved(just as it was for the previous solution) by ticket #7270 which allows select_related to traverse reverse relationships. In any event, we can write a metaclass to handle this for us automatically:
Here we've created a fairly trivial metaclass that subclasses the default one Django uses for it's models. The only method we've written is __call__, on a metalcass what __call__ does is handle the instantiation of an object, so it would call __init__. What we do is do whatever the default __call__ does, so that we get an instances as normal, and then we call the get_object() method we wrote earlier and return it, and that's all.
We've now looked at 2 ways to handle polymorphism, with this way being more efficient in all cases(ignoring the overhead of having the extra charfield). However, it still isn't totally efficient, and it fails in several edge cases. Whether automating the handling of something like this is a good idea is something that needs to be considered on a project by project basis, as the extra queries can be a large overhead, however, they may not be avoidable in which case automating it is probably advantages.
from django.db import models
class InheritanceMixIn(models.Model):
_class = models.CharField(max_length=100)
class Meta:
abstract = True
So now we have a simple abstract model that the base of our inheritance trees can subclass that has a field for caching which subclass we are. Now let's add a method to actually cache it and retrieve the subclass:
from django.db import models
from django.db.models.fields import FieldDoesNotExist
from django.db.models.related import RelatedObject
class InheritanceMixIn(models.Model):
...
def save(self, *args, **kwargs):
if not self.id:
parent = self._meta.parents.keys()[0]
subclasses = parent._meta.get_all_related_objects()
for klass in subclasses:
if isinstance(klass, RelatedObject) and klass.field.primary_key \
and klass.opts == self._meta:
self._class = klass.get_accessor_name()
break
return super(InheritanceMixIn, self).save(*args, **kwargs)
def get_object(self):
try:
if self._class and self._meta.get_field_by_name(self._class)[0].opts != self._meta:
return getattr(self, self._class)
except FieldDoesNotExist:
pass
return self
Our save method is where all the magic really happens. First, we make sure we're only doing this caching if it's the first time a model is being saved. Then we get the first parent class we have (this means this probably won't play nicely with multiple inheritance, that's unfortunate, but not as common a usecase), then we get all the related objects this class has(this includes the reverse relationship the subclasses have). Then for each of the subclasses, if it is a RelatedObject, and it is a primary key on it's model, and the class it points to is the same as us then we cache the accessor name on the model, break out, and do the normal save procedure.
Our get_object function is pretty simple, if we have our class cached, and the model we are cached as isn't of the same type as ourselves we get the attribute with the subclass and return it, otherwise we are the last descendent and just return ourselves. There is one(possible quite large) caveat here, if our inheritance chain is more than one level deep(that is to say our subclasses have subclasses) then this won't return those objects correctly. The class is actually cached correctly, but since the top level object doesn't have an attribute by the name of the 2nd level subclass it doesn't return anything. I believe this can be worked around, but I haven't found a way yet. One idea would be to actually store the full ancestor chain in the CharField, comma separated, and then just traverse it.
There is one thing we can do to make this even easier, which is to have instances automatically become the correct subclass when they are pulled in from the DB. This does have an overhead, pulling in a queryset with n items guarantees O(n) queries. This can be improved(just as it was for the previous solution) by ticket #7270 which allows select_related to traverse reverse relationships. In any event, we can write a metaclass to handle this for us automatically:
from django.db import models
from django.db.models.base import ModelBase
from django.db.models.fields import FieldDoesNotExist
from django.db.models.related import RelatedObject
class InheritanceMetaclass(ModelBase):
def __call__(cls, *args, **kwargs):
obj = super(InheritanceMetaclass, cls).__call__(*args, **kwargs)
return obj.get_object()
class InheritanceMixIn(models.Model):
__metaclass__ = InheritanceMetaclass
...
Here we've created a fairly trivial metaclass that subclasses the default one Django uses for it's models. The only method we've written is __call__, on a metalcass what __call__ does is handle the instantiation of an object, so it would call __init__. What we do is do whatever the default __call__ does, so that we get an instances as normal, and then we call the get_object() method we wrote earlier and return it, and that's all.
We've now looked at 2 ways to handle polymorphism, with this way being more efficient in all cases(ignoring the overhead of having the extra charfield). However, it still isn't totally efficient, and it fails in several edge cases. Whether automating the handling of something like this is a good idea is something that needs to be considered on a project by project basis, as the extra queries can be a large overhead, however, they may not be avoidable in which case automating it is probably advantages.
Saturday, January 31, 2009
Building a Magic Manager
A very common pattern in Django is to create methods on a manager to abstract some usage of ones data. Some people take a second step and actually create a custom QuerySet subclass with these methods and have their manager proxy these methods to the QuerySet, this pattern is seen in Eric Florenzano's Django From the Ground Up screencast. However, this requires a lot of repetition, it would be far less verbose if we could just define our methods once and have them available to us on both our managers and QuerySets.
Django's manager class has one hook for providing the QuerySet, so we'll start with this:
Here we have a very simple get_query_set method, it doesn't do anything but return it's parent's queryset. Now we need to actually get the methods defined on our class onto the queryset:
The trick here is we dynamically create a subclass of whatever class the call to our parent's get_query_set method returns, then we take each attribute on ourself, and if the queryset doesn't have an attribute by that name, and if that attribute is a method then we assign it to our QuerySet subclass. Finally we set the __class__ attribute of the queryset to be our QuerySet subclass. The reason this works is when Django chains queryset methods it makes the copy of the queryset have the same class as the current one, so anything we add to our manager will not only be available on the immediately following queryset, but on any that follow due to chaining.
Now that we have this we can simply subclass it to add methods, and then add it to our models like a regular manager. Whether this is a good idea is a debatable issue, on the one hand having to write methods twice is a gross violation of Don't Repeat Yourself, however this is exceptionally implicit, which is a major violation of The Zen of Python.
Django's manager class has one hook for providing the QuerySet, so we'll start with this:
from django.db import models
class MagicManager(models.Manager):
def get_query_set(self):
qs = super(MagicManager, self).get_query_set()
return qs
Here we have a very simple get_query_set method, it doesn't do anything but return it's parent's queryset. Now we need to actually get the methods defined on our class onto the queryset:
class MagicManager(models.Manager):
def get_query_set(self):
qs = super(MagicManager, self).get_query_set()
class _QuerySet(qs.__class__):
pass
for method in [attr for attr in dir(self) if not attr.startswith('__') and callable(getattr(self, attr)) and not hasattr(_QuerySet, attr)]:
setattr(_QuerySet, method, getattr(self, method))
qs.__class__ = _QuerySet
return qs
The trick here is we dynamically create a subclass of whatever class the call to our parent's get_query_set method returns, then we take each attribute on ourself, and if the queryset doesn't have an attribute by that name, and if that attribute is a method then we assign it to our QuerySet subclass. Finally we set the __class__ attribute of the queryset to be our QuerySet subclass. The reason this works is when Django chains queryset methods it makes the copy of the queryset have the same class as the current one, so anything we add to our manager will not only be available on the immediately following queryset, but on any that follow due to chaining.
Now that we have this we can simply subclass it to add methods, and then add it to our models like a regular manager. Whether this is a good idea is a debatable issue, on the one hand having to write methods twice is a gross violation of Don't Repeat Yourself, however this is exceptionally implicit, which is a major violation of The Zen of Python.
Saturday, January 24, 2009
Django Ajax Validation 0.1.0 Released
I've just uploaded the first official release of Django Ajax Validation up to PyPi. You can get it there. For those that don't know it is a reusable Django application that allows you to do JS based validation using you're existing form definitions. Currently it only works using jQuery. If there are any problems please let me know.
Monday, January 19, 2009
Optimizing a View
Lately I've been playing with a bit of a fun side project. I have about a year and half worth of my own chatlogs with friends(and 65,000 messages total) and I've been playing around with them to find interesting statistics. One facet of my communication with my friends is that we link each other lots of things, and we can always tell when someone is linking something that we've already seen. So I decided an interesting bit of information would be to see who is the worst offender.
So we want to write a function that returns the number of items each person has relinked, excluding items they themselves linked. So I started off with the most simple implementation I could, and this was the end result:
Here I iterated over the messages and for each one I went through each of the words and if any of them started with http(the definition of a link for my purposes) I checked to see if this had ever been linked before by someone other than the author of the current message.
This took about 4 minutes to execute on my dataset, it also executed about 10,000 SQL queries. This is clearly unacceptable, you can't have a view that takes that long to render, or hits your DB that hard. Even with aggressive caching this would have been unmaintainable. Further this algorithm is O(n**2) or thereabouts so as my dataset grows this would have gotten worse exponentially.
By changing this around however I was able to achieve far better results:
Here what I do is go through each of the messages which contain the string "http"(this is already a huge advantage since that means we process about 1/6 of the messages in Python that we originally were), for each message we go through each of the words in it, and for each that is a link we check if any other person has said it by looking in the caches we maintain in Python, and if they do we increment their count, finally we add the link to that persons cache.
By comparison this executes in .3 seconds, executes only 1 SQL query, and it will scale linearly(as well as is possible). For reference both of these functions are compiled using Cython. This ultimately takes almost no work to do and for computationally heavy operations this can provide a huge boon.
So we want to write a function that returns the number of items each person has relinked, excluding items they themselves linked. So I started off with the most simple implementation I could, and this was the end result:
from collections import defaultdict
from operator import itemgetter
from django.utils.html import word_split_re
from logger.models import Message
def calculate_relinks():
"""
Calculate the number of times each individual has linked something that was
linked previously in the course of the chat.
"""
links = defaultdict(int)
for message in Message.objects.all().order_by('-time').iterator():
words = word_split_re.split(message.message)
for word in words:
if word.startswith('http'):
if Message.objects.filter(time__lt=message.time).filter(message__contains=word).exclude(speaker=message.speaker).count():
links[message.speaker] += 1
links = sorted(links.iteritems(), key=itemgetter(1), reverse=True)
return links
Here I iterated over the messages and for each one I went through each of the words and if any of them started with http(the definition of a link for my purposes) I checked to see if this had ever been linked before by someone other than the author of the current message.
This took about 4 minutes to execute on my dataset, it also executed about 10,000 SQL queries. This is clearly unacceptable, you can't have a view that takes that long to render, or hits your DB that hard. Even with aggressive caching this would have been unmaintainable. Further this algorithm is O(n**2) or thereabouts so as my dataset grows this would have gotten worse exponentially.
By changing this around however I was able to achieve far better results:
from collections import defaultdict
from operator import itemgetter
from django.utils.html import word_split_re
from logger.models import Message
def calculate_relinks():
"""
Calculate the number of times each individual has linked something that was
linked previously in the course of the chat.
"""
links = defaultdict(set)
counts = defaultdict(int)
for message in Message.objects.all().filter(message__contains="http").order_by('time').iterator():
words = word_split_re.split(message.message)
for word in words:
if word.startswith('http'):
if any([word in links[speaker] for speaker in links if speaker != message.speaker]):
counts[message.speaker] += 1
links[message.speaker].add(word)
counts = sorted(counts.iteritems(), key=itemgetter(1), reverse=True)
return counts
Here what I do is go through each of the messages which contain the string "http"(this is already a huge advantage since that means we process about 1/6 of the messages in Python that we originally were), for each message we go through each of the words in it, and for each that is a link we check if any other person has said it by looking in the caches we maintain in Python, and if they do we increment their count, finally we add the link to that persons cache.
By comparison this executes in .3 seconds, executes only 1 SQL query, and it will scale linearly(as well as is possible). For reference both of these functions are compiled using Cython. This ultimately takes almost no work to do and for computationally heavy operations this can provide a huge boon.
Wednesday, January 14, 2009
New Admin URLs
I'm very happy to announce that with revision 9739 of Django the admin now uses normal URL resolvers and its URLs can be reversed. This is a tremendous improvement over the previous ad hoc system and it gives users the distinct advantage of being able to reverse the admin's URLs. However, in order to make this work a new feature went into the URL resolving system that any user can use in their own code.
Specifically users can now have objects which provide URLs. Basically this is because include() can now accept any iterable, rather than just a string which points to a urlconf. To get an idea of what this looks like you can look at the way the admin now does it.
There are going to be a few more great additions to Django going in as we move towards the 1.1 alpha so keep an eye out for them.
Specifically users can now have objects which provide URLs. Basically this is because include() can now accept any iterable, rather than just a string which points to a urlconf. To get an idea of what this looks like you can look at the way the admin now does it.
There are going to be a few more great additions to Django going in as we move towards the 1.1 alpha so keep an eye out for them.
Saturday, January 3, 2009
2008 and 2009
Eric Florenzano recently wrote an excellent post titled, "2008 in Review & 2009 Goals". I am now going to blantly steal his idea.
2008:
2009:
2008:
- Joined Twitter
- Voted for the first time
- Had a blast at PyCon
- Wrote a reusable Django application and open sourced it
- Learned git
- Got accepted at, and began studying Computer Science at RPI
- Wrote a blog post every day for 30 days in a row
- Started work on my programming language, Al
- Contributed heavily to Django
- Started a blog
- Proposed a panel for PyCon 2009 and was accepted
2009:
- Continue work on Al, bring it up to a usable state
- Continue writing on my blog
- Propose a talk for another conference
- Continue contributing to Django
- Become a committer on one of the projects I use
- Do something interesting over the summer, hopefully a cool internship or Google Summer of Code
- Do well in class
Subscribe to:
Posts (Atom)