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 の 2 つの機能的なバージョンを次に示しますが、ここでのアイデアは、クロージャをサポートするどの言語でも機能するはずです。基本的に、反復の代わりに再帰を使用して同じことを達成し、途中で中断する代わりに値を返し、再帰を停止します。

元の擬似コード:

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

折り畳み（別名Array#reduce、またはアンダースコアの_.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

実行可能な例。

このアルゴリズムは最初のアルゴリズムよりもはるかにアクセスしやすいことがわかりました (そして、中間オブジェクトを作成せず、短絡を行うため、パフォーマンスが向上するはずです)。

更新/補足: 2 番目のアルゴリズムは「純粋」ではありません。これは、渡された関数が参照透過的_.findではないため (外部変数を変更するという副作用があります)、アルゴリズム全体が参照透過的です。関数にカプセル化すると、関数は純粋になり、同じ入力に対して常に同じ出力を返します。これは非常に重要なことです。なぜなら、FP 以外の構造を (パフォーマンス、読みやすさ、または何らかの理由で) 内部で使用しながら、FP の利点を得ることができるからです :DtotalfindItem = (items, r) ->

于 2013-08-10T01:29:25.583 に答える
0

os基になるタスクは、それぞれweightの sで定義された頻度で配列から「イベント」(オブジェクト) をランダムに選択していると思います。このアプローチは、乱数 (一様分布) を階段状累積確率分布関数にマップ (検索) することです。

正の重みを使用すると、それらの累積合計は 0 から 1 に増加します。提供されたコードは、単純に 0 の終わりから検索を開始します。繰り返し呼び出しで速度を最大化するには、事前に合計を計算し、最大の重みが最初になるようにイベントを並べ替えます。

反復 (ループ) で検索するか、再帰で検索するかは、実際には問題ではありません。再帰は、「純粋に機能的」であろうとする言語では優れていますが、根底にある数学的問題の理解には役立ちません。また、タスクをクリーンな関数にパッケージ化するのにも役立ちません。関数は反復をパッケージ化する別のunderscore方法ですが、基本的な機能は変更しません。ターゲットが見つかった場合にのみany、all早期に終了します。

小さなos配列の場合、この単純な検索で十分です。ただし、配列が大きい場合は、バイナリ検索の方が高速になります。調べてみると、この戦略underscoreを使用していることがわかります。（ドロップイン）sortedIndexから、「バイナリ検索を使用して、ソートされた配列のソート順を維持するために、配列に値を挿入する必要がある最小のインデックスを決定します」Lo-Dashunderscore

の基本的な使用法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 }

Jed Clinger の再帰的検索は、coffeescript では次のように記述できます。

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/sortedindexsortedIndexでのテストでは、1000 前後の場合は高速os.lengthですが、長さが 30 に近い場合は単純なループよりも遅くなる ことが 示唆されています。

于 2013-08-09T20:47:53.490 に答える