News for hackers. Stuff that matters.
Re:Turn O(n^2) reverse into O(n) by tibbon on Sunday December 15, 2013 @10:19PM (#6912584)
My Haskell skills still are growing. Can someone explain?
Re:Turn O(n^2) reverse into O(n) by seliopou on Sunday December 15, 2013 @10:23PM (#6912610)
The original line was something like this:

  acc = "";
  for (var i = 0; i < strings.length; i++) {
      acc += strings[i]
  }
The new version is something like this:

  strings.join("")
The second version can pre-allocate a string and copy characters into that string under the hood. The first version has to allocate a new string and recopy the characters on every iteration.
Re:Turn O(n^2) reverse into O(n) by tmoertel on Sunday December 15, 2013 @11:03PM (#6912785)
Even if the buffers were vanilla Strings, and there were no pre-allocation, the patch would still have fixed the quadratic-runtime problem. Consider that, for vanilla Strings, the buffer ops are implemented like so:

    buf_append bufOps = (++)
    buf_concat bufOps = concat
Since (++) has a running time that's linear in the length of its left argument, you want to treat it as a right-associative operator to prevent quadratic runtime when joining a bunch of strings.

But, going back to the patch in question, the original code was effectively this:

    foldr (flip (++)) [] strs
Since flip had been applied to (++), the resulting operator you now want to treat as left associative to avoid quadratic blow-up. The code, however, uses the right-associative fold, foldr, to join the list of strings str.

The patch fixes this problem by replacing the code with the equivalent code

    concat (reverse strs)
And how is concat defined in the libraries? Looking at the source [1], it's

    concat = foldr (++) []
Thus the fix is basically

    foldr (++) [] (reverse strs).
This version reverses strs, at linear-time cost, to be able to apply the normal, unflipped (++) with a right-associative fold and thus avoid the dreaded quadratic blow-up.

[1] http://hackage.haskell.org/package/base-4.6.0.1/docs/src/GHC...

EDITED TO ADD: Also, if you knew the buffers were vanilla Strings, you could even eliminate the reverse overhead since

    foldr op z xs == foldl (flip op) z (reverse xs)
for all finite lists xs. Thus you could flip (++) and use foldl instead of foldr to get an efficient implementation like this:

    foldl (flip (++)) [] strs
Re:Turn O(n^2) reverse into O(n) by djipko on Monday December 16, 2013 @04:11AM (#6913622)
Nice explanation. I'm surprised that no one so far mentioned a cool trick for getting around this using a different way to define mappend as function composition, to make sure ++ is applied in the right order, since it's from LYAH (scroll to end of the linked chapter):

http://learnyouahaskell.com/for-a-few-monads-more#writer

Re:Turn O(n^2) reverse into O(n) by fekberg on Sunday December 15, 2013 @10:39PM (#6912669)
I recall when I studied algorithms and data structures, but just swapping to using references/pointers instead of copying memory, I could speed up my algorithms ridiculously. Correct me if I am wrong. "Small" things like these (as we just saw) can be really beneficial!
Re:Turn O(n^2) reverse into O(n) by eru on Sunday December 15, 2013 @10:51PM (#6912739)
As an aside, immutability (ie purity) in Haskell allows refercences everywhere, and thus less copying. (They call it `sharing' in Haskell land.)
Re:Turn O(n^2) reverse into O(n) by yongjik on Monday December 16, 2013 @01:59PM (#6916981)
I wonder if there's something different about Haskell that makes "less copying" more attractive?

In the C++ world, libstdc++ strings have copy-on-write semantics, which (as far as I heard) turned out to be terrible because you have to do reference counting instead, and with multithreading it requires atomic operations, which is slower than copying for small strings.

Re:Turn O(n^2) reverse into O(n) by thinkpad20 on Sunday December 15, 2013 @11:00PM (#6912775)
It's worth noting, though, that immutability doesn't always mean less copying. Immutable arrays, where the entire array must be copied with the change of one element, are an example of that. And by extension, hash tables, etc. Of course there are lots of tricks that can be employed to get around this, to a degree.
Re:Turn O(n^2) reverse into O(n) by coolsunglasses on Sunday December 15, 2013 @11:13PM (#6912828)
>Immutable arrays, where the entire array must be copied with the change of one element, are an example of that

That is not how modern persistent data structures are implemented. Please do not talk about immutability as if it necessarily means having a naive implementation like this.

Re:Turn O(n^2) reverse into O(n) by thinkpad20 on Monday December 16, 2013 @01:34AM (#6913233)
Like I said there are tricks to get around it. I was referring to a C-style array. I think it's still accurate to say that immutability does not always mean less copying.
Re:Turn O(n^2) reverse into O(n) by coolsunglasses on Monday December 16, 2013 @02:04AM (#6913302)
"tricks to get around it" if by that you mean non-naive data structures that you're supposed to use in order to make immutability efficient yes.

Egregious mischaracterization.

Said "tricks" are an entire branch of research in CS.

Re:Turn O(n^2) reverse into O(n) by graue on Monday December 16, 2013 @04:18AM (#6913644)
As a fellow Clojurist, I agree with the substance of what you're saying here but wish you could express it in a more friendly manner. Both your comments essentially say "you're wrong" without educating or adding value. I don't feel that reflects well on the Clojure community, and I'd like us to do better.
Re:Turn O(n^2) reverse into O(n) by thinkpad20 on Monday December 16, 2013 @01:24PM (#6916674)
Your tone suggests that you think I don't understand what you're saying (which perhaps I wouldn't, since you succeeded only in telling me I was wrong and failed to actually explain "how modern persistent data structures are implemented" -- as if they were all implemented the same way). Your last sentence suggests that you don't think I know that efficient immutable data structures are an active area of computer science research. Both assumptions are incorrect.

Now, I realize that in my original post, I might have given the wrong impression. I thought that by my second post I was being clear enough, but perhaps I wasn't. Let's try take three:

Immutable data structures do not necessarily guarantee less copying, or necessarily imply a performance gain. A data structure which does not lend itself well to immutability, such as a C-style array, can lead to very inefficient code when used in an immutable fashion. The C-style array or a variation thereof is also the default in most current languages, including Java, Python, C++, Ruby, and many others, so this is hardly a thing of the past. It's important to be aware of the performance characteristics of the data structures one is using, respective to the way in which they are used.

Re:Turn O(n^2) reverse into O(n) by PeterisP on Monday December 16, 2013 @04:57AM (#6913789)
No, you'd have to resort to tricks in order to have a C-style array and encounter this problem; if you just use the default stuff, you get data structures that work great with immutability.
Re:Turn O(n^2) reverse into O(n) by graue on Sunday December 15, 2013 @11:54PM (#6912983)
> Immutable arrays, where the entire array must be copied with the change of one element, are an example of that.

Only in a naive implementation. Clojure, for example, has a persistent vector that only requires O(log32 n) copying, which grows so slowly as to be effectively O(1).

See: http://hypirion.com/musings/understanding-persistent-vector-...

Re:Turn O(n^2) reverse into O(n) by eru on Sunday December 15, 2013 @11:13PM (#6912826)
Yes. The right data structure for the right job.

If your array only has one future---ie there are no references to the unchanged array around---you can re-use the old array. That means you get to mutate in place but still pretend you have immutability.

Re:Turn O(n^2) reverse into O(n) by dmak on Sunday December 15, 2013 @10:51PM (#6912738)
How is the original (the for loop that you mentioned) O(n^2)? Isn't that O(n)? Isn't acc += strings[i] a O(1) operation?
Re:Turn O(n^2) reverse into O(n) by alok-g on Sunday December 15, 2013 @11:01PM (#6912779)
Each time strings[i] is added to acc, it may require reallocating entire acc to new memory location with more memory for the concatenated string.
Re:Turn O(n^2) reverse into O(n) by masklinn on Monday December 16, 2013 @02:07AM (#6913318)
`acc` is assumed immutable, so it has to be copied entirely on each concatenation. Copying a string is an O(n) operation.
Re:Turn O(n^2) reverse into O(n) by MBCook on Sunday December 15, 2013 @11:06PM (#6912797)
But strings.length is O(n), and you have to run it n times.
Re:Turn O(n^2) reverse into O(n) by comex on Sunday December 15, 2013 @11:11PM (#6912819)
No, it is not.
Re:Turn O(n^2) reverse into O(n) by jefffoster on Monday December 16, 2013 @03:38AM (#6913539)
With the naive representation of a string as a list of characters [Char], it is. The only way to get to the end of the list is to recursively take the tail of the string (see the source at http://hackage.haskell.org/package/base-4.6.0.1/docs/src/GHC...).

There's alternative representations with different trade offs, such as Data.Text

Re:Turn O(n^2) reverse into O(n) by comex on Monday December 16, 2013 @12:33PM (#6916296)
Heh... but I was referring to the example seliopou gave, which appears to be in JavaScript, and strings is [String] rather than [Char]. I think the analogy might cause more confusion than clarification.
Re:Turn O(n^2) reverse into O(n) by 10098 on Sunday December 15, 2013 @10:58PM (#6912763)
not if you have to reallocate space for storing acc on each iteration
Re:Turn O(n^2) reverse into O(n) by auggierose on Sunday December 15, 2013 @10:49PM (#6912725)
It is a standard mistake that people sometimes make when working with lists. Lists have a O(1) complexity of prepending an element, and O(n) complexity of appending an element. So when you have to append a bunch of elements to a list, it is better to reverse the list, prepend the elements, and then reverse the list again, instead of just appending all elements. The former approach has linear complexity, the latter quadratic.
Re:Turn O(n^2) reverse into O(n) by aidenn0 on Sunday December 15, 2013 @11:30PM (#6912891)
Lists don't have O(n) complexity of appending an element, if you keep track of the tail element.
Re:Turn O(n^2) reverse into O(n) by verbin217 on Sunday December 15, 2013 @11:54PM (#6912984)
I assume you're talking about lists with mutable pointers. I don't think that's what they're talking about here. Functional (persistent) lists are immutable. You can add elements only by creating a new data structure, similar to a linked list node, that will hold immutable references to the existing list and the new element. By convention the element is considered to be in front of the list. Hence prepending is rather easy (constant time) while appending requires rebuilding the whole list (linear time).
Re:Turn O(n^2) reverse into O(n) by danieldk on Monday December 16, 2013 @01:47AM (#6913264)
I assume you're talking about lists with mutable pointers. I don't think that's what they're talking about here. Functional (persistent) lists are immutable. [...] Hence prepending is rather easy (constant time) while appending requires rebuilding the whole list (linear time).

You can append in O(1) time using difference lists. They don't have all the niceties of Prolog difference lists, but they are still great if you only have to append:

http://hackage.haskell.org/package/dlist

Re:Turn O(n^2) reverse into O(n) by mhogomchungu on Sunday December 15, 2013 @11:19PM (#6912848)
A list manager with a pointer to the last element on the list should also be able to append to the managed list in O(1)
Re:Turn O(n^2) reverse into O(n) by auggierose on Sunday December 15, 2013 @11:22PM (#6912856)
That does not work if your list is persistent.