用于在随机加权选择之间进行选择的惯用语

Question

在涉及Clojure时,我完成了一个小例子程序,从一个选择列表中随机选择.

基本思想是迭代选择(分配权重)并将其权重转换为范围,然后在总范围内选择一个随机数来选择一个.它可能不是最优雅的设计,但让我们理所当然.

与下面的例子相比,我会做些什么？

我对整体程序结构建议,名称间距等不感兴趣,主要是在你对每个函数的方法中.

我特别感兴趣的是经验丰富的Clojurer如何处理"增强"功能,我必须使用外部"cur"变量来指代范围的前一端.

  (def colors
      (hash-map 
            :white 1,
            :red 10,
            :blue 20,
            :green 1,
            :yellow 1
       )
     )

    (def color-list (vec colors))

    (def cur 0)

    (defn augment [x] 
      (def name (nth x 0))
      (def val (nth x 1))
      (def newval (+ cur val))
      (def left cur)
      (def right newval)
      (def cur (+ cur val))
      [name left right]
    )

    (def color-list-augmented (map augment color-list))

    (defn within-bounds [bound]
      (def min-bound (nth bound 1))
      (def max-bound (nth bound 2))
      (and (> choice min-bound) (< choice max-bound))
    )

    (def choice (rand-nth (range cur)))

    (def answer 
      (first (filter within-bounds color-list-augmented))
    )

    (println "Random choice:" (nth answer 0))

Answer 1

我建议在学习Clojure时在http://www.4clojure.com/上做一些问题.您可以"关注"顶级用户,看看他们如何解决问题.

这是一个解决方案.它再次不是最有效的,因为我的目标是保持简单,而不是使用您将在稍后学习的更高级的想法和结构.

user=> (def colors {:white 1  :red 10  :blue 20  :green 1  :yellow 1})
#'user/colors
user=> (keys colors)
(:white :red :blue :green :yellow)   
user=> (vals colors)
(1 10 20 1 1)

要将权重转换为间隔,我们只需要累积总和:

user=> (reductions #(+ % %2) (vals colors))
(1 11 31 32 33)

找到随机区间:

user=> (rand-int (last *1))
13
user=> (count (take-while #(<= % *1 ) *2 ))
2

*1REPL中的注意事项是指最近打印的值,*2下一个最近的值等.所以我们要求一个0(包括)和33(不包括)之间的随机整数.这33种可能的选择对应于权重的总和.接下来,我们计算了我们需要通过的间隔数来找到该数字.这里的随机数为13.

(1 11 31 32 33) 
     ^ 13 belongs here, 2 numbers in

我们发现我们的随机数为2英寸.请注意,为了降落在这里,我们必须至少有11但少于31,所以有20种可能性,这正是......的重量...

user=> (nth (keys colors) *1)
:blue

所以,把这一切放在一个函数中:

(defn weighted-rand-choice [m]
    (let [w (reductions #(+ % %2) (vals m))
          r (rand-int (last w))]
         (nth (keys m) (count (take-while #( <= % r ) w)))))

我们来测试一下:

user=> (->> #(weighted-rand-choice colors) repeatedly (take 10000) frequencies)
{:red 3008, :blue 6131, :white 280, :yellow 282, :green 299}

Answer 2

来自ants.clj的 Rich Hickey有点过时(2008)的解决方案:

(defn wrand 
  "given a vector of slice sizes, returns the index of a slice given a
  random spin of a roulette wheel with compartments proportional to
  slices."
  [slices]
  (let [total (reduce + slices)
        r (rand total)]
    (loop [i 0 sum 0]
      (if (< r (+ (slices i) sum))
        i
        (recur (inc i) (+ (slices i) sum))))))

Stuart Halloway最近(2012年)的data.generators解决方案:

(defn weighted
  "Given a map of generators and weights, return a value from one of
  the generators, selecting generator based on weights."
  [m]
  (let [weights   (reductions + (vals m))
        total   (last weights)
        choices (map vector (keys m) weights)]
    (let [choice (uniform 0 total)]
      (loop [[[c w] & more] choices]
        (when w
          (if (< choice w)
            (call-through c)
            (recur more)))))))