Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Since there are a few <strong>misconceptions</strong> flying around here, I’d like to clarify some points.</p> <ul> <li><p>The “in-place” quicksort isn’t really in-place (and quicksort is <em>not</em> by definition in-place). It requires additional storage in the form of stack space for the recursive step, which is in the order of <em>O</em>(log <em>n</em>) in the best case, but <em>O</em>(<i>n</i>) in the worst case.</p></li> <li><p>Implementing a functional variant of quicksort that operates on arrays defeats the purpose. Arrays are never immutable.</p></li> <li><p>The “proper” functional implementation of quicksort uses immutable lists. It is of course not in-place but it’s got the same worst-case asymptotic runtime (<em>O</em>(<i>n</i>^2)) and space complexity (<em>O</em>(<i>n</i>)) as the procedural in-place version.</p> <p>On average, its running time is <em>still</em> on par with that of the in-place variant (<em>O</em>(<i>n</i> log <em>n</em>)). Its space complexity, however, is still <em>O</em>(<i>n</i>).</p></li> </ul> <hr> <p>There are <em>two obvious disadvantages</em> of a functional quicksort implementation. In the following, let’s consider this reference implementation in Haskell (I don’t know Scala …) from the <a href="http://www.haskell.org/haskellwiki/Introduction" rel="noreferrer">Haskell introduction</a>:</p> <pre><code>qsort [] = [] qsort (x:xs) = qsort lesser ++ [x] ++ qsort greater where lesser = (filter (&lt; x) xs) greater = (filter (&gt;= x) xs) </code></pre> <ol> <li><p>The first disadvantage is <em>the choice of the pivot element</em>, which is very inflexible. The strength of modern quicksort implementations relies heavily on a smart choice of the pivot (compare <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8162" rel="noreferrer">“Engineering a sort function” by Bentley <em>et al.</em></a>). The above algorithm is poor in that regard, which degrades average performance considerably.</p></li> <li><p>Secondly, this algorithm uses <em>list concatenation</em> (instead of list construction) which is an <em>O</em>(<i>n</i>) operation. This doesn’t impact on the asymptotic complexity but it’s a measurable factor.</p></li> </ol> <p>A third disadvantage is somewhat hidden: unlike the “in-place” variant, this implementation <em>continually requests memory from the heap</em> for the cons cells of the list and potentially scatters memory all over the place. As a result, this algorithm has a very <em>poor cache locality</em>. I don’t know whether smart allocators in modern functional programming languages can mitigate this – but on modern machines, cache misses have become a major performance killer.</p> <hr> <p><strong>What’s the conclusion?</strong> Unlike others, I wouldn’t say that quicksort is inherently imperative and that’s why it performs badly in an FP environment. Quite on the contrary, I would argue that quicksort is a perfect example of a functional algorithm: it translates seamlessly into an immutable environment, its asymptotic running time and space complexity are on par with the procedural implementation, and even its procedural implementation employs recursion.</p> <p>But this algorithm <em>still</em> performs worse when constrained to an immutable domain. The reason for this is that the algorithm has the peculiar property of benefitting from a lot of (sometimes low-level) fine-tuning that can only be efficiently performed on arrays. A naive description of the quicksort misses all these intricacies (both in the functional and in the procedural variant).</p> <p>After reading “Engineering a sort function” I can no longer consider quicksort an elegant algorithm. Implemented efficiently, it is a clunky mess, an engineer’s piece of work, not an artist’s (not to devalue engineering! this has its own aesthetic).</p> <hr> <p>But I would also like to point out that this point is particular to quicksort. Not every algorithm is amenable to the same sort of low-level tweaking. A lot of algorithms and data structures really <em>can</em> be expressed without performance loss in an immutable environment.</p> <p>And immutability can even <em>decrease</em> performance costs by removing the need of costly copies or cross-thread synchronizations.</p> <p>So, to answer the original question, “<strong>is immutability expensive?</strong>” – In the particular case of quicksort, there is a cost that is indeed a result of immutability. But in general, <strong>no</strong>.</p>
    singulars
    1. This table or related slice is empty.
    1. POFunctional programming - is immutability expensive?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USKonrad Rudolph
    1. USKonrad Rudolph
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POFunctional programming - is immutability expensive?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO+1 - great answer! Although I would personally have ended with _sometimes_ rather than _no_. Still, that's just personality--you've explained the issues very well.
      singulars
      1. PO
      1. USRex Kerr
    2. COYou should add that a proper implementation using immutable values is immediately parallelisable as opposed to imperative versions. In modern technological context, this becomes more and more important.
      singulars
      1. PO
      1. USRaphael
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload