LootTable 概率分布的简化

Question

我为我正在开发的一个业余爱好游戏创建了一个简单的 LootTable class，它运行得非常好。但是，我广泛意识到代码中存在一个缺陷。当我说缺陷时，我实际上是指：为了减轻 processing/computational 成本，可以 improved/simplified 实现的一个区域。我将尽我所能解释这一点，在此之前，这是我的 LootTable class:

的代码

using System;
using System.Collections.Generic;
using System.Linq;
using DreamforceFramework.Framework.Game.Logic.Structs;
using DreamforceFramework.Framework.Probability;

namespace DreamforceFramework.Framework.Game.Probability
{
    public class LootTable
    {
        public string Name;
        private readonly List<string> _lootTable;
        private readonly Dictionary<string, int> _cachedLoot;
        private bool _isRebuildRequired;

        public LootTable()
        {
            _cachedLoot = new Dictionary<string, int>();
            _lootTable = new List<string>();
        }

        public LootTable(string name)
        {
            this.Name = name;
            _cachedLoot = new Dictionary<string, int>();
            _lootTable = new List<string>();
        }

        public void Add(string name, int probability)
        {
            this._cachedLoot.Add(name, probability);
            _isRebuildRequired = true;
        }

        public bool Contains(string name)
        {
            return _cachedLoot.ContainsKey(name);
        }

        public void Add(LootTableItem item)
        {
            this._cachedLoot.Add(item.Name, item.Rarity);
            _isRebuildRequired = true;
        }

        public void Add(List<LootTableItem> items)
        {
            foreach (LootTableItem lootTableItem in items)
            {
                this._cachedLoot.Add(lootTableItem.Name, lootTableItem.Rarity);
            }
            _isRebuildRequired = true;
        }

        public void Remove(string name)
        {
            this._cachedLoot.Remove(name);
            _isRebuildRequired = true;
        }

        public double ComputeProbability(string name)
        {
            double total = _cachedLoot.Values.Sum(n => n);
            double percent = _cachedLoot[name] / total;
            return Math.Round(percent * 100, 2);
        }

        public void Edit(string name, int newProbability)
        {
            this._cachedLoot[name] = newProbability;
            _isRebuildRequired = true;
        }

        public void Clear()
        {
            this._cachedLoot.Clear();
            this._isRebuildRequired = true;
        }

        private void Rebuild()
        {
            _lootTable.Clear();
            foreach (KeyValuePair<string, int> pair in _cachedLoot)
            {
                for (int i = 0; i < pair.Value; i++)
                {
                    _lootTable.Add(pair.Key);
                }
            }
            _isRebuildRequired = false;
        }

        public string Next()
        {
            if (_isRebuildRequired)
            {
                this.Rebuild();
            }
            return _lootTable[DreamforceRandom.NextInteger(_lootTable.Count)];
        }

        public List<string> Next(int quantity)
        {
            List<string> returnList = new List<string>();
            if (_isRebuildRequired)
            {
                this.Rebuild();
            }
            for (int i = 0; i < quantity; i++)
            {
                returnList.Add(_lootTable[DreamforceRandom.NextInteger(_lootTable.Count)]);
            }
            return returnList;
        }
    }
}

还有 LootTableItem 结构：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DreamforceFramework.Framework.Game.Logic.Structs
{
    public struct LootTableItem
    {
        public string Name;
        public int Rarity;
        public LootTableItem(string name, int rarity)
        {
            this.Name = name;
            this.Rarity = rarity;
        }
    }
}

对于那些看过上面代码的人，您会看到我所说的低效区域。为了生成内部战利品 table，我创建了一个字符串列表，它等于物品的稀有度。所以假设我把一个 "Rusty Sword" 放入稀有度为 20 的战利品 table 中。这意味着当重建战利品 table 时，它将添加 20 "Rusty Sword" 字符串到table。没什么大不了的吧？但现在可以说我正在添加两个对象。我将价值 100 的 "Ruby" 和价值 100 的 "Emerald" 添加到战利品 table。好吧，这意味着我将在战利品 table 中创建 200 个字符串，这非常愚蠢，因为它可以简化为添加 1 个 Ruby 字符串和 1 个翡翠字符串。这将达到相同的概率，即 50/50。

所以我的问题是：如何简化将物品添加到 LootTable 的概率，以便它自动优化数据而不是创建一个庞大的字符串列表。

我希望我解释得足够清楚，我有时在书面表达方面比较欠缺

编辑：

这是所选答案提出的可行解决方案： http://pastebin.com/4w0B0V6y

Answer 1

您的解决方案对于检索操作（Next 方法）具有最优的 O(1) 时间复杂度，但正如您所提到的，它使用了很多 space。正如您还提到的，space 最终可以通过查找和消除最大公约数来优化，但这是一项复杂的任务，如果项目稀有度相对较高，则也不起作用。因此，我将向您展示一个具有最佳 O(N) space 复杂度的解决方案（其中 N 是检索操作的 table) 和 O(log2(N)) 时间复杂度中的项目。

假设我们在 table 中有以下项目：

Name         Rarity  
============ ======  
Rusty Sword      20  
Ruby            100  
Emerald         100

我们可以这样看：

Name         Total Range
============ ===== ========
Rusty Sword     20 [0-19]
Ruby           120 [20-119]
Emerald        220 [120-219]
------------ -----
Total          220

底部的总数表示您实施中的 _lootTable.Count，而对于该项目，它是您当时添加的计数的运行总和。因此，在 [0, Total-1] 范围内有一个随机数，我们需要找到该范围内包含该数字的项目的索引，这可以使用二进制搜索轻松完成（因此在 Log2 时间内）。

这里是你如何做到的：

首先，将_lootTable成员替换为以下成员

private List<string> _lootName = new List<string>();
private List<int> _lootTotal = new List<int>();
private int _total;

然后改变Rebuild方法

private void Rebuild()
{
    _lootName.Clear();
    _lootTotal.Clear();
    _total = 0;
    foreach (var item in _cachedLoot)
    {
        _total += item.Value;
        _lootName.Add(item.Key);
        _lootTotal.Add(_total);
    }
    _isRebuildRequired = false;
}

添加一个辅助函数来封装逻辑并相应地更新 Next 方法

private string NextCore()
{
    Debug.Assert(_cachedLoot.Count > 0 && !_isRebuildRequired); // Preconditions
    int total = DreamforceRandom.NextInteger(_total);
    int index = _lootTotal.BinarySearch(total);
    if (index < 0)
        index = ~index;
    else
        index++;
    return _lootName[index];
}

public string Next()
{
    if (_cachedLoot.Count == 0) return null; // Sanity check
    if (_isRebuildRequired)
    {
        this.Rebuild();
    }
    return NextCore();
}

public List<string> Next(int quantity)
{
    var returnList = new List<string>();
    if (_cachedLoot.Count == 0) return returnList; // Sanity check
    if (_isRebuildRequired)
    {
        this.Rebuild();
    }
    for (int i = 0; i < quantity; i++)
    {
        returnList.Add(NextCore());
    }
    return returnList;
}

好了。希望对您有所帮助。

LootTable 概率分布的简化

Simplification of LootTable probability distribution

c#

optimization

probability