我当前的爱好项目为纸牌游戏提供蒙特卡罗模拟French牌组(52 张牌,从 2 到 A)。
为了尽可能快地进行模拟,我在某些地方将多张卡表示为位掩码。这是一些(简化的)代码:
public struct Card
{
public enum CardColor : byte { Diamonds = 0, Hearts = 1, Spades = 2, Clubs = 3 }
public enum CardValue : byte { Two = 0, Three = 1, Four = 2, Five = 3, Six = 4, Seven = 5, Eight = 6, Nine = 7, Ten = 8, Jack = 9, Queen = 10, King = 11, Ace = 12 }
public CardColor Color { get; private set; }
public CardValue Value { get; private set; }
// ID provides a unique value for each card, ranging from 0 to 51, from 2Diamonds to AceClubs
public byte ID { get { return (byte)(((byte)this.Value * 4) + (byte)this.Color); } }
// --- Constructors ---
public Card(CardColor color, CardValue value)
{
this.Color = color;
this.Value = value;
}
public Card(byte id)
{
this.Color = (CardColor)(id % 4);
this.Value = (CardValue)((id - (byte)this.Color) / 4);
}
}
保存多张卡作为位掩码的结构:
public struct CardPool
{
private const ulong FULL_POOL = 4503599627370495;
internal ulong Pool { get; private set; } // Holds all cards as set bit at Card.ID position
public int Count()
{
ulong i = this.Pool;
i = i - ((i >> 1) & 0x5555555555555555);
i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333);
return (int)((((i + (i >> 4)) & 0xF0F0F0F0F0F0F0F) * 0x101010101010101) >> 56);
}
public CardPool Clone()
{
return new CardPool() { Pool = this.Pool };
}
public void Add(Card card)
{
Add(card.ID);
}
public void Add(byte cardID)
{
this.Pool = this.Pool | ((ulong)1 << cardID);
}
public void Remove(Card card)
{
Remove(card.ID);
}
public void Remove(byte cardID)
{
this.Pool = this.Pool & ~((ulong)1 << cardID);
}
public bool Contains(Card card)
{
ulong mask = ((ulong)1 << card.ID);
return (this.Pool & mask) == mask;
}
// --- Constructor ---
public CardPool(bool filled)
{
if (filled)
this.Pool = FULL_POOL;
else
this.Pool = 0;
}
}
我想从第二个结构中随机抽取一张或多张牌CardPool,但我无法想象如何在不迭代池中单个位的情况下做到这一点。
是否有任何已知的算法可以执行此操作?如果没有,你有办法快速做到这一点吗?
Update:
该结构并不旨在从中抽取所有牌。它经常被克隆,并且克隆数组是不可行的。我真的想到了用于绘制一张或多张卡片的位操作。
Update2:
我编写了一个类,将卡片作为列表进行比较。
public class CardPoolClass
{
private List<Card> Cards;
public void Add(Card card)
{
this.Cards.Add(card);
}
public CardPoolClass Clone()
{
return new CardPoolClass(this.Cards);
}
public CardPoolClass()
{
this.Cards = new List<Card> { };
}
public CardPoolClass(List<Card> cards)
{
this.Cards = cards.ToList();
}
}
比较完整套牌的 1,000,000 次克隆操作:
- 结构:17 毫秒
- 类:73 毫秒
承认:差异没有我想象的那么大。
但考虑到我还放弃了预先计算值的简单查找,这会产生很大的差异。
当然,用这个类抽一张随机卡会更快,但是我必须计算一个用于查找的索引,这只是将问题转移到另一个地方。
我重复我最初的问题:是否有一种已知的算法用于从整数值中选择随机设置位,或者是否有人有比迭代所有位更快地完成此操作的想法?
关于使用带有列表或数组的类的讨论没有任何意义,这不是我的问题,我可以自己详细说明是否使用类会更好。
Update3,查找代码:
代码已删除:这可能会产生误导,因为它没有提到性能因线程主题而受到影响的段落。