Earlier quoted context omitted.
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.
Jumping in this fascinating thread about sorting to ask what the double less than chevrons mean? I know what one means but what do two of them mean?
Timsort, the Python sorting algorithm
111–120 of 135 posts
Re: Timsort, the Python sorting algorithm
#112Earlier quoted context omitted.
The person never said that you had to google it to be a "proper developer", just that they hoped that every python developer would have done so.
I hate to disappoint that hope but I have never search for Python's sorting algorithm.
What about the hash strategy used in dicts? I'm holding on to hope.
Re: Timsort, the Python sorting algorithm
#113Earlier quoted context omitted.
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.
Jumping in this fascinating thread about sorting to ask what the double less than chevrons mean? I know what one means but what do two of them mean?
Basically “much less than”.
Re: Timsort, the Python sorting algorithm
#114Earlier 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.)
> beyond the current level of technology
I’m sure there quite a few languages that will catch that at compile time.
Re: Timsort, the Python sorting algorithm
#115My favourite TimSort story is of ex-Sun employee, Joshua Bloch of Effective Java fame. J Bloch was in audience at the time when Tim Peters presented his new algorithm to sort a list, and he was so blown away that he started porting Tim's implementation right there with an intent to commit it to the JDK mainline [0], which he eventually did [1]. [0] Some of the core JDK developers are really on another level. The JDK…
And then 3 years later we have [0] and 6 years after that we have [1]. I appreciate Masters of the Universe types like Bloch and Lea contributing wickedly-efficient code, but somehow it's always mere mortals who end up mopping things up after the fact. Whether it's a bug in the actual algorithm or a "Comparison method violates its general contract!" exception that happens once in a blue moon, I think putting TimSort…
> I appreciate Masters of the Universe types like Bloch and Lea contributing wickedly-efficient code, but somehow it's always mere mortals who end up mopping things up after the fact
I think this is the wrong way to look at the problem. Progress is always iterative. If a given person happens to make a bigger iteration, then people call them 'masters of the universe', but that iteration isn't inherently different from the normal, smaller kind of iteration. And - consider: if every line of code has a chance of being buggy, then a bigger change is likelier to be more buggy. I say more buggy, rather than have more bugs, because bugginess is rarely disconnected; the whole conception is likely to be more flawed the newer it is. If we were to only accept small contributions then, somewhere along the way from here to the limit, we would arrive at timsort. And all the flaws of timsort wouldn't be gone, they would just be amortized into smaller chunks along the way from here to there. Which may be preferable, but that's something you have to consider; it's not so cut-and-dry as 'if we only make change conservatively, then we avoid catastrophic failure'.
All this not to mention that there are people who are 'masters of the universe' at fixing bugs.
Re: Timsort, the Python sorting algorithm
#116Earlier 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.)
> beyond the current level of technology I’m sure there quite a few languages that will catch that at compile time.
It is possible for a compiler to catch that particular mistake at compile-time. It's also possible for the user to provide a proof to a given compiler that a comparison function is well-formed. But I think that the parent was referring to a function that would check arbitrary comparison functions in java for correctness, without a proof, which is afaik provable impossible.
Re: Timsort, the Python sorting algorithm
#117Earlier quoted context omitted.
Then, many years later, input was found that made the Java version crash: https://link.springer.com/chapter/10.1007/978-3-319-21690-4_...
I found a similar problem using a fairly battle-tested C# implementation of timsort. Felt lucky that I had managed to reproduce it in a dev environment instead of it being a mysterious crash for users.
Many years ago, I copied an implementation of the Cohen-Sutherland algorithm (for line clipping) to C++ from pseudo code (I don't remember where I got this pseudo code from, but other sources used equivalent pseudo code).
The code (it was a backend server code for a web app) was heavily tested with ab [0] and JMeter [1] against extreme load, everything seemed to worked fine. Fast-forward 6 months, when we had a sudden peak in users (for a few days, we went from around 500 visitors a day to around 500.000, which roughly meant > 5 million requests per day). Suddenly, the backend, which ran without problems for half a year, crashed in production every 5 hours or so with a segmentation fault. I could not for the life of me reproduce this. After some panicking, I let the backend run in gdb in production against the ~50 requests per second we were still getting. After a few hours, the segfault occurred again, and I figured out that on extremely rare edge cases, the pseudo code I copied to C++ divided by 0, which lead to chain of problems afterwards, eventually resulting in said segfault. If I remember correctly, the fix was trivial.
Re: Timsort, the Python sorting algorithm
#118Earlier quoted context omitted.
Practice, challenge yourself constantly, seek mentorship, humbly request feedback and act on it, and devote your life to the craft, not your wallet or your family. I think. Read Hamming.
Easier said than done
If it was easy, folks wouldn't have to ask how it could be done and everyone would that THAT good. ;)
Re: Timsort, the Python sorting algorithm
#119My favourite TimSort story is of ex-Sun employee, Joshua Bloch of Effective Java fame. J Bloch was in audience at the time when Tim Peters presented his new algorithm to sort a list, and he was so blown away that he started porting Tim's implementation right there with an intent to commit it to the JDK mainline [0], which he eventually did [1]. [0] Some of the core JDK developers are really on another level. The JDK…
Then, many years later, input was found that made the Java version crash: https://link.springer.com/chapter/10.1007/978-3-319-21690-4_...
It seems like a standard library sort-function is the ideal candidate for investing in proving correctness.
Re: Timsort, the Python sorting algorithm
#120Earlier quoted context omitted.
I agree in theory. But in practice that specific caller's code bug was so widespread and Timsort broke so much existing code that it warranted offering a "-Djava.util.Arrays.useLegacyMergeSort=true" option. The specific line from the Javadoc you're alluding to [0] is: > The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for all x and y. The problem is the second implied half of that statement: Pr…
It seems way better to fail with a RuntimeException than to get possibly unsorted results that cause some hideous error deeper in your application.
It depends on the contract.
It's good to have a contract that defines behaviour even in the case of invalid input.
That could be throwing an error, or it could be given unsorted input. Either way is ok.
(The C and C++ answer is to leave the behaviour in the face of invalid input undefined. Undefined means that anything goes, including formatting your hard disk.)