Doesn't explain why Earthly.dev is under the BSL.
I don't know why you would expect a post with a title like this to touch on that, even though being wary of the BSL licence is fair.
Beating TimSort at Merging
41–50 of 72 posts
Re: Beating TimSort at Merging
#42To get more gonzo, in CPython's list.sort(), the C code that actually merges two lists (which happen, in context, to be two contiguous array slices) is in listobject.c's `merge_at(()` function. That brings in the world of "galloping" (exponential search) optimizations, much faster than one-pair-at-a-time compares in many real-world cases. So that's a whole lot of additional complication, but it's the heart of what _r…
Wow. Thanks for writing it. I believe this is the part you are referring to: https://github.com/python/cpython/blob/main/Objects/listobje...
Right, `merge_at()`. But that in turn calls small mountains of other C code. It is, alas, a complicated approach. Folding it in would be substantially more work than you've already done.
The point: for inputs like your:
a = list(range(-100, 1700)) b = list(range(1400, 1800))
it would first use a variant of binary search to find where b[0] belongs in a. "Almost all of a" is consumed by that via a relatively tiny number of compares. It would similarly do a binary-ish search to find where a[-1] belongs in b. The tail end of b, from 1700 through 1799, then also never needs to be looked at again.
In the lucky case that two input lists don't overlap at all, and a[-1] <= b[0], that's enough so that a "one-pair-at-a-time" compare _never_ needs to be done. In context (the two lists are contiguous slices of an array), no pointers at all need to be copied in that case either - it deduces that the combined array slices are already in sorted order in total time O(log(len(a)) + log(len(b))), and it's done.
Re: Beating TimSort at Merging
#43Earlier quoted context omitted.
Wow. Thanks for writing it. I believe this is the part you are referring to: https://github.com/python/cpython/blob/main/Objects/listobje...
Right, `merge_at()`. But that in turn calls small mountains of other C code. It is, alas, a complicated approach. Folding it in would be substantially more work than you've already done. The point: for inputs like your: a = list(range(-100, 1700)) b = list(range(1400, 1800)) it would first use a variant of binary search to find where b[0] belongs in a. "Almost all of a" is consumed by that via a relatively tiny numbe…
Very Cool!
Edit: Ok, I get it now. Don't just pop, binary search into it, so you can fast forward through. I'm not sure I'll get around to implementing that, at least not in the immediate future, but that makes total sense.
Re: Beating TimSort at Merging
#44To get more gonzo, in CPython's list.sort(), the C code that actually merges two lists (which happen, in context, to be two contiguous array slices) is in listobject.c's `merge_at(()` function. That brings in the world of "galloping" (exponential search) optimizations, much faster than one-pair-at-a-time compares in many real-world cases. So that's a whole lot of additional complication, but it's the heart of what _r…
Is there a reason to use galloping over an array vs a seek in a search tree?
Better real world factors?
Galloping, Demaine set intersection, worst case optimal joins, they all seem to be different aspects of the same underlying principle.
So I'm very curious about the peculiarities in the sorting case.
Re: Beating TimSort at Merging
#45[deleted]
Re: Beating TimSort at Merging
#46To get more gonzo, in CPython's list.sort(), the C code that actually merges two lists (which happen, in context, to be two contiguous array slices) is in listobject.c's `merge_at(()` function. That brings in the world of "galloping" (exponential search) optimizations, much faster than one-pair-at-a-time compares in many real-world cases. So that's a whole lot of additional complication, but it's the heart of what _r…
I had the same idea, that re-using a lot of the non-sort parts of the TimSort code in this merge, the result would be just "Tim".
Re: Beating TimSort at Merging
#47Earlier quoted context omitted.
Right, `merge_at()`. But that in turn calls small mountains of other C code. It is, alas, a complicated approach. Folding it in would be substantially more work than you've already done. The point: for inputs like your: a = list(range(-100, 1700)) b = list(range(1400, 1800)) it would first use a variant of binary search to find where b[0] belongs in a. "Almost all of a" is consumed by that via a relatively tiny numbe…
Very Cool! Edit: Ok, I get it now. Don't just pop, binary search into it, so you can fast forward through. I'm not sure I'll get around to implementing that, at least not in the immediate future, but that makes total sense.
You already got a win - quit while you're ahead ;-) Note that plain binary search here is probably not a good idea. See "listsort.txt", in the same directory as "listobject.c", for excruciating details.
Re: Beating TimSort at Merging
#48To get more gonzo, in CPython's list.sort(), the C code that actually merges two lists (which happen, in context, to be two contiguous array slices) is in listobject.c's `merge_at(()` function. That brings in the world of "galloping" (exponential search) optimizations, much faster than one-pair-at-a-time compares in many real-world cases. So that's a whole lot of additional complication, but it's the heart of what _r…
Is there a reason to use galloping over an array vs a seek in a search tree? Better real world factors? Galloping, Demaine set intersection, worst case optimal joins, they all seem to be different aspects of the same underlying principle. So I'm very curious about the peculiarities in the sorting case.
See CPython's https://github.com/python/cpython/blob/main/Objects/listsort...
for details about the sort. In fact, its "galloping" was inspired by a paper of which Demaine was a co-author (reference in the file already linked to).
CPython's lists are implemented as contiguous C arrays of pointers (to Python objects). Any way of grafting a tree-ish structure on top of that would be unacceptably wasteful of space and/or time. So sorting "gallops" over arrays because it's array-in, array-out.
Re: Beating TimSort at Merging
#49I 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 space by half. You should be able to go faster if there is duplicated data since there are multiple permutations of the list that would work.
Re: Beating TimSort at Merging
#50To get more gonzo, in CPython's list.sort(), the C code that actually merges two lists (which happen, in context, to be two contiguous array slices) is in listobject.c's `merge_at(()` function. That brings in the world of "galloping" (exponential search) optimizations, much faster than one-pair-at-a-time compares in many real-world cases. So that's a whole lot of additional complication, but it's the heart of what _r…
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!