겸손하고 포부가 있는 초보 개발자의 확률적 사고 지침일련의 포효와 이상한 생각.

defmodule DungeonCrawl.Room do
  @moduledoc """
  data structure representing a "room"
  a room has "actions" borrowed
  """
  alias DungeonCrawl.Room, as: Room
  alias DungeonCrawl.Room.Triggers, as: Triggers
  import DungeonCrawl.Room.Action

  defstruct name: nil, description: nil, actions: [], trigger: nil, probability: nil

  def all,
    do: [
      %Room{
        name: :exit,
        description: "You can see a small light from a crack in the walls",
        actions: [forward()],
        trigger: Triggers.Exit,
        probability: [:exit]
      },
    %Room{
        name: :goblin,
        description: "You can see an enemy blocking your path",
        actions: [forward()],
        trigger: Triggers.Enemy,
        probability: [:goblin, :goblin, :goblin, :goblin, :goblin]
      },
    %Room{
        name: :ogre,
        description: "Something moves around in the dark, what do you do?",
        actions: [forward()],
        trigger: Triggers.Enemy,
        probability: [:ogre, :ogre, :ogre]
      },
    ]
end

 defp bias_probability(rooms) do
    rooms
    |> Enum.map(fn room -> room.probability end)
    |> Enum.reduce(fn room, acc -> room ++ acc end)
    |> Enum.random()
  end

    rooms
    |> Enum.find(fn room -> room.name == bias_probability(rooms) end)

확률은 불공평해!

선형 스캐닝 O(kay)법

import random

def weighted_random(weights):
    """
    INPUT probabilities - [0.2, 0.3, 0.5]
    OUTPUT index of random_weight - [0, 1, 2]
    """
    remaining_distance = random.random() * sum(weights)
    # probability distribution sample size * random integer
    for (i, weight) in enumerate(weights):
        # [{0, 0.2}, {1, 0.3}, {2, 0.5}]
        remaining_distance -= weights[i]
        #print("debug", remaining_distance)
        if remaining_distance < 0:
            return i

# Repeat the experiment to observe bias factor
for e in range(10):
  print(f"exp trial{e}",weighted_random([0.2, 0.3, 0.5]))

defmodule Prob do
  def bias_probability(weights) do
    # [i[0] P=0.2, i[1] P=0.5 , i[2] P=0.3] s.s = 3
    # P(n) = distribution sample len bias * random() - P[i] < 0
    len = Enum.count(weights)
    # could increase range for greater float precision as you like
    distance = Enum.random(1..99)/100 * Enum.sum(weights)
    # bias factor
    enumerated_list = Enum.zip(0..len, weights)

    Enum.reduce_while(enumerated_list, distance, fn (_weight = {i, w}, acc) ->
      if (acc - w) > 0, do: {:cont, acc - w}, else: {:halt, i}
    end)
  end
end

IO.inspect Prob.bias_probability([0.2, 0.3, 0.5])

    rooms
    |> Enum.map(fn room -> room.probability end)
    |> Enum.fetch(bias_probability(rooms))

Aliasing(Vose) the O yes! method

def prepare_aliased_randomizer(weights):
    N = len(weights) # limit
    avg = sum(weights)/N # alias partition

    aliases = [(1, None)] * N
    # [(1, None), (1, None), (1, None)] --> alias table

    # Bucketting (pseudo quick sort like behaviour*)
    # weight/avg < | > avg
    # smalls are partial alias fits
    # bigs fits and remainder thrown to smalls

    smalls = ((i, w/avg) for (i, w) in enumerate(weights) if w < avg)
    bigs = ((i, w/avg) for (i, w) in enumerate(weights) if w >= avg)

    # [(0, 0.6), (1, 0.9)] --> small weight avgs
    # [(2, 1.5)] --> big weight avgs
    #cycle through small and big partition generator
    small, big = next(smalls, None), next(bigs, None)

    # if elems are not exhauted kindly loop
    while big and small:
        # put the partial elem in aliases
        aliases[small[0]] = (small[1], big[0])
        print("alias lookup table transformation", aliases)

        # big = i of big , weight_b - (1 - weight_s)
        # big = (0, (1.5 - (1 - 0.6))
        big = (big[0], big[1] - (1-small[1]))
        if big[1] < 1:
            print("large weight is < 1 skip", aliases)
            small = big
            big = next(bigs, None)
        else:
            small = next(smalls, None)

    print("alias table generated", aliases)
    # SELECTION STAGE
    def weighted_random():
        r = random.random() * N
        i = int(r)
        # choose a random probability
        # from the alias table
        (odds, alias) = aliases[i]
        print("what are the odds of", r)
        # return the larger probability if
        # it's odds are higher else
        # return the smaller probability index
        return alias if (r-i) > odds else i

    return weighted_random()

# single trial selection
print(f"experiment trial", prepare_aliased_randomizer([ 0.2, 0.3, 0.]))

# Repeat the experiment to observe bias factor
for e in range(10):
  print(f"experiment trial", prepare_aliased_randomizer([0.2, 0.3, 0.5]))

defmodule Probability do
  def bias_probability(weights) do
    # Initialization
    n = Enum.count(weights)
    prepare_alias_table(weights, n)
  end

  defp prepare_alias_table(weights, n) do
    alias_table = Enum.map(1..n, fn _ -> {0, nil} end)
    prob = Enum.map(1..n, fn _ -> nil end)

    # create work lists
    scaled_weight = scale_probability(weights, n)
    small =
      scaled_weight
      |> Enum.filter(fn {_, w} -> w < 1 end)

    large =
      scaled_weight
      |> Enum.filter(fn {_, w} -> w >= 1 end)

    # recursively create table (TCO optimized)
    transform_alias(small, large, alias_table, prob)
  end

  # Base case when small and large are empty
  defp transform_alias([], [], _, prob), do: prob

  defp transform_alias(small = [], [_g = {i, _} | tail], alias_table, prob) do
    # Remove the first element from large call it g, Set prob[g] = 1
    transform_alias(
      small,
      tail,
      alias_table,
      List.replace_at(prob, i, 1)
    )
  end

  defp transform_alias([_l = {i, _} | tail], large = [], alias_table, prob) do
    # (clause will trigger due to numerical instability)
    # Remove the first element from Small, call it l
    transform_alias(
      tail,
      large,
      alias_table,
      List.replace_at(prob, i, 1)
    )
  end

  defp transform_alias(
         [{index_l, weight_l} | tail_s],
         [_g = {index_g, weight_g} | tail_l],
         alias_table,
         prob
       ) do
    # Remove the first element from small call it l
    # Remove the first element from large call it g
    # Pg := (pg + pl) - 1 (numerical stability :) )
    new_weight_g = (weight_g + weight_l) - 1

    # if Pg < 1 add g to small
    if new_weight_g < 1 do
      transform_alias(
        [{index_g, new_weight_g} | tail_s],
        tail_l,
        List.replace_at(alias_table, index_l, weight_g),
        List.replace_at(prob, index_l, weight_l)
      )

      # else Pg >= 1 add g to large
    else
      transform_alias(
        tail_s,
        [{index_g, new_weight_g} | tail_l],
        List.replace_at(alias_table, index_l, weight_g),
        List.replace_at(prob, index_l, weight_l)
      )
    end
  end
  # HELPER
  defp scale_probability(probs, n) do
    0..n
    |> Enum.zip(probs)
    |> Stream.map(fn {i, w} -> {i, w * n} end)
  end
end

  def bias_probability(weights) do
    # Initialization
    # does the probability exist in memory?
    current_probability = try do
      [weights: cached_probs] = :ets.lookup(:weight_probability, :weights)
      cached_probs
    rescue
      ArgumentError -> cache(weights)
    end

    current_probability
    #|> weighted_random # to be implemented next
  end

  defp cache(weights) do
    n = Enum.count(weights)
    :ets.new(:weight_probability, [:duplicate_bag, :private, :named_table])
    :ets.insert(:weight_probability, {:weights, prepare_alias_table(weights, n)})
    [weights: cached_probs] = :ets.lookup(:weight_probability, :weights)
    cached_probs
  end

  # GENERATION
  defp weighted_random(aliased_table, n) do
    # Generate a fair random distro in a range
    # from n and call it i.
    r = Enum.random(0..1000)/1000 * n
    # random choice P(1/3)
    i = floor(r) # 0, 1 , 2

    prob = aliased_table

    {:ok, odd} = Enum.fetch(prob, i)

    # partial fit
    if (r - i) > (odd) do
      # which piece of what goes where
      bias = prob
      |> Enum.with_index()
      |> Stream.filter(fn {p, _} -> p == 1 end)
      |> Enum.random()

      {_, i} = bias

      i
    else
       i
    end
  end