5 ms·

Quick sort comes with a steep penalty. Worst case is O(n^(2)). The reason quicksort is good is because it's in place. Once you throw away the in place aspect of

Quick sort comes with a steep penalty. Worst case is O(n^(2)). The reason quicksort is good is because it's in place. Once you throw away the in place aspect of quick sort, it's straight up bad. This implementation of quicksort is actually a great example of why functional programming sucks. It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead. Algorithms that are optimal under the mutable data assumption are different than algorithms that are optimal under the constant data assumption. So a normal programmer might sort via quicksort in Haskell because it's the optimal sort in imperative languages even though naive Haskell quicksort is objectively worse in every way than naive Haskell mergesort. Performant programming in Haskell requires a much more intimate understanding of the underlying architecture than performant programming in, for instance, C++. And that's a very low bar.

kccqzy 7y ago
> It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead. Please tell me what imperative quicksort algorithm has O(1) space. All versions I've seen and could recall use recursion; although each recursive call uses O(1) space, in the worst case of bad pivot element selection each recursive call would only really sort one element resulting in a worst-case O(n) space. Use of randomization would result in a high probability of choosing a good pivot element, but even then you can expect approximately O(log n) space. Also would like to see why you think the Haskell version has enormous constant time overhead. Where do you think this overhead comes from? If you are comparing to an equivalent program in C++ then sure allocations and stuff, but compared with the typical Haskell list-processing programs I don't see any significantly larger overhead.
- foota 7y ago
  I don't know that I would ever do this, since O(lgn) space is normally trivial, but couldn't you use a RNG that's based on like the depth and start position of a given "stack frame" of a recursion-less quicksort? Like to "recurse" (not actually recurse, but pretend) you would increment depth, the update the start position, and calculate the new partition index based on the (depth, start) tuple? And run that in reverse for going back up the stack. edit: Hah. This is fun. There's a variant where you do tricks with the elements of the array to get constant space. https://link.springer.com/chapter/10.1007/BFb0016252 https://link.springer.com/chapter/10.1007/BFb0016252 The idea is that you partition the elements, but then instead of storing the bounds of the left and right sides, you switch the element from the start of the right side with the partition element of the "stack frame" above you. This later serves as a flag indicating the end of the right side, since the partition of the parent "stack frame" is greater than all elements on the right you know you've hit then end of the right side when you see a larger number than the parent "stack frame"'s pivot.
- ivalm 7y ago
  For non recursive quicksorts see code at bottom of this link: https://www.geeksforgeeks.org/iterative-quick-sort/ https://www.geeksforgeeks.org/iterative-quick-sort/
  - kccqzy 7y ago
    That link basically just simulates recursion by defining a stack in the function. It recognizes that in the recursive version among the stack variables only the two indexes need to be stored so it stores them. It is even less space efficient than the recursive version because it always allocates O(n) space.
- scythe 7y ago
  The path towards O(1) space instead of O(log n) space is fraught with technicalities. At the bottom, you realize that no matter what algorithm you use, you always store the array size in lg(n) bits! So it makes more sense to say “less memory” rather than O(1) memory for sorts.
brokencode 7y ago
I don’t see how this is a great example of how functional programming sucks. It is easy in any programming language to build a slow sorting algorithm. The fact that you need to use different algorithms with immutable data is irrelevant. You need to use different algorithms for pretty much any type of data structure. Functional programming makes a different set of tradeoffs than imperative programming. You have to work harder to get peak performance, but in many cases it is actually quite performant. Just look at how fast Elm is for web applications, and how that approach allows for a time-traveling debugger and virtually no crashes.
mirekrusin 7y ago
I remember on olympiads one trick that I though was brilliant out-of-the-box thinking was to shuffle input before sorting to avoid worst-case-prepared inputs.
tombert 7y ago
Ok, I’ll bite. If having to think a bit harder about your sorting algorithm is why functional programming sucks, can I give examples of every bullshit concurrency problem I’ve had in Java as an example of why imperative programming sucks? Persistent data structures are a bit slower but largely become non issues if you deal with concurrency and avoid a lock that you would have otherwise required in C or Java. It’s not like the people who wrote Haskell are idiots; most of these data structures end up sharing a lot of data, and a “new” structure is often only the diffs from the previous version. Not to mention that since you have a compile time guarantee that the data isn’t going to change, you effectively avoid any need for defensive copying. I’m sure you can find some benchmark that proves C++ is faster in the most technical sense, but for network and multithreaded applications, it’s not even close; it’s so much easier to make sure a functional concurrent language is actually correct that the benchmarks become almost irrelevant.
- bjoli 7y ago
  I say this as a die hard FP fan: I agree with your parent comment. I think FP is generally good enough or sometimes even quite close. But I don't know how many times I ended up writing C in Haskell or scheme to make an algorithm really fast (once all other algorithms have been tried or discarded). The quicksort example is a shitty quicksort, because it will be slow as molasses. A proper quicksort in Haskell will degrade you to writing C in Haskell (with the benefits of a large standard library)and then you have lost. C in C will always beat C in Haskell or any other language. Is it a worthwhile tradeoff? I believe so. The few times I am limited by speed in that way are few and far between, and most often it was because I thought something like O(n2) would be good enough which is easily fixable. Sometimes I just need to make optimal code faster. By then I always wish I would be using an imperative language instead.
  - monsieurbanana 7y ago
    Is the level of my English lacking? The comment you're agreeing to clearly seems to argue that fp sucks as a whole because it's not as fast for tight looped algorithms, not that it sucks only for them.
  - 7y ago
lordfoom 7y ago
> Quick sort comes with a steep penalty. Worst case is O(n^(2)). The reason quicksort is good is because it's in place. Once you throw away the in place aspect of quick sort, it's straight up bad. That's why you shuffle the list before you sort it :)
excursionist 7y ago
> It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead. It doesn't silently transform O(1) to O(n), the code is explicitly O(n^2) space worst-case. The only 'silent' transformation that could happen here is an optimization to improve performance. Also, I don't know where you got the 'enormous constant time overhead' part. > Algorithms that are optimal under the mutable data assumption are different than algorithms that are optimal under the constant data assumption. A normal programmer wouldn't be defining writing their own sort functions. A normal Haskell programmer would understand mutability in Haskell. > Performant programming in Haskell requires a much more intimate understanding of the underlying architecture than performant programming in, for instance, C++. It really depends on what you're writing and how much performance you actually need. Implementing a moderate-complexity parallel data processing algorithm in Haskell may result in a slightly slower but much simpler implementation than C++. An implementation of the same complexity in C++ may be slower than Haskell. Writing performant, parallel, safe code for a moderately complex algorithm in C++ is far from easy.
manifestsilence 7y ago
This is why Python uses Timsort: https://en.wikipedia.org/wiki/Timsort https://en.wikipedia.org/wiki/Timsort

kccqzy 7y ago

> It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead. Please tell me what imperative quicksort algorithm has O(1) space. All versions I've seen and could recall use recursion; although each recursive call uses O(1) space, in the worst case of bad pivot element selection each recursive call would only really sort one element resulting in a worst-case O(n) space. Use of randomization would result in a high probability of choosing a good pivot element, but even then you can expect approximately O(log n) space. Also would like to see why you think the Haskell version has enormous constant time overhead. Where do you think this overhead comes from? If you are comparing to an equivalent program in C++ then sure allocations and stuff, but compared with the typical Haskell list-processing programs I don't see any significantly larger overhead.

foota 7y ago
I don't know that I would ever do this, since O(lgn) space is normally trivial, but couldn't you use a RNG that's based on like the depth and start position of a given "stack frame" of a recursion-less quicksort? Like to "recurse" (not actually recurse, but pretend) you would increment depth, the update the start position, and calculate the new partition index based on the (depth, start) tuple? And run that in reverse for going back up the stack. edit: Hah. This is fun. There's a variant where you do tricks with the elements of the array to get constant space. https://link.springer.com/chapter/10.1007/BFb0016252 https://link.springer.com/chapter/10.1007/BFb0016252 The idea is that you partition the elements, but then instead of storing the bounds of the left and right sides, you switch the element from the start of the right side with the partition element of the "stack frame" above you. This later serves as a flag indicating the end of the right side, since the partition of the parent "stack frame" is greater than all elements on the right you know you've hit then end of the right side when you see a larger number than the parent "stack frame"'s pivot.
ivalm 7y ago
For non recursive quicksorts see code at bottom of this link: https://www.geeksforgeeks.org/iterative-quick-sort/ https://www.geeksforgeeks.org/iterative-quick-sort/
- kccqzy 7y ago
  That link basically just simulates recursion by defining a stack in the function. It recognizes that in the recursive version among the stack variables only the two indexes need to be stored so it stores them. It is even less space efficient than the recursive version because it always allocates O(n) space.
scythe 7y ago
The path towards O(1) space instead of O(log n) space is fraught with technicalities. At the bottom, you realize that no matter what algorithm you use, you always store the array size in lg(n) bits! So it makes more sense to say “less memory” rather than O(1) memory for sorts.

brokencode 7y ago

I don’t see how this is a great example of how functional programming sucks. It is easy in any programming language to build a slow sorting algorithm. The fact that you need to use different algorithms with immutable data is irrelevant. You need to use different algorithms for pretty much any type of data structure. Functional programming makes a different set of tradeoffs than imperative programming. You have to work harder to get peak performance, but in many cases it is actually quite performant. Just look at how fast Elm is for web applications, and how that approach allows for a time-traveling debugger and virtually no crashes.

mirekrusin 7y ago

I remember on olympiads one trick that I though was brilliant out-of-the-box thinking was to shuffle input before sorting to avoid worst-case-prepared inputs.

tombert 7y ago

Ok, I’ll bite. If having to think a bit harder about your sorting algorithm is why functional programming sucks, can I give examples of every bullshit concurrency problem I’ve had in Java as an example of why imperative programming sucks? Persistent data structures are a bit slower but largely become non issues if you deal with concurrency and avoid a lock that you would have otherwise required in C or Java. It’s not like the people who wrote Haskell are idiots; most of these data structures end up sharing a lot of data, and a “new” structure is often only the diffs from the previous version. Not to mention that since you have a compile time guarantee that the data isn’t going to change, you effectively avoid any need for defensive copying. I’m sure you can find some benchmark that proves C++ is faster in the most technical sense, but for network and multithreaded applications, it’s not even close; it’s so much easier to make sure a functional concurrent language is actually correct that the benchmarks become almost irrelevant.

bjoli 7y ago
I say this as a die hard FP fan: I agree with your parent comment. I think FP is generally good enough or sometimes even quite close. But I don't know how many times I ended up writing C in Haskell or scheme to make an algorithm really fast (once all other algorithms have been tried or discarded). The quicksort example is a shitty quicksort, because it will be slow as molasses. A proper quicksort in Haskell will degrade you to writing C in Haskell (with the benefits of a large standard library)and then you have lost. C in C will always beat C in Haskell or any other language. Is it a worthwhile tradeoff? I believe so. The few times I am limited by speed in that way are few and far between, and most often it was because I thought something like O(n2) would be good enough which is easily fixable. Sometimes I just need to make optimal code faster. By then I always wish I would be using an imperative language instead.
- monsieurbanana 7y ago
  Is the level of my English lacking? The comment you're agreeing to clearly seems to argue that fp sucks as a whole because it's not as fast for tight looped algorithms, not that it sucks only for them.
- 7y ago

lordfoom 7y ago

> Quick sort comes with a steep penalty. Worst case is O(n^(2)). The reason quicksort is good is because it's in place. Once you throw away the in place aspect of quick sort, it's straight up bad. That's why you shuffle the list before you sort it :)

excursionist 7y ago

> It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead. It doesn't silently transform O(1) to O(n), the code is explicitly O(n^2) space worst-case. The only 'silent' transformation that could happen here is an optimization to improve performance. Also, I don't know where you got the 'enormous constant time overhead' part. > Algorithms that are optimal under the mutable data assumption are different than algorithms that are optimal under the constant data assumption. A normal programmer wouldn't be defining writing their own sort functions. A normal Haskell programmer would understand mutability in Haskell. > Performant programming in Haskell requires a much more intimate understanding of the underlying architecture than performant programming in, for instance, C++. It really depends on what you're writing and how much performance you actually need. Implementing a moderate-complexity parallel data processing algorithm in Haskell may result in a slightly slower but much simpler implementation than C++. An implementation of the same complexity in C++ may be slower than Haskell. Writing performant, parallel, safe code for a moderately complex algorithm in C++ is far from easy.

manifestsilence 7y ago

This is why Python uses Timsort: https://en.wikipedia.org/wiki/Timsort https://en.wikipedia.org/wiki/Timsort