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

61–70 of 72 posts

Re: Beating TimSort at Merging

#61

Post by actually_a_dog »

dang wrote: post #13

Past TimSort threads, for anyone interested: Timsort, the Python sorting algorithm - https://news.ycombinator.com/item?id=21196555 - Oct 2019 (131 comments) On the Worst-Case Complexity of TimSort - https://news.ycombinator.com/item?id=17883461 - Aug 2018 (74 comments) Timsort is a sorting algorithm that is efficient for real-world data - https://news.ycombinator.com/item?id=17436591 - July 2018 (77 comments) Functio…

I once had a Hackerrank problem that ultimately boiled down to "merge these sorted lists." I had 15 minutes, I think, to code the solution. I spent 10 of them deciding whether to use list.sort(), then finally just did it and cited the paper linked in On the Worst-Case Complexity of TimSort to claim linear time.

I passed, and ultimately got the job.

Re: Beating TimSort at Merging

#62

Post by lifthrasiir »

pg_bot wrote: post #49

I was thinking about how to make sorting faster the other day and was toying around with the idea of a permutation sort. If you think about a list of items generally (at least) one of the permutations of the list is guaranteed to be the correct sort order. Theoretically you should be able to do a binary search to find a correct permutation since there should always be a comparison you can do to reduce the search spac…

That wouldn't work for general n, but for smaller n, optimized sorting libraries frequently use size-optimal sorting networks [1] which effectively do the same thing (partitioning permutations into two halves with the minimal size difference).

[1] https://en.wikipedia.org/wiki/Sorting_network#Optimal_sortin...

Re: Beating TimSort at Merging

#63

Post by masklinn »

CogitoCogito wrote: post #17
typon wrote: post #9

Earlier quoted context omitted.

Because it's written in python

Re-writing it in C wouldn't automatically make much of a difference. Of course a C implementation wouldn't be slower (at minimum you could flatten out the byte-code sequence and use the generated C api calls), but it wouldn't necessarily be noticeably faster. Given the features of the python version, it might very well be the case that writing the same code in C wouldn't speed things up if the same use-cases were sup…

> Re-writing it in C wouldn't automatically make much of a difference.

It probably would even with a line-for-line translation: you’d save all the interpreter overhead, function calls if there are any (I did not look), and most refcount traffic.

Re: Beating TimSort at Merging

#64

Post by viraptor »

barosl wrote: post #50
borski wrote: post #37

Earlier quoted context omitted.

Gosh, comments like these from the actual author are a reminder of why I love HN. :)

I'm also amazed by the fact that that John Nagle from the popular Nagle's algorithm is still active on HN!

There are lots of known people on HN. I started tagging HN usernames with a browser extension some time ago and sometimes I spot some really interesting exchanges given the context of what the posters worked on.

Re: Beating TimSort at Merging

#65

Post by CogitoCogito »

masklinn wrote: post #63
CogitoCogito wrote: post #17

Earlier quoted context omitted.

Re-writing it in C wouldn't automatically make much of a difference. Of course a C implementation wouldn't be slower (at minimum you could flatten out the byte-code sequence and use the generated C api calls), but it wouldn't necessarily be noticeably faster. Given the features of the python version, it might very well be the case that writing the same code in C wouldn't speed things up if the same use-cases were sup…

> Re-writing it in C wouldn't automatically make much of a difference. It probably would even with a line-for-line translation: you’d save all the interpreter overhead, function calls if there are any (I did not look), and most refcount traffic.

Maybe. It's true you would save a certain amount of interpreter overhead and some refcount. How much that would help is not clear to me. So really I just see any speedups pure speculation honestly. Besides the interesting question isn't really whether it speeds up or not (it obviously will speed up at least a little bit with any non-sane implementation), but how _much_ it speeds up. If you gain 1% honestly who cares. If you gain 30%, then that's more interesting. And how close can you get with this more general version in C to the version in the blog post that is using a simplified implementation without all the extra features.

Anyway I am curious to know the answer, but I don't personally feel like writing out the implementation. If you do, I'd be interested in seeing the results.

Re: Beating TimSort at Merging

#66

Post by kilotaras »

CGamesPlay wrote: post #34

I definitely used this to my advantage in ACM ICPC contests. Most of the students and professors wrote the problems and benchmarked against Java. However, on several problems, it boiled down to "write this specific algorithm for this class of problem, or use C." I once netted my team an extra problem after we timed out in Java and I just rewrote the teammate's solution in C++.

My team used java in two cases: BigInteger or 'isProbableTime.' For everything else performance penalty was almost always unacceptable. C++ can also be sometimes finetuned enough to pass with unintended complexity (i.e. O(n lg n) instead of O(n)).

Re: Beating TimSort at Merging

#67

Post by kilotaras »

kilotaras wrote: post #66
CGamesPlay wrote: post #34

I definitely used this to my advantage in ACM ICPC contests. Most of the students and professors wrote the problems and benchmarked against Java. However, on several problems, it boiled down to "write this specific algorithm for this class of problem, or use C." I once netted my team an extra problem after we timed out in Java and I just rewrote the teammate's solution in C++.

My team used java in two cases: BigInteger or 'isProbableTime.' For everything else performance penalty was almost always unacceptable. C++ can also be sometimes finetuned enough to pass with unintended complexity (i.e. O(n lg n) instead of O(n)).

isProbableTime -> isProbablePrime.

Re: Beating TimSort at Merging

#68

Post by agbell »

viraptor wrote: post #64
barosl wrote: post #50

Earlier quoted context omitted.

I'm also amazed by the fact that that John Nagle from the popular Nagle's algorithm is still active on HN!

There are lots of known people on HN. I started tagging HN usernames with a browser extension some time ago and sometimes I spot some really interesting exchanges given the context of what the posters worked on.

I'd like to more about this. Can I use this?

Re: Beating TimSort at Merging

#69

Post by viraptor »

agbell wrote: post #68
viraptor wrote: post #64

Earlier quoted context omitted.

There are lots of known people on HN. I started tagging HN usernames with a browser extension some time ago and sometimes I spot some really interesting exchanges given the context of what the posters worked on.

I'd like to more about this. Can I use this?

Search for HN username tagging extension. There's quite a few options available.

Re: Beating TimSort at Merging

#70

Post by CogitoCogito »

CogitoCogito wrote: post #65
masklinn wrote: post #63

Earlier quoted context omitted.

> Re-writing it in C wouldn't automatically make much of a difference. It probably would even with a line-for-line translation: you’d save all the interpreter overhead, function calls if there are any (I did not look), and most refcount traffic.

Maybe. It's true you would save a certain amount of interpreter overhead and some refcount. How much that would help is not clear to me. So really I just see any speedups pure speculation honestly. Besides the interesting question isn't really whether it speeds up or not (it obviously will speed up at least a little bit with any non-sane implementation), but how _much_ it speeds up. If you gain 1% honestly who cares.…

I'm a bit amazed I've received downvotes for this post. I'm saying (1) you don't know how much this will speed up by going to C without trying it and (2) you don't know how much of the speed up in this case comes from the OP having written it in C and how much comes from the fact that it's a different algorithm. The fact that anyone would disagree with these (obviously true) statements is kind of incredible to me.
Post reply on HN