1
\$\begingroup\$

To answer a question on Stack Overflow, I needed to generate a large, nested map that I could postwalk over to do some testing.

After a couple stabs, this is what I came up with. It works by taking a "template map", iterating over it, and randomly changing one of the children of the template via recursion.

While it works, and I'm fairly happy with it, I'd like any advice on how it could be improved. I'm mostly concerned about how prone gen-tree is to Stack Overflows, which necessitated the creation of gen-giant-tree to "brute-force" the problem and find the best of the results. Any advice here especially would be appreciated.

Example usage:

(gen-giant-tree 1000 0.1 {:a 1, :b 2, :c 3, :d 4, :e 5, :f 6})

{:a 1,
 :b 2,
 :c 3,
 :d {:a {:a 1,
         :b 2,
         :c 3,
         :d {:a {:a {:a 1, :b {:a 1, :b 2, :c 3, :d 4, :e 5, :f 6}, :c 3, :d 4, :e 5, :f 6},
                 :b 2,
                 :c 3,
                 :d 4,
                 :e 5,
                 :f {:a {:a 1,
                         :b {:a 1, :b 2, :c 3, :d 4, :e 5, :f 6},
                         :c {:a 1, :b 2, :c 3, :d 4, :e 5, :f 6},
                         :d 4,
                         :e 5,
                         :f 6},
                     :b 2,
                     :c 3,
                     :d 4,
                     :e 5,
                     :f {:a {:a {:a 1,
                                 :b 2,
                                 :c 3,
                                 :d {:a 1, :b 2, :c 3, :d 4, :e 5, :f {:a 1, :b 2, :c 3, :d 4, :e 5, :f 6}},
                                 :e 5,
                                 :f 6},
                             :b {:a 1, :b 2, :c 3, :d 4, :e 5, :f 6},
                             :c 3,
                             :d 4,
                             :e 5,
                             :f 6},
                         :b 2,
                         :c {:a 1,
                             :b 2,
                             :c {:a 1,
                                 :b 2,
                                 :c {:a {:a 1, :b 2, :c 3, :d 4, :e 5, :f 6},
                                     :b 2,
                                     :c 3,
                                     :d 4,
                                     :e 5,
                                     :f {:a 1, :b 2, :c 3, :d 4, :e 5, :f 6}},
                                 :d 4,
                                 :e 5,
                                 :f 6},
                             :d 4,
                             :e {:a 1,
                                 :b 2,
                                 :c 3,
                                 :d {:a {:a 1, :b 2, :c {:a 1, :b 2, :c 3, :d 4, :e 5, :f 6}, :d 4, :e 5, :f 6},
                                     :b 2,
                                     :c 3,
                                     :d 4,
                                     :e 5,
                                     :f 6},
                                 :e 5,
                                 :f 6},
                             :f 6},
                         :d 4,
                         :e 5,
                         :f {:a 1, :b 2, :c 3, :d 4, :e 5, :f 6}}}},
             :b 2,
             :c 3,
             :d 4,
             :e 5,
             :f 6},
         :e 5,
         :f 6},
     :b 2,
     :c 3,
     :d 4,
     :e {:a 1, :b 2, :c 3, :d 4, :e 5, :f {:a 1, :b 2, :c 3, :d 4, :e 5, :f 6}},
     :f 6},
 :e 5,
 :f 6}

The code:

(ns fast-tree-transform.test-data)

(defn random-percent?
  "Returns true percent% of the time."
  [percent]
  (<= (rand) percent))

(defn gen-tree
  "Generates a deeply nested tree by branching from a child of the template chance-of-branch% of the time.
  Very prone to StackOverflows since there is no limitor."
  [chance-of-branch template-map]
  (into {}
    (map (fn [[k :as pair]] (if (random-percent? chance-of-branch)
                              [k (gen-tree chance-of-branch template-map)]
                              pair))
         template-map)))

(defn gen-giant-tree
  "Tries to generate tries number of trees. Throws out any tries that result in a StackOverflow, then returns the 
  result with the longest length when stringified."
  [tries chance-of-branch template-map]
  (->> (repeatedly tries #(try
                            (gen-tree chance-of-branch template-map)

                            (catch StackOverflowError e
                              nil)))
       (filter identity)
       (sort #(compare (count (str %)) (count (str %2))))
       (last)))
\$\endgroup\$
  • \$\begingroup\$ It makes sense in retrospect, but I found, through fairly rigorous testing, that the optimal chance-of-branch is (/ 1 (count template-map)). I'm guessing this is because any more than this causes a StackOverflow since there will on average be more than 1 branch per branch, which will explode. Any less than that would lower the branches/branch beyond what is necessary to avoid SOs. I created a optimal-branch-chance function, and allowed chance-of-branch to default to a call to that function. \$\endgroup\$ – Carcigenicate Apr 17 '18 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.