4

我在 SO 上找到了一个答案，解释了如何为游戏编写一个随机加权的掉落系统。我更愿意以更具功能性的编程风格编写这段代码，但我无法为这段代码找到一种方法。我将在这里内联伪代码：

R = (some random int); 
T = 0; 
for o in os 
    T = T + o.weight; 
    if T > R 
        return o;

这怎么能写成更实用的风格呢？我正在使用 CoffeeScript 和 underscore.js，但我更希望这个答案与语言无关，因为我在以功能方式 思考这个问题时遇到了麻烦。

4

3 回答 3

3

这是 Clojure 和 JavaScript 中的另外两个功能版本，但这里的想法应该适用于任何支持闭包的语言。基本上，我们使用递归而不是迭代来完成同样的事情，而不是在中间中断，我们只是返回一个值并停止递归。

原始伪代码：

R = (some random int); 
T = 0; 
for o in os 
    T = T + o.weight; 
    if T > R 
        return o;

Clojure 版本（对象仅被视为 clojure 映射）：

(defn recursive-version
  [r objects]
  (loop [t 0
         others objects]
    (let [obj (first others)
          new_t (+ t (:weight obj))]
      (if (> new_t r)
        obj
        (recur new_t (rest others))))))

JavaScript 版本（为方便起见使用下划线）。小心，因为这可能会炸毁堆栈。这在概念上与 clojure 版本相同。

var js_recursive_version = function(objects, r) {
    var main_helper = function(t, others) {
        var obj = _.first(others);
        var new_t = t + obj.weight;
        if (new_t > r) {
          return obj;
        } else {
          return main_helper(new_t, _.rest(others));
        }
    };


    return main_helper(0, objects);
};
于 2013-08-09T18:43:06.550 回答
2

您可以使用折叠（akaArray#reduce或 Underscore's _.reduce）来实现这一点：

SSCCE：

items = [
  {item: 'foo', weight: 50}
  {item: 'bar', weight: 35}
  {item: 'baz', weight: 15}
]

r = Math.random() * 100

{item} = items.reduce (memo, {item, weight}) ->
  if memo.sum > r
    memo
  else
    {item, sum: memo.sum + weight}
, {sum: 0}

console.log 'r:', r, 'item:', item

您可以在 coffeescript.org 上多次运行它，然后查看结果是否有意义 :)

话虽如此，我发现折叠有点做作，因为您必须记住所选项目和迭代之间的累积权重，并且在找到项目时它不会短路。

也许可以考虑纯 FP 和重新实现查找算法的乏味之间的折衷解决方案（使用_.find）：

total = 0
{item} = _.find items, ({weight}) ->
  total += weight
  total > r

可运行的例子。

我发现（不是双关语）这个算法比第一个算法更容易访问（它应该表现得更好，因为它不会创建中间对象，并且会短路）。

更新/旁注：第二种算法不是“纯”的，因为传递给的函数_.find不是引用透明total的（它具有修改外部变量的副作用），但整个算法是引用透明的。如果您将其封装在一个findItem = (items, r) ->函数中，该函数将是纯函数，并且始终为相同的输入返回相同的输出。这是一件非常重要的事情，因为这意味着您可以在使用一些非 FP 构造（出于性能、可读性或其他原因）的同时获得 FP 的好处：D

于 2013-08-10T01:29:25.583 回答
0

我认为基本任务是从数组中随机选择“事件”（对象）os，其频率由它们各自weight的 s 定义。该方法是将随机数（具有均匀分布）映射（即搜索）到阶梯累积概率分布函数上。

使用正权重，它们的累积和从 0 增加到 1。您给我们的代码只是从 0 端开始搜索。为了最大限度地提高重复调用的速度，预先计算总和，并对事件进行排序，以便最大的权重在前。

无论您使用迭代（循环）还是递归进行搜索都无关紧要。递归在试图“纯函数式”但无助于理解潜在数学问题的语言中很好。它并不能帮助您将任务打包成一个干净的函数。函数是打包迭代的underscore另一种方式，但不会更改基本功能。只有在找到目标时才any提前all退出。

对于小os数组，这个简单的搜索就足够了。但是对于大数组，二分查找会更快。看着underscore我发现sortedIndex使用这种策略。从Lo-Dash（一个underscoredropin），“使用二分搜索来确定应该将值插入数组的最小索引，以保持排序数组的排序顺序”

的基本用途sortedIndex是：

os = [{name:'one',weight:.7},
      {name:'two',weight:.25},
      {name:'three',weight:.05}]
t=0; cumweights = (t+=o.weight for o in os)
i = _.sortedIndex(cumweights, R)
os[i]

您可以使用嵌套函数隐藏累积和计算，例如：

osEventGen = (os)->
  t=0; xw = (t+=y.weight for y in os)
  return (R) ->
    i = __.sortedIndex(xw, R)
    return os[i]
osEvent = osEventGen(os)
osEvent(.3)
# { name: 'one', weight: 0.7 }
osEvent(.8)
# { name: 'two', weight: 0.25 }
osEvent(.99)
# { name: 'three', weight: 0.05 }

在 coffeescript 中，Jed Clinger 的递归搜索可以这样写：

foo = (x, r, t=0)->
  [y, x...] = x
  t += y
  return [y, t] if x.length==0 or t>r
  return foo(x, r, t)

使用相同基本思想的循环版本是：

foo=(x,r)->
  t=0
  while x.length and t<=r
    [y,x...]=x  # the [first, rest] split
    t+=y
    y

对 jsPerf http://jsperf.com/sortedindex的测试 表明，在 1000 左右sortedIndex时更快os.length，但在长度更像 30 时比简单循环慢。

于 2013-08-09T20:47:53.490 回答