5 ms·

The 'pack' function is still consing together unnecessary subsequences. No, it's not. The count function also has to iterate across each of thes

by fogus 16y ago

The 'pack' function is still consing together unnecessary subsequences. No, it's not. The count function also has to iterate across each of these subsequences Only the sequences that it sees. This can be done much more cleanly in a recursive fashion. I suppose we have different definitions of clean. implementing this in a point free style is horribly inefficient. Call me unconvinced.

ohyes 16y ago
I wasn't sure if you were just obstinately dismissing my arguments, so I decided to do a benchmark and prove this to you. http://paste.lisp.org/display/120386 http://paste.lisp.org/display/120386 Here is the benchmark. I did two versions in clojure 1.2, the first one uses a transient vector... the second a list. (which it reverses at the end). As you can see, on my machine, the timings for these benchmarks puts the recursive list version approximately 2x faster than your version. edit: annotated paste with more generous timings of composition version. http://paste.lisp.org/display/120386#2 http://paste.lisp.org/display/120386#2 Are you convinced that yours is doing more work now? edit2: I will note, however that neither of mine are fully lazy. I am not a Clojure expert, so I'm not intimately familiar with the laziness abstractions, how would I make these functions use the laziness abstractions? is it even possible?
- dpritchett 16y ago
  I was going to chime in to say that moving from a vector to a recursive reversed list-based implementation for a mere 3x performance gain was a premature optimization at the expense of readability. Then I actually read your code and the two implementations looked nearly identical, so I guess I'll just leave this here. n.b. - I have actually done a bit of Clojure programming myself but the fine points you and Fogus are discussing here are largely over my head, at least juding by the code sample.
- scott_s 16y ago
  I've upmodded this whole discussion because I think it's the kind of thing I love to see on HN, even though my bias is "do the cleaner thing first, optimize later if necessary." But, I just wanted to point out that paste.lisp.org's paren matching is beautiful.
- ohyes 16y ago
  I've added a tail-recursive lazy version. It seems to be about the same amount of a speedup, with the nice addition of less memory use. http://paste.lisp.org/display/120386#3 http://paste.lisp.org/display/120386#3 I thought the 'better performance' of my other versions were specious because data-structure choice often makes a big difference in these sorts of benchmarks. List vs Array vs Lazy-Seq should make a difference. I think this is more definitive, as it produces the (program-flow wise) similar computation to the original. (Not just the same results).
  - fogus 16y ago
    You seem to have reframed the discussion from "horribly inefficient" as defined by extraneous operations, to one of raw speed. I'm certain I've never claimed that a tail-recursive implementation couldn't produce faster times. My statement from the beginning has been that recursion is a low-level operation. I stand by that statement. My combinator post provided 3 useful functions that could prove useful in the future. Your `recle4` implementation does one thing only. If any one of the functions in my combination gains speed, then my implementation will likewise gain speed. This leaves room for optimization without having to dive right into creating a convoluted recursive implementation. I'm pretty sure the words "avoided if at all possible" subsumes the need to optimize if every ounce of speed is required. Raw execution speed is not the only unit of speed that we should consider. We shouldn't sacrifice the speed of the developer or the speed of comprehension just to placate our lizard brains.
    - ohyes 16y ago
      I have not done any reframing whatsoever. You never framed the conversation to begin with. You said, point blank, that composition is better than recursion in functional languages. Better. I called BS. How, exactly, then, do you define 'better'? You didn't give an operational definition of 'better' (which is your responsibility, not mine), so I made up my own. If you don't like it, then be more careful with your claims. It certainly is not 'better' in all meanings of the word. (at least any of those that are clearly defined or measurable for me. In retrospect I see that you were talking about 'style' but 'style' is pretty impossible to measure as it is entirely subjective). .. I wrote a similar function in the same language, and it was twice as fast as yours. Your function, therefore, wastes operations. (At least twice as many, approximately). That isn't a small amount! I'm not even serious about Clojure and my solution seems pretty straightforward. Unless all recursion is rocket science, it is very simple recursion. (Granted I had to RTFM to write it and I suppose a proper name might help, but it would help your implementation too). Why do I need dozens and dozens of ravioli functions that I'm just going to forget that I implemented clutter my name-spaces? Please, for the love of God, at least use a letfn/flet/labels. What is the next developer going to do when I am dead or have retired to my private island? He'll have to learn, not one, but 3 different functions, and know what they do. None of your composed functions are particularly self explanatory. In what way do you think you will get a 2x improvement through the improvement of other functions? I suppose if you write a new compiler for Clojure (perhaps a sufficiently smart one?), it could happen, but you will not get that type of improvement simply by improving the 'pack' function, for example. The way that you are going about collecting the values is fundamentally opposed to efficiency. 'Creating homogeneous groupings then counting the size of those groups' (what you did) is going to be slower than 'counting consecutive same things' (what I did). This isn't really about raw efficiency, this is about a fundamentally broken thought process used to describe the algorithm. That broken thought process is a result of attempting to shoehorn the answer into the realm of functional composition. Anyway, I respectfully disagree.
jamwt 16y ago
Haskell version that is fully lazy, (though not point-free or completely idiomatic). import Data.List (group) rle = map (\x-> (length x, head x)) . group main = print $ rle "aaaabccaadeeee"
- brehaut 16y ago
  You can replace (\x -> (length x, head x)) with (length &&& head) if you import Control.Arrow to make it fully point free
  - eru 16y ago
    And stream fusion should get rid of intermediate data structures.
  - jamwt 16y ago
    Good idea re: Arrows, and we can go all out as long as we're using them. :-) rle = group >>> map (length &&& head)

by fogus 16y ago

ohyes 16y ago

I wasn't sure if you were just obstinately dismissing my arguments, so I decided to do a benchmark and prove this to you. http://paste.lisp.org/display/120386 http://paste.lisp.org/display/120386 Here is the benchmark. I did two versions in clojure 1.2, the first one uses a transient vector... the second a list. (which it reverses at the end). As you can see, on my machine, the timings for these benchmarks puts the recursive list version approximately 2x faster than your version. edit: annotated paste with more generous timings of composition version. http://paste.lisp.org/display/120386#2 http://paste.lisp.org/display/120386#2 Are you convinced that yours is doing more work now? edit2: I will note, however that neither of mine are fully lazy. I am not a Clojure expert, so I'm not intimately familiar with the laziness abstractions, how would I make these functions use the laziness abstractions? is it even possible?

dpritchett 16y ago
I was going to chime in to say that moving from a vector to a recursive reversed list-based implementation for a mere 3x performance gain was a premature optimization at the expense of readability. Then I actually read your code and the two implementations looked nearly identical, so I guess I'll just leave this here. n.b. - I have actually done a bit of Clojure programming myself but the fine points you and Fogus are discussing here are largely over my head, at least juding by the code sample.
scott_s 16y ago
I've upmodded this whole discussion because I think it's the kind of thing I love to see on HN, even though my bias is "do the cleaner thing first, optimize later if necessary." But, I just wanted to point out that paste.lisp.org's paren matching is beautiful.
ohyes 16y ago
I've added a tail-recursive lazy version. It seems to be about the same amount of a speedup, with the nice addition of less memory use. http://paste.lisp.org/display/120386#3 http://paste.lisp.org/display/120386#3 I thought the 'better performance' of my other versions were specious because data-structure choice often makes a big difference in these sorts of benchmarks. List vs Array vs Lazy-Seq should make a difference. I think this is more definitive, as it produces the (program-flow wise) similar computation to the original. (Not just the same results).
- fogus 16y ago
  You seem to have reframed the discussion from "horribly inefficient" as defined by extraneous operations, to one of raw speed. I'm certain I've never claimed that a tail-recursive implementation couldn't produce faster times. My statement from the beginning has been that recursion is a low-level operation. I stand by that statement. My combinator post provided 3 useful functions that could prove useful in the future. Your `recle4` implementation does one thing only. If any one of the functions in my combination gains speed, then my implementation will likewise gain speed. This leaves room for optimization without having to dive right into creating a convoluted recursive implementation. I'm pretty sure the words "avoided if at all possible" subsumes the need to optimize if every ounce of speed is required. Raw execution speed is not the only unit of speed that we should consider. We shouldn't sacrifice the speed of the developer or the speed of comprehension just to placate our lizard brains.
  - ohyes 16y ago
    I have not done any reframing whatsoever. You never framed the conversation to begin with. You said, point blank, that composition is better than recursion in functional languages. Better. I called BS. How, exactly, then, do you define 'better'? You didn't give an operational definition of 'better' (which is your responsibility, not mine), so I made up my own. If you don't like it, then be more careful with your claims. It certainly is not 'better' in all meanings of the word. (at least any of those that are clearly defined or measurable for me. In retrospect I see that you were talking about 'style' but 'style' is pretty impossible to measure as it is entirely subjective). .. I wrote a similar function in the same language, and it was twice as fast as yours. Your function, therefore, wastes operations. (At least twice as many, approximately). That isn't a small amount! I'm not even serious about Clojure and my solution seems pretty straightforward. Unless all recursion is rocket science, it is very simple recursion. (Granted I had to RTFM to write it and I suppose a proper name might help, but it would help your implementation too). Why do I need dozens and dozens of ravioli functions that I'm just going to forget that I implemented clutter my name-spaces? Please, for the love of God, at least use a letfn/flet/labels. What is the next developer going to do when I am dead or have retired to my private island? He'll have to learn, not one, but 3 different functions, and know what they do. None of your composed functions are particularly self explanatory. In what way do you think you will get a 2x improvement through the improvement of other functions? I suppose if you write a new compiler for Clojure (perhaps a sufficiently smart one?), it could happen, but you will not get that type of improvement simply by improving the 'pack' function, for example. The way that you are going about collecting the values is fundamentally opposed to efficiency. 'Creating homogeneous groupings then counting the size of those groups' (what you did) is going to be slower than 'counting consecutive same things' (what I did). This isn't really about raw efficiency, this is about a fundamentally broken thought process used to describe the algorithm. That broken thought process is a result of attempting to shoehorn the answer into the realm of functional composition. Anyway, I respectfully disagree.

jamwt 16y ago

Haskell version that is fully lazy, (though not point-free or completely idiomatic). import Data.List (group) rle = map (\x-> (length x, head x)) . group main = print $ rle "aaaabccaadeeee"

brehaut 16y ago
You can replace (\x -> (length x, head x)) with (length &&& head) if you import Control.Arrow to make it fully point free
- eru 16y ago
  And stream fusion should get rid of intermediate data structures.
- jamwt 16y ago
  Good idea re: Arrows, and we can go all out as long as we're using them. :-) rle = group >>> map (length &&& head)