Clojurians Log v2

Quick contract bounty for anyone interested. https://pastebin.com/advYsru8 (It's only ~50 lines of code. A type of combination generator.) That comment at the end runs ~25 seconds on my 4-core Thinkpad Carbon. $25 for every 5 second (~20 percentage point) speed increase. Leave a comment if you start working on it so multiple people don't spend time. Only paying the first. (But if someone has a 25% suggestion and another person has a 50% suggestion later, $25 to each of you.)

2 sample runs:

pId                                                           nCalls        Min      50% ≤      90% ≤      95% ≤      99% ≤        Max       Mean   MAD      Clock  Total

:ezmonic.combination-generator/defn_merge-and-join_2       4,194,304    99.00ns     3.42μs     4.78μs     5.51μs     6.96μs   523.56ms     4.55μs  ±45%    19.10s     77%
:ezmonic.combination-generator/defn_-merge_2               4,194,303   489.00ns     2.48μs     3.57μs     4.14μs     5.28μs   170.38ms     2.85μs  ±27%    11.96s     48%
:tufte/compaction                                                 10   156.28ms   191.06ms   367.37ms   523.54ms   523.54ms   523.54ms   253.38ms  ±38%     2.53s     10%
:ezmonic.combination-generator/defn_combination-generator          1   251.19μs   251.19μs   251.19μs   251.19μs   251.19μs   251.19μs   251.19μs   ±0%   251.19μs     0%

Accounted                                                                                                                                                  33.59s    136%
Clock                                                                                                                                                      24.77s    100%


pId                                                           nCalls        Min      50% ≤      90% ≤      95% ≤      99% ≤        Max       Mean   MAD      Clock  Total

:ezmonic.combination-generator/defn_merge-and-join_2       4,194,304   117.00ns     3.41μs     5.00μs     5.76μs     7.02μs   382.44ms     4.73μs  ±50%    19.85s     78%
:ezmonic.combination-generator/defn_-merge_2               4,194,303   646.00ns     2.48μs     3.70μs     4.28μs     5.37μs   181.27ms     3.11μs  ±38%    13.06s     51%
:tufte/compaction                                                 10   141.32ms   157.05ms   378.63ms   382.43ms   382.43ms   382.43ms   220.94ms  ±41%     2.21s      9%
:ezmonic.combination-generator/defn_combination-generator          1   350.24μs   350.24μs   350.24μs   350.24μs   350.24μs   350.24μs   350.24μs   ±0%   350.24μs     0%

Accounted                                                                                                                                                  35.12s    138%
Clock                                                                                                                                                      25.54s    100%

I may tinker with it for a bit to see what the performance results are for your code, versus an implementation that uses the core.rrb-vector library, but I won't be surprised if core.rrb-vector is even slower, if most of the lists/vectors involved are "short" (e.g. 100 elements or less).

FYI, my tinkering is mostly for my own curiosity on the performance of this problem and whether that library might help. I don't plan on claiming the bounty, so if anyone else wants it, go for it.

Does the particular order of lists returned by combination-generator matter to you? Or is any order just as useful to you?

The order does not matter.

To clarify, the order of the overall list doesn't matter. But each inner grouping, order does matter.

[ ( [1] [2] )
  ( [1 2]   ) ]

[ ( [1 2] )
  ( [1] [2] ) ]

understood

I've got something that on my laptop at least takes 1/3 of the time for the size 23 case

It just uses built-in Clojure operations, without the rrb-vector library

(defn combination-gen2 [xs]
  (let [n (bounded-count 2 xs)]
    (cond
      (zero? n) '(())

      (= n 1)
      (list (list xs))

      :else
      (let [one-elem (first xs)
            list-of-one-elem-only (list one-elem)
            sub-solution (combination-gen2 (rest xs))]
        (concat (map (fn [lst] (cons list-of-one-elem-only lst))
                     sub-solution)
                (map (fn [lst] (cons (cons one-elem (first lst)) (rest lst)))
                     sub-solution))))))

Basically it restricts itself to doing on lists what is fast: accessing only the beginning of the list, and prepending elements to the front.

It could be made more clean for reading and understanding purposes, a bit.

That's excellent. Thanks! I know you said you didn't plan on claiming the bounty. But I have to do something with it. If you change your mind, message me your Venmo or Paypal. Or if you'd rather, give me a patreon or github repo that you want to support and I'll send it straight there.

If you are interested in supporting Cognitect development at $3/month for however long interests your, you can get access to their REBL software, and support whatever they use that money for: https://www.patreon.com/cognitect

Cognitect = Rich Hickey, Stuart Halloway, Alex Miller, and a bunch of other people who use and enhance Clojure

Thy bounty be done. Thanks again.