Упрощение распределения вероятности LootTable

Question

Я создал простой класс LootTable для хобби, над которым я работаю, и работает отлично. Тем не менее, я широко осведомлен о недостатке, который присутствует в коде. Когда я говорю об ошибке, я на самом деле имею в виду: область реализации, которая может быть улучшена/упрощена, чтобы облегчить обработку/вычислительные затраты. Я попытаюсь объяснить, как лучше всего, как я могу, и прежде, чем я, вот код для моего LootTable класса:

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; 
     } 
    } 
} 

Для тех из вас, которые просматривают вышеприведенный код, вы увидите неэффективную область, о которой я говорю. Чтобы создать внутреннюю таблицу лута, я создаю список строк, равный редкости элемента. Так скажите, что я помещал «Ржавый Меч» в таблицу лута с редкостью 20. Это означает, что когда таблица добычи будет перестроена, она добавит 20 строк «Ржавый Меч» к таблице. Не так ли? Но теперь скажем, что я добавляю два объекта. Я добавляю «Ruby» со значением 100 и «Изумруд» со значением 100 в таблицу добычи. Ну, это значит, что я буду создавать 200 строк в таблице добычи, что ужасно глупо, когда его можно просто упростить до добавления 1 строки Ruby и 1 строки Emerald. Это обеспечило бы такую ​​же вероятность, которая составляет 50/50.

Так что мой вопрос: Как упростить вероятность добавления элементов в LootTable, чтобы он автоматически оптимизировал данные, а не создавал один гигантский список строк.

Надеюсь, я объяснил это достаточно ясно, иногда мне недостает, когда речь заходит о письменной артикуляции.

EDIT:

Вот рабочее решение, предложенное выбранный ответ: http://pastebin.com/4w0B0V6y

Answer 1

Ваше решение имеет оптимальное O (1) временной сложность для работы (Next метода) извлечений, но как вы уже упоминали, он использует много места. Как вы уже упоминали, пространство в конечном итоге может быть оптимизировано путем поиска и устранения наибольшего общего делителя, но это сложная задача, а также не работает, если раритеты элементов относительно велики. Поэтому я собираюсь представить вам решение с оптимальной сложностью пространства (N - это количество элементов в таблице) и O (log2 (N)) временная сложность для восстановить операцию.

Представьте, что мы имеем следующие пункты в таблице:

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; 
} 

И вот вы идете. Надеюсь, это поможет.