Timsort, the Python sorting algorithm • Hacker News Board

Re: Timsort, the Python sorting algorithm

#131

Post by estebank » Wed, Oct 09, 2019, 7:37 PM UTC

chc wrote: post #68

AnimalMuppet wrote: post #57

Earlier quoted context omitted.

If you supply an invalid comparison function to your sort function, which would you prefer to happen - that it crash, or that it give you unsorted output? (If you actually wanted sorted output, you should have provided a valid comparison function.)

Ideally I'd like a compile-time error — but that's beyond the current level of technology, so the next best thing is a crash. Having code that does unintended things is the worst-case scenario IMO. (Obviously it's the programmer's fault for providing buggy code, but that's a fault that every programmer shares. Personally, I appreciate any help in guarding against it.)

> but that's beyond the current level of technology

Is it? In Rust and other languages you would use trait bounds to restrict the input types to be comparable with each other, which would make this a compile time error.

Re: Timsort, the Python sorting algorithm

#132

Post by hinkley » Wed, Oct 09, 2019, 7:52 PM UTC

cbarrick wrote: post #105

hinkley wrote: post #43

Earlier quoted context omitted.

It concerns me that the most recent citation in that bibliography says “ We achieve our goal using Recursive Partitioning combined with In Place merging to sort a given array” Stack frames are external storage. I’d have to see the code to see how they manage to do recursion without log(n) external storage. Traditional merge sort can be written using iteration, which makes the external storage for sort state O(1), but…

To be fair, tail calls don't require stack frames. If it's just a matter of keeping up with the bounds of the partitions, I can see that being done in constant space.

This isn’t a tail call situation, though. In order to convert it to iteration you have to use external storage.

Re: Timsort, the Python sorting algorithm

#133

Post by Dylan16807 » Wed, Oct 09, 2019, 9:08 PM UTC

estebank wrote: post #131

chc wrote: post #68

Earlier quoted context omitted.

Ideally I'd like a compile-time error — but that's beyond the current level of technology, so the next best thing is a crash. Having code that does unintended things is the worst-case scenario IMO. (Obviously it's the programmer's fault for providing buggy code, but that's a fault that every programmer shares. Personally, I appreciate any help in guarding against it.)

> but that's beyond the current level of technology Is it? In Rust and other languages you would use trait bounds to restrict the input types to be comparable with each other, which would make this a compile time error.

How does that prevent you from accidentally making a.compare(b) and b.compare(a) inconsistent on some values?

Making sure you can compare the types is already happening in the compiler, and doesn't find the bug.

Re: Timsort, the Python sorting algorithm

#134

Post by Dylan16807 » Wed, Oct 09, 2019, 9:40 PM UTC

bloomer wrote: post #100

joshuamorton wrote: post #78

Earlier quoted context omitted.

No, radix sort is worst case O(n * k). In many common cases, k ~= log(n). IN certain specific cases, k < log(n), and specifically for cases where you have a very large n, but a bounded number of values (say, you're sorting 10 billion 4-bit ints), k can be considered a constant. But that is by no means generally true.

In most cases k << n. For 64-bit integers, byte wise radix sort k is 8, which is less than log n whenever n is more than 256. So, radix sort is typically much faster than an O(n log n) sort of your data support it. It just isn’t as widely used because it is not as general as a comparison based sort.

That logic isn't right. You can implement an O(n log n) sort with whatever log base/radix you want. It could be 2, it could be 256, it could be 4096. If you use the same base/radix for both n and k, then log n is close to k and probably smaller.

Which version ends up faster is mostly based on factors that big O notation doesn't capture easily. You have to push things to impractical numbers like n=2^1000 or 2^1000000 to properly distinguish between constant factors and log factors, and at that point it doesn't actually help you write better code.

Re: Timsort, the Python sorting algorithm

#135

Post by nullc » Thu, Oct 10, 2019, 6:38 AM UTC

unnouinceput wrote: post #102

saagarjha wrote: post #95

Earlier quoted context omitted.

I suggest you read up on how superposition works in quantum computers–they not just computers with an infinite number of cores :/

No, they are not. Also 128 billion is a big enough number that if you'd say to a 18th century scientist who was working with punch cards computers that in the future one with 128 billion punch cards would exists he would've replied something along the lines, just like you, that there are not enough trees on Earth to create 128 billion cards for a single computer, let alone billion of them that they are more common th…

If you are going to come up with purely conjectural advantages with no basis in known science, why bother attributing them to one thing (like quantum computing) and not any other thing?

Like why are you not arguing that C++24 will make all algorithms O(1)? There is as much reason to believe that as there is to believe that quantum computing will do so.

Or maybe graphene memresistors will form timelike loops and allow computers that give you results before you ask the question? Maybe! Again, no more reason to think that won't happen than some kind of purely conjectural magic from quantum computation.

Maybe the development of green energy such as solar panels will lead to the development of nano-scale self assemblers, allow us to turn the entire moon into ultra efficient computronium powered by sinking the moon's residual heat of formation into deep space, making the asymptotic complexity of most algorithms on many problems largely irrelevant. Maybe! Or maybe the insight might actually come from a school kid that trips over a rock and gets a vision after hitting their head. Better start putting pebbles out in front of schools, because you never know! :)

Isn't getting a sqrt() speedup for everything and an exponential speed up for a few things good enough for you?

If we really understand the idea of quantum computing so poorly that that we've massively underestimated it, isn't it even more likely that our misunderstanding has made us massively overestimate it?