随机选择设置位的有效方法 [英] Efficient way to randomly select set bit

问题描述

我当前的爱好项目是为带有法语副牌(52张卡片，从2到A)的纸牌游戏提供蒙特卡洛模拟.

My current hobby project provides Monte-Carlo-Simulations for card games with French decks (52 cards, from 2 to Ace).

为了尽可能快地进行仿真，我在某些位置使用多张卡表示为位掩码.这是一些(简化的)代码:

To simulate as fast as possible, I use to represent multiple cards as bitmasks in some spots. Here is some (simplified) code:

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

将多张卡作为位掩码的结构:

The structure which holds multiple cards as bitmask:

 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 中随机抽取一张或多张牌，但是我无法想象如何在不迭代池中单个位的情况下做到这一点. 有什么已知的算法可以执行此操作吗?如果没有，您是否有打算快速执行此操作?

I want to draw one or more cards at random from the second struct CardPool, but I cannot imagine how to do that without iterating single bits in the pool. Is there any known algorithm to perfom this? If not, do you have any idea of doing this fast?

更新: 该结构并非旨在抽取所有卡片.它经常被克隆，克隆数组是没有选择的.我真的想到了绘制一张或多张卡的位操作.

Update: The structure is not intended to draw all cards from. It gets cloned frequently and cloning an array is no option. I really think of bitoperations for drawing one or multiple cards.

Update2 : 我写了一个类，将卡片作为列表进行比较.

Update2: I wrote a class which holds the cards as List for comparison.

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毫秒

Comparing 1.000.000 clone operations of full decks: - struct: 17 ms - class: 73 ms

承认:差异不像我想的那么大. 但是考虑到我还放弃了对预先计算的值的轻松查找，因此产生了很大的不同. 当然，用此类绘制一张随机卡片会更快，但是我必须计算一个索引才能进行查找，这只是将问题转移到另一个地方.

Admitted: The difference is not as much as I thought. But taken into account that I additionally give up the easy lookup of precalculated values, this makes a big difference. Of course, it would be faster to draw a random card with this class, but I would have to calculate an index for lookup then, what just transfers the problem to another spot.

我重复我的第一个问题:是否有一种已知的算法可以从整数值中选择一个随机置位，还是有人想过要比迭代所有位更快地做到这一点?

I repeat my initial question: Is there a known algorithm for choosing a random set bit from an integer value or has someone an idea for getting this done faster than to iterate all bits?

关于将类与List或Array一起使用的讨论无济于事，这不是我的问题，如果可以更好地使用类，我可以自行阐述.

The discussion about using a class with a List or an Array takes us nowhere, this is not my question and I am able to elaborate on my own if I would be better off using a class.

Update3 ，查找代码:

代码已删除:这可能会引起误解，因为它没有涉及性能受线程主题影响的段落.

CODE DELETED: This might be misleading because it does not refer to passages which performance suffers from what is subject of the thread.

推荐答案

由于同一张卡片不能连续两次绘制，因此可以放置每张卡片(在您的情况下，请按Pool的设置位的索引)在一个阵列中将其洗牌，然后从该阵列的任一端一张一张弹出卡片.

Since a same card cannot be drawn twice in a row, you can place every card (in your case, the indices of Pool's set bits) in an array, shuffle it, and pop the cards one by one from any end of this array.

这是一个伪代码(因为我不懂C#).

Here's a pseudo-code (because I don't know C#).

declare cards as an array of indices

for each bit in Pool
    push its index into cards

shuffle cards

when a card needs to be drawn
    pop an index from cards
    look up the card with Card(byte id)

修改

这是一种算法，它使用

Here's an algorithm to get a random set bit once in a 64-bit integer, using a code from Bit Twiddling Hacks to get position of a bit with given rank (number of more significant set bits).

ulong v = this.Pool;
// ulong a = (v & ~0UL/3) + ((v >> 1) & ~0UL/3);
ulong a = v - ((v >> 1) & ~0UL/3);
// ulong b = (a & ~0UL/5) + ((a >> 2) & ~0UL/5);
ulong b = (a & ~0UL/5) + ((a >> 2) & ~0UL/5);
// ulong c = (b & ~0UL/0x11) + ((b >> 4) & ~0UL/0x11);
ulong c = (b + (b >> 4)) & ~0UL/0x11;
// ulong d = (c & ~0UL/0x101) + ((c >> 8) & ~0UL/0x101);
ulong d = (c + (c >> 8)) & ~0UL/0x101;
ulong t = (d >> 32) + (d >> 48);

int bitCount = ((c * (~0UL / 0xff)) >> 56);
ulong r = Randomizer.Next(1, bitCount+1);

ulong s = 64;
// if (r > t) {s -= 32; r -= t;}
s -= ((t - r) & 256) >> 3; r -= (t & ((t - r) >> 8));
t = (d >> (s - 16)) & 0xff;
// if (r > t) {s -= 16; r -= t;}
s -= ((t - r) & 256) >> 4; r -= (t & ((t - r) >> 8));
t = (c >> (s - 8)) & 0xf;
// if (r > t) {s -= 8; r -= t;}
s -= ((t - r) & 256) >> 5; r -= (t & ((t - r) >> 8));
t = (b >> (s - 4)) & 0x7;
// if (r > t) {s -= 4; r -= t;}
s -= ((t - r) & 256) >> 6; r -= (t & ((t - r) >> 8));
t = (a >> (s - 2)) & 0x3;
// if (r > t) {s -= 2; r -= t;}
s -= ((t - r) & 256) >> 7; r -= (t & ((t - r) >> 8));
t = (v >> (s - 1)) & 0x1;
// if (r > t) s--;
s -= ((t - r) & 256) >> 8;
s--; // s is now the position of a random set bit in v

带注释的行创建了另一个带有分支的版本.如果要比较两个版本，请取消注释这些行，并注释其后的行.

The commented lines make another version, with branches. If you want to compare the two versions, uncomment these lines and comment the lines following them.

在原始代码中，最后一行是s = 65 - s，但是由于您使用1 << cardID进行卡池操作，并且r还是随机的，因此s--给出正确的值.

In the original code, the last line is s = 65 - s, but since you use 1 << cardID for manipulations on card pools, and r is random anyway, s-- gives the correct value.

唯一需要注意的是v的值为零.但是无论如何，在空的池中执行此代码将毫无意义.

The only thing to watch out for is a zero value for v. But executing this code on an empty pool would be meaningless anyway.

这篇关于随机选择设置位的有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！