On Thu, Jan 20, 2011 at 12:48 PM, Dan Stromberg <drsali...@gmail.com> wrote: > On Thu, Jan 20, 2011 at 11:36 AM, Jake Biesinger > <jake.biesin...@gmail.com> wrote: >>> Thanks for the great suggestions! >> >> On a related note, is there no way to efficiently sort a python array? >> >> >>>>> x = array('f', xrange(10000000)) >>>>> x.sort() >> --------------------------------------------------------------------------- >> AttributeError Traceback (most recent call last) >> >> /home/wbiesing/src/python-sort/<ipython console> in <module>() >> >> AttributeError: 'array.array' object has no attribute 'sort' >> >>>>> type(sorted(x)) >> <type 'list'> >> >> Seems like a common enough task, but no way to do it efficiently without >> scipy/numpy. > > Tap, tap: Is this thing on? I keep sending messages to this list, but > no one seems to "hear" what I'm writing.
Hey Dan, indeed thanks for the code; I pulled it down and played around with timsort a while ago. Timsort is indeed a beast. My current solution is to do an argsort. Since I can't roll with your cython implementations (pure python *only*), this seems a bit faster than sorting the original two lists using a modified pure-python timsort. Something along the lines of: args = sorted(range(len(seq1)), key=seq1.__getitem__) seq1 = [seq1[i] for i in args] seq2 = [seq2[i] for i in args] but the method suffers from a fairly high memory usage (big list of int's for args). If this barrier is too high, I will be switching over to your pure-python timsort. > Anyway, I have a bunch of sorts in python (pure or cython, your > option) at > http://stromberg.dnsalias.org/cgi-bin/viewvc.cgi/sorts/compare/trunk/?root=svn > > The pure python versions should all work out of the box with an > array.array. I tested the timsort on an array.array, and it worked > well. your pylint runs fail for me, saying you should use disable, not disable-msg. pylint 0.23.0, astng 0.21.1, common 0.54.0 Python 2.6.6 (r266:84292, Sep 15 2010, 16:22:56) [GCC 4.4.5] > Also, I just made a trivial modification (not checked in! ...but I did > test it) to make the cythonized timsort support sorting arrays - just > change the "list" type declarations to "object" (or perhaps > "array.array") prior to compiling. I'm not very familiar with cython syntax-- how do you bring in the array module? cimport array? import array? I see you need to change cdef list to cdef array.array or something like that. Perhaps you could send a diff? Thanks! -- http://mail.python.org/mailman/listinfo/python-list