4 ms·

Except in this case, it is not better. His RLE example traverses the sequence twice and creates an intermediate structure. It works find for small examples, bu

by ohyes 16y ago

Except in this case, it is not better. His RLE example traverses the sequence twice and creates an intermediate structure. It works find for small examples, but what happens when you are doing 3x the work on your 1,000,000 item sequence? This could be done just as clearly (possibly more clearly) recursively, traversing the sequence only once, without an intermediate data structure. I am all for functional composition in programming languages, but composition and recursion should be treated as equally fundamental (what is recursion but composing a function with itself, in a certain way, anyway?) Here is a (not heavily tested) tail-recursive common lisp version (no recent clojure version installed here currently). http://paste.lisp.org/display/120383 http://paste.lisp.org/display/120383

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 ago
  Yes 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 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.

by ohyes 16y ago

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 ago
Yes 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 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.