効率的にセットビットをランダムに選択する

Question

私の現在の趣味プロジェクトは、フランス語デッキ（52枚、エースから52枚まで）のカードゲームのモンテカルロシミュレーションを提供しています。

可能な限り高速にシミュレーションするために、複数のカードをいくつかの箇所でビットマスクとして表現しています。ここではいくつかの（簡体字）のコードは次のとおりです。

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

ビットマスクとして複数のカードを保持する構造体：

私は2番目の構造体 CardPoolからランダムに1枚以上のカードを描きたい

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

} 

が、私はプール内の単一のビットを反復せずにそれを行う方法を想像することはできません。 これを実現するアルゴリズムはありますか？もしそうでなければ、これを速くする考えはありますか？

更新： この構造体は、すべてのカードを引き出すものではありません。それは頻繁にクローンされ、アレイのクローン作成はオプションではありません。私は実際に1つまたは複数のカードを描くためのビット操作を考える。

更新2： 私は、比較のためにカードをListとして保持するクラスを作成しました。 17ミリ秒 - クラス：73ミリ入所

：違いは、私が思ったほどあまりないです - 構造体 ：

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クローン操作を比較します。 しかし、あらかじめ計算された値の簡単な検索をあきらめていることを考慮に入れると、これは大きな違いになります。 もちろん、このクラスではランダムなカードを描く方が速いでしょうが、別の場所に問題を転送するだけのルックアップのためのインデックスを計算する必要があります。

私は私の最初の質問繰り返し：これはすべてのビットを反復処理するよりも早く行って取得するためのアイデアを整数値からランダムにセットされたビットを選択するか、誰かを持っているため、既知のアルゴリズムはありますか？

リストや配列でクラスを使うことについての議論はどこにもわかりませんが、これは私の質問ではなく、クラスを使う方が良いと自分で説明することができます。

Update3と、ルックアップコード：

CODE DELETED：それは、スレッドの対象が何であるかに苦しんでいるパフォーマンスの通路を参照していないので、これは誤解を招くかもしれません。

Answer 1

同じカードを2回連続して描くことはできないので、すべてのカード（あなたのケースでは、Poolの設定ビットのインデックス）を配列に入れて、シャッフルしてからカードを1枚ずつこの配列の任意の終わり。

私は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) 

が所定ランクのビットの位置を取得するBit Twiddling Hacksからコードを使用して、64ビット整数に一度ランダムセットのビットを取得するために、アルゴリズムの（数セットビット）。

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 

コメント行は、ブランチを持つ別のバージョンを作成します。 2つのバージョンを比較したい場合は、これらの行のコメントを外し、それに続く行にコメントを付けます。元のコードで

、最後の行はs = 65 - sですが、あなたはカードプールの操作に1 << cardIDを使用しているため、とrはとにかくランダムで、s--は正しい値を示します。

唯一の注意点は、vのゼロ値です。しかし、このコードを空のプールで実行することは、とにかく意味がありません。