Earlier quoted context omitted.
Chances are you'll get an OutOfMemoryException first :)
The Java text file has a comment asking the user to allocate more memory for jvm.
Yes but that hardly works when you try to exploit a system..
On the Worst-Case Complexity of TimSort
71–78 of 78 posts
Re: On the Worst-Case Complexity of TimSort
#72Amazing there is still something to find in a sort algorithm.
Especially when targeting realistic machine models, there are a lot of things that are suboptimal about the classical sorting algorithms like quicksort or mergesort. For example, a quicksort with perfect choice of pivot will incur a branch miss with probability 50% for every element. That's not something classical complexity analysis measures, but on actual CPUs, branch misses have quite an impact (something like 10–…
I think I need to swear off of involving myself in order of complexity conversations and just get back to doing useful work. "The difference between theory and practice is that in theory there is no difference." and as processors evolve that just becomes more and more true for complexity calculations.
It's still a useful and helpful mental exercise but what matters is if I can do an operation cheaper and more reliably than you can. Order of complexity informs that decision but doesn't define it.
Even a moderately sized C is proportional to log(n) for quite a lot of data sets most of us actually work with. Conversely, adding, subtracting or comparing two numbers of arbitrary precision (eg, bignum) takes log(n) time, not O(1) time. Very few algorithms we call ∞
Complexity analysis is step 2. Step 1 being admitting you have a bottleneck. But there are a lot of other steps after those, with a lot of challenging, specialized work.
Re: On the Worst-Case Complexity of TimSort
#73Earlier quoted context omitted.
No, worst-case complexity of real quicksort is always O(n^2), regardless of pivot choice strategy (even with stochastic pivot choice, although you’d have to get very unlucky to hit that worst case). You can make the average case better or worse though. The only way of making quicksort’s worst-case runtime O(n log n) is by limiting recursion depth, as done e.g. in introsort. But that’s no longer quicksort.
This is wrong. See https://en.m.wikipedia.org/wiki/Quicksort , section "Selection-based pivoting".
Specifically,
> A variant of quickselect, the median of medians algorithm, chooses pivots more carefully, ensuring that the pivots are near the middle of the data (between the 30th and 70th percentiles), and thus has guaranteed linear time – O(n). This same pivot strategy can be used to construct a variant of quicksort (median of medians quicksort) with O(n log n) time. However, the overhead of choosing the pivot is significant, so this is generally not used in practice.
Re: On the Worst-Case Complexity of TimSort
#74Earlier quoted context omitted.
Especially when targeting realistic machine models, there are a lot of things that are suboptimal about the classical sorting algorithms like quicksort or mergesort. For example, a quicksort with perfect choice of pivot will incur a branch miss with probability 50% for every element. That's not something classical complexity analysis measures, but on actual CPUs, branch misses have quite an impact (something like 10–…
I think I need to swear off of involving myself in order of complexity conversations and just get back to doing useful work. "The difference between theory and practice is that in theory there is no difference." and as processors evolve that just becomes more and more true for complexity calculations. It's still a useful and helpful mental exercise but what matters is if I can do an operation cheaper and more reliabl…
It all depends on your machine model. You're right in that the RAM model doesn't model the performance characteristics of real-world computers very precisely. That's why it's a model :) Other models exist that can be used to analyse various aspects of algorithms, e.g. the External Memory model (which can be applied to any level of the memory hierarchy, e.g. to quantify data transfer between cache and RAM). Or you can count the number of hard-to-predict branches, etc.
We almost always assume that a machine word is large enough to describe the input size n. This usually implies constant-time operations on log(n) bits. Not doing so would clutter up notation and complicate analysis, and the whole point of using models is avoiding that where reasonably possible.
I mean you could take this thinking to the extreme and say that as we live in three-dimensional space, the wire length to access more and more memory has to grow at least with the cube root of the size of the memory, because that memory needs to physically be stored somewhere at the end of the day. That's not helpful for analysing algorithms, though :)
Re: On the Worst-Case Complexity of TimSort
#75Earlier quoted context omitted.
I think I need to swear off of involving myself in order of complexity conversations and just get back to doing useful work. "The difference between theory and practice is that in theory there is no difference." and as processors evolve that just becomes more and more true for complexity calculations. It's still a useful and helpful mental exercise but what matters is if I can do an operation cheaper and more reliabl…
It all depends on your machine model. You're right in that the RAM model doesn't model the performance characteristics of real-world computers very precisely. That's why it's a model :) Other models exist that can be used to analyse various aspects of algorithms, e.g. the External Memory model (which can be applied to any level of the memory hierarchy, e.g. to quantify data transfer between cache and RAM). Or you can…
But for instance in a world where horizontal scalability is almost a given, we have to allow that the cost of sending a message between 2 arbitrary servers is going to be at least log(n) time, because if you build a star topology your entire server room would be wires.
So if you're doing a distributed hash, the base cost of fetching two values to compare them is not only nothing to sneeze at, it is probably fundamental to how you solve the problem.
Re: On the Worst-Case Complexity of TimSort
#76The linked java test file, http://igm.univ-mlv.fr/~pivoteau/Timsort/Test.java - still crashes the latest Java 10.0.2 with an 'Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 49'. Amazing! I wonder if this makes some web services vulnerable.. if the user can submit a just-so array of ints to be sorted? But it does seem like it would require uploading a really huge array (>4GB?)
arrayToSort[sum] = 1; This is just blatant programmer error. The code is attempting to assign a value to a slot in an array of a fixed size, which does not exist. Use: Integer[] arrayToSort = new Integer[2000000000]; No error.
You are incorrect. Look at the error message more closely:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 49
at java.util.ComparableTimSort.pushRun(Unknown Source)
at java.util.ComparableTimSort.sort(Unknown Source)
at java.util.Arrays.sort(Unknown Source)
at Test.main(Test.java:80)
arrayToSort[sum] = 1;
Re: On the Worst-Case Complexity of TimSort
#77Earlier quoted context omitted.
I'd say it the other way around : 1/ it's amazing that a code that is used in countless occurences can still have a bug; 2/ (I've studied sorting algorithms for a while) finding such a bug is very clever... Kudo's to the authors.
What's amazing is how little understanding we seem to have over such critical widely-used code. Java opted for a complex and arguably unproven algorithm, so it was always a risk. We now have functional languages that are able to express provably correct sorting algorithms, so the bar is getting higher.
Provably correct and provably fast are widely different concepts.
Re: On the Worst-Case Complexity of TimSort
#78Earlier quoted context omitted.
It all depends on your machine model. You're right in that the RAM model doesn't model the performance characteristics of real-world computers very precisely. That's why it's a model :) Other models exist that can be used to analyse various aspects of algorithms, e.g. the External Memory model (which can be applied to any level of the memory hierarchy, e.g. to quantify data transfer between cache and RAM). Or you can…
But for instance in a world where horizontal scalability is almost a given, we have to allow that the cost of sending a message between 2 arbitrary servers is going to be at least log(n) time, because if you build a star topology your entire server room would be wires. So if you're doing a distributed hash, the base cost of fetching two values to compare them is not only nothing to sneeze at, it is probably fundament…
Now you’re in some unspecified distributed model without even defining your variables. Again, models are there to allow us to reason about things without going into every detail. It might make more sense to treat the time to open a connection and the time to send one machine word over an established connection as variables in asymptotic analysis. Then you can reason about sequential processing time, communication volume, and latency in one term.