[PYTHON] Le nombre de bits rapides est bin (). Count ('1')

Nous implémentons la réversité en utilisant BitBoard. Le nombre de pierres est calculé en comptant (comptage de bits) le nombre de bits debout.

J'ai comparé plusieurs implémentations, mais la mise en œuvre facile est rapide.

bin_count

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

Au début, je pensais que ce serait lent car il passe par une chaîne de caractères, mais je pense que c'est optimisé et rapide. Le code que j'ai essayé est ci-dessous.

python

#Fonction factice pour la mesure de la surcharge d'appel
def dummy(board):
    return 0

#Mise en place de 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)

#Manière stupide
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()

Le résultat est ci-dessous.

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

«count1» peut être calculé dans le même ordre que la surcharge d'appel («factice»). L'algorithme count2 utilise un algorithme O (logN) appelé popcount, qui est lent. La différence est claire par rapport à «count3».