Fork me on GitHub
Eric Ihli20:06:55

Quick contract bounty for anyone interested. (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.)

Eric Ihli20:06:33

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%


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

Eric Ihli20:06:52

The order does not matter.

Eric Ihli20:06:42

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

[ ( [1] [2] )
  ( [1 2]   ) ]
is as good as
[ ( [1 2] )
  ( [1] [2] ) ]
But the order of the inner combinations does matter. [2 1] would not be ok in the above example.


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)]
      (zero? n) '(())

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

      (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))
                (map (fn [lst] (cons (cons one-elem (first lst)) (rest lst)))

👏 4

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.

Eric Ihli21:06:10

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:

❤️ 28

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

Eric Ihli22:06:47

Thy bounty be done. Thanks again.


@UJP37GW2K if you get submissions with further improvements, I hope you'll post them in this thread; I don't have time to play with this myself, but it'd be fun to see what people come up with 😄


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.