효율적으로 무작위로 세트 비트를 선택하는 방법

Question

현재 취미 프로젝트는 프랑스 데크 (52 장, 2에서 에이스까지)의 카드 게임에 대한 몬테카를로 시뮬레이션을 제공합니다.

최대한 빨리 시뮬레이션하기 위해 일부 카드에서는 여러 개의 카드를 비트 마스크로 사용합니다. 여기에 몇 가지 (간체) 코드는 다음과 같습니다

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

비트 마스크로 여러 개의 카드를 보유 구조 :

내가 두 번째 구조체 CardPool에서 무작위로 하나 이상의 카드를 그리려는

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

} 

하지만, 나는 수영장에서 싱글 비트를 반복하지 않고 어떻게하는지 상상할 수 없다. 이것을 수행하는 알려진 알고리즘이 있습니까? 그렇지 않다면이 일을 빨리 할 생각이 있습니까?

업데이트 : 이 구조는 모든 카드를 꺼내기위한 것이 아닙니다. 그것은 자주 복제되고 배열을 복제하는 것은 선택 사항이 아닙니다. 나는 하나 또는 여러 장의 카드를 그리기위한 비트 연산을 정말로 생각합니다.

업데이트 2 : 비교를 위해 카드를 List로 유지하는 클래스를 작성했습니다. 17 MS - 클래스 : 73 MS 합격자

: 차이는 생각만큼되지 않습니다 - 구조체 :

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 복제 작업을 비교. 그러나 미리 계산 된 값을 쉽게 찾아 볼 수 있다는 점을 감안하면 큰 차이가 있습니다. 물론이 클래스를 사용하여 임의의 카드를 그리는 것이 더 빠르지 만 조회를위한 색인을 계산해야합니다. 그러면 문제를 다른 지점으로 전송하는 것입니다.

초기 질문을 반복하십시오. : 정수 값에서 임의의 비트 세트를 선택하는 알려진 알고리즘이 있습니까? 아니면 모든 비트를 반복하는 것보다 빠르게 수행하는 아이디어가 있습니까?

List 또는 Array와 함께 클래스를 사용하는 것에 대한 설명은 우리를 아무 곳에도 데려가 지 않습니다. 이것은 제 질문이 아니며 수업을 사용하는 것이 더 나을지 모르겠다면 스스로 정교 할 수 있습니다.

갱신 3, 조회 코드 : 삭제

CODE : 그것은 성능이 스레드의 대상이 무엇을 앓고 구절을 참조하지 않기 때문에 오해의 소지가있을 수 있습니다.

Answer 1

동일한 카드를 두 번 연속으로 그릴 수 없기 때문에 모든 카드 (귀하의 경우에는 Pool의 설정 비트 수)를 배열에 넣고 셔플 링 한 다음 카드를 하나씩 팝핑 할 수 있습니다 이 배열의 임의의 끝.

다음은 의사 코드입니다 (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 

주석 처리 된 행은 브랜치가있는 다른 버전을 만듭니다. 두 버전을 비교하려면이 행의 주석을 제거하고 그 다음 행을 주석 처리하십시오. 원래 코드에서

은 마지막 줄 s = 65 - s이지만 카드 풀에 대한 조작을 위해 1 << cardID을 사용하고 r 어쨌든 무작위이기 때문에, s-- 올바른 값을 제공합니다.

유일한주의 사항은 v의 경우 0입니다. 그러나 빈 풀에서이 코드를 실행하는 것은 어쨌든 의미가 없습니다.