3 ms·
> Except in this case, it is not better. Clojure's sequence functions are lazy. Observe the following: (def inf (interleave (cycle [1 1 2])
by fogus 16y ago
> Except in this case, it is not better.
Clojure's sequence functions are lazy. Observe the following:
(def inf (interleave (cycle [1 1 2])
(cycle [1 2 2])))
Depending on your REPL settings, if you try to evaluate inf you'll eventually blow your heap. This is clearly an infinite sequence. So by your measure, passing it into rle will be a disaster right?
(take 5 (rle inf))
;;=> ([3 1] [3 2] [3 1] [3 2] [3 1])
The laziness of Clojure guarantees that at no point is the full sequence realized in memory. The sequence is processed once, and only the part of the sequence that we care about is processed.
- ohyes 16y agoYes the sequences are lazy, but that isn't really the point. The 'pack' function is still consing together unnecessary subsequences. The count function also has to iterate across each of these subsequences (assuming they are lists, which they look to be). This can be done much more cleanly in a recursive fashion. When I'm counting consecutive equivalent entries in a list, why wouldn't I just count them and return the results? Sorry fogus, but implementing this in a point free style is horribly inefficient.
- fogus 16y agoThe '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 agoI 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 agoI 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 agoI'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 agoI'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 agoYou 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.
- jamwt 16y agoHaskell 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 agoYou can replace (\x -> (length x, head x)) with (length &&& head) if you import Control.Arrow to make it fully point free