Django Query Natural Sort
Question: Let's say I have this Django model:

    
    
    class Question(models.Model):
        question_code = models.CharField(max_length=10)
    

and I have 15k questions in the database.

I want to sort it by _question_code_ , which is alphanumeric. This is quite a
classical problem and has been talked about in:

  * <http://blog.codinghorror.com/sorting-for-humans-natural-sort-order/>
  * [Does Python have a built in function for string natural sort?](http://stackoverflow.com/questions/4836710/does-python-have-a-built-in-function-for-string-natural-sort)

I tried the code in the 2nd link (which is copied below, changed a bit), and
notice it takes up to 3 seconds to sort the data. To make sure about the
function's performance, I write a test which creates a list of 100k random
alphanumeric string. It takes only 0.76s to sort that list. So what's
happening?

This is what I think. The function needs to get the _question_code_ of each
question for comparing, thus calling this function to sort 15k values means
requesting mysql 15k separate times. And this is the reason why it takes so
long. Any idea? And any solution to natural sort for Django in general? Thanks
a lot!

    
    
    def natural_sort(l, ascending, key=lambda s:s):
        def get_alphanum_key_func(key):
            convert = lambda text: int(text) if text.isdigit() else text
            return lambda s: [convert(c) for c in re.split('([0-9]+)', key(s))]
        sort_key = get_alphanum_key_func(key)
        return sorted(l, key=sort_key, reverse=ascending)
    


Answer: As far as I'm aware there isn't a generic Django solution to this. You can
reduce your memory usage and limit your db queries by building an
id/question_code lookup structure

    
    
    from natsort import natsorted
    question_code_lookup = Question.objects.values('id','question_code')
    ordered_question_codes = natsorted(question_code_lookup, key=lambda i: i['question_code'])
    

Assuming you want to page the results you can then slice up
ordered_question_codes, perform another query to retrieve all the questions
you need order them according to their position in that slice

    
    
    #get the first 20 questions
    ordered_question_codes = ordered_question_codes[:20]
    question_ids = [q['id'] for q in ordered_question_codes]
    questions = Question.objects.filter(id__in=question_ids)
    #put them back into question code order
    id_to_pos = dict(zip((question_ids), range(len(question_ids))))
    questions = sorted(questions, key = lambda x: id_to_pos[x.id])
    

If the lookup structure still uses too much memory, or takes too long to sort,
then you'll have to come up with something more advanced. This certainly
wouldn't scale well to a huge dataset

