I wrote this after reading The Alphanum Algorithm (http://www.davekoelle.com/alphanum.html) by David Koelle a few years ago; my goal was to improve the performances of the Python version of his scripts.
My version is approximatly 10 times faster than it's
alphanum.py and about 3 times faster than the
alphanum.py_v2.4 on my computer, yielding the same results (for non-unicode at least).
Note: see the version of wizkid in the comments which is even faster.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
def keynat(string): '''A natural sort helper function for sort() and sorted() without using regular expression. ''' r =  for c in string: if c.isdigit(): if r and isinstance(r[-1], int): r[-1] = r[-1] * 10 + int(c) else: r.append(int(c)) else: r.append(c) return r
>>> items = ['Z', 'a', '10', '1', '9'] >>> sorted(items) ['1', '10', '9', 'Z', 'a'] >>> sorted(items, key=keynat) ['1', '9', '10', 'Z', 'a'] >>> items.sort(cmp=lambda a,b:cmp(keynat(a), keynat(b))) >>> items ['1', '9', '10', 'Z', 'a']
Where is "keynat2"?
Damn, i should try to check what i'm posting sometimes :) thanks for reporting the typo.
I made my own version before I found this post. So I benchmarked both.
On small keys mine was 30% faster:
And on larger keys it was about 50% faster
My function looks like this. And I think one reason is that I don't call int() on every digit:
Hi wizkid, yes, your version made mine totally obsolete; is 44 to 60% faster than mine on my setup. Thank's for sharing it!