Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Beating TimSort at Merging

earthly.dev

Post reply on HN
Print view View original

21–30 of 72 posts

Re: Beating TimSort at Merging

#21

Post by masklinn »

jhokanson wrote: post #10

As someone that rarely works with Python lists, as opposed to numpy arrays, I was pleasantly surprised to see numpy does what I would expect in providing a mergesort option. I'm surprised Python doesn't, other than via heapq and only implemented in Python (according to my reading of the post and a very quick Google search). Oops, just for fun the numpy documentation currently states: "The datatype determines which of…

Why would Python provide a mergesort option when timsort was the replacement for a standard mergesort?

`heapq.merge` is not a mergesort, it's a merge of sorted sequences (aka just the merge part of a mergesort).

Re: Beating TimSort at Merging

#22

Post by CogitoCogito »

adamgordonbell wrote: post #19
lyxell wrote: post #5

Interesting read. This post seems to be written by Adam Gordon Bell who is also the host of the excellect CoRecursive podcast. Recently featured at HN in The Untold Story of SQLite [0]. [0]: https://news.ycombinator.com/item?id=27718701

That's me. Thanks for reading it and listening to the podcast. The SQLite episode is now nearly the most listened to, thanks to hacker news. On Merging lists: I was caught off guard by recommendation to use sort to merge sorted lists. Everyone I mentioned it to was surprised as well so I thought it was worthy of some investigation. This is my first C extension in Python and I got help so someone else might be able to…

> It is interesting when our normal short hands for thinking about runtime complexity break down.

Actually I think more interesting would be to write a python version following the algorithm of your C extension (i.e. only allow two lists, don't allow generators, don't return generators, etc). You could probably do that quite quickly and generate the same graphs. I would expect that python version to lie somewhere between your C extension and the heapq.merge() version which is more general.

edit: If you were to do this, I wouldn't recommend using the python version in your blog since it pops the lists from the front. This seems to be O(n) in general:

https://wiki.python.org/moin/TimeComplexity

I did a 10 minute glance at the python source code and couldn't totally verify this (it needs more than 10 minutes...), but it makes sense for popping from anywhere but the back to cause a list copy to occur. Maybe this isn't technically necessary when popping from the front, but I couldn't verify it. Either way it's easy to avoid by just not mutating the input lists anyway so I don't see a good reason not to go that way.

Re: Beating TimSort at Merging

#24

Post by kzrdude »

jhokanson wrote: post #10

As someone that rarely works with Python lists, as opposed to numpy arrays, I was pleasantly surprised to see numpy does what I would expect in providing a mergesort option. I'm surprised Python doesn't, other than via heapq and only implemented in Python (according to my reading of the post and a very quick Google search). Oops, just for fun the numpy documentation currently states: "The datatype determines which of…

mergesort mandates that it's a stable sort, so I guess they get away with replacing "like for like" that way. For varying definitions of like.

Re: Beating TimSort at Merging

#25

Post by adamgordonbell »

CogitoCogito wrote: post #22
adamgordonbell wrote: post #19

Earlier quoted context omitted.

That's me. Thanks for reading it and listening to the podcast. The SQLite episode is now nearly the most listened to, thanks to hacker news. On Merging lists: I was caught off guard by recommendation to use sort to merge sorted lists. Everyone I mentioned it to was surprised as well so I thought it was worthy of some investigation. This is my first C extension in Python and I got help so someone else might be able to…

> It is interesting when our normal short hands for thinking about runtime complexity break down. Actually I think more interesting would be to write a python version following the algorithm of your C extension (i.e. only allow two lists, don't allow generators, don't return generators, etc). You could probably do that quite quickly and generate the same graphs. I would expect that python version to lie somewhere bet…

So we could determine what gains I am getting are due to C and the specific compares and which are due just being 2 lists? That would be an interesting test.

Maybe I'll do a follow-up. Thanks for reading the article. I suspect you know way more about C extensions in Python than I do. I saw you have a talk on this topic.

I think you are totally right that pop is not the way to go, but using an offset to track the head, like the C example does. I actually put that in a footnote, because I was considering testing my python version but the SO answer mentioned pop being expensive.

I think the simple version is still great as psuedo-code for communicating a solution though and hopefully it makes the c code a bit easier to follow once you've seen the python version.

Re: Beating TimSort at Merging

#26

Post by CogitoCogito »

adamgordonbell wrote: post #25
CogitoCogito wrote: post #22

Earlier quoted context omitted.

> It is interesting when our normal short hands for thinking about runtime complexity break down. Actually I think more interesting would be to write a python version following the algorithm of your C extension (i.e. only allow two lists, don't allow generators, don't return generators, etc). You could probably do that quite quickly and generate the same graphs. I would expect that python version to lie somewhere bet…

So we could determine what gains I am getting are due to C and the specific compares and which are due just being 2 lists? That would be an interesting test. Maybe I'll do a follow-up. Thanks for reading the article. I suspect you know way more about C extensions in Python than I do. I saw you have a talk on this topic. I think you are totally right that pop is not the way to go, but using an offset to track the head…

Well the version I'm saying is essentially the same as the pop version you have so I don't think it's too complicated. You would just do something like this instead:

    def merge_sorted_lists(l1, l2):
        sorted_list = []
        i = 0
        j = 0
        while i
I haven't tested that (you probably should before using it), but it looks mostly right and is essentially the same algorithm as yours.

Re: Beating TimSort at Merging

#27

Post by danbruc »

The first Python implementation is bad - removing the first element in each iteration is O(n), the C implementation gets this right by maintaining one index into each list instead of modifying the lists.

Re: Beating TimSort at Merging

#28

Post by XelNika »

danbruc wrote: post #27

The first Python implementation is bad - removing the first element in each iteration is O(n), the C implementation gets this right by maintaining one index into each list instead of modifying the lists.

Yes, it says so in footnote 1 in the article. It's also not the benchmarked code so it doesn't really matter.

Re: Beating TimSort at Merging

#29

Post by toxik »

CogitoCogito wrote: post #20
tehjoker wrote: post #18

Earlier quoted context omitted.

This is not true. I have written many libraries to improve on the performance of numpy for image processing applications. Sort backs many operations, such as unique, that result in painfully slow code.

I too have written a lot of extension code to speed up numpy code. It's often not even especially difficult since any code at that level tends to be very algorithmic and looks essentially the same if written in numpy or C++. Having control of the memory layout and algorithms can be a huge win. Of course I don't _usually_ do this, but that's just be most of the code I write doesn't need it. But it's not at all some cr…

Tangential but np.bincount is typically the fast version of np.unique. Not entirely the same thing, but it’s worth knowing about it.

Re: Beating TimSort at Merging

#30

Post by ww520 »

forrestthewoods wrote: post #6

Great post. I almost did a spit take when I read: > Timsort overcomes this disadvantage by being written in C rather than Python. Yeah, Python is SLOW. Thankfully the author dug into C. That was nice to see. Edit: lol I have no idea why this is being downvoted. Y’all weird.

That's what I suspected when reading the first part of the post where it states that heapq.merge() is slower than sort(). Hmm, isn't it comparing Apple to Orange since heapq.merge() is implement in Python and the system sort() would be in C?
Post reply on HN