[PYTHON] Die schnelle Bitanzahl ist bin (). Count ('1')

Wir implementieren die Umkehrung mit BitBoard. Die Anzahl der Steine wird durch Zählen (Bitzählen) der Anzahl stehender Bits berechnet.

Ich habe mehrere Implementierungen verglichen, aber die einfache Implementierung ist schnell.

bin_count

def count1(board):
    return bin(board).count('1')

Zuerst dachte ich, es wäre langsam, weil es eine Zeichenkette durchläuft, aber ich denke, es ist optimiert und schnell. Der Code, den ich ausprobiert habe, ist unten.

python

#Dummy-Funktion zur Messung des Anrufaufwands
def dummy(board):
    return 0

#Implementierung von Popcount
def count2(board):
    board = (board & 0x5555555555555555) + (board >> 1 & 0x5555555555555555)
    board = (board & 0x3333333333333333) + (board >> 2 & 0x3333333333333333)
    board = (board & 0x0f0f0f0f0f0f0f0f) + (board >> 4 & 0x0f0f0f0f0f0f0f0f)
    board = (board & 0x00ff00ff00ff00ff) + (board >> 8 & 0x00ff00ff00ff00ff)
    board = (board & 0x0000ffff0000ffff) + (board >> 16 & 0x0000ffff0000ffff)
    return (board & 0x00000000ffffffff) + (board >> 32)

#Blöder Weg
def count3(board):
    result = 0
    while board:
        board >>= 1
        result += board & 1
    return result

def main():
    board = 0b0010000000100000000011000011010000111100000110000000000000000000

    import time

    temp = time.time()
    for i in range(100000):
        dummy(board)
    print(f"dummy : {time.time() - temp}")

    temp = time.time()
    for i in range(100000):
        count1(board)
    print(f"count1: {time.time() - temp}")

    temp = time.time()
    for i in range(100000):
        count2(board)
    print(f"count2: {time.time() - temp}")

    temp = time.time()
    for i in range(100000):
        count3(board)
    print(f"count3: {time.time() - temp}")

if __name__ == "__main__":
    main()

Das Ergebnis ist unten.

dummy : 0.010009050369262695
count1: 0.0470428466796875
count2: 0.152146577835083
count3: 1.0559582710266113

count1 kann in derselben Reihenfolge berechnet werden wie der Anruf-Overhead ( Dummy). Der `count2'-Algorithmus verwendet einen O (logN) -Algorithmus namens popcount, der langsam ist. Der Unterschied ist klar im Vergleich zu "count3".