L'algorithme utilisé par la fonction PHP shuffle

Question

Quel est l'algorithme utilisé par la fonction PHP shuffle ou où puis-je obtenir son code. Je dois l'implémenter en langage C. J'ai mis en œuvre des algues de pêche algo en C mais pas de bons résultats comme le montre la fonction de mélange de php.

Answer 1

Qu'est-ce qui constitue exactement "pas de bons résultats"? Le shuffle de Fisher-Yates produira toutes les permutations avec une probabilité égale, mais seulement si vous générez vos nombres aléatoires correctement. Il y a trois problèmes à connaître ici. Tout d'abord, vous avez besoin d'un bon générateur de nombres pseudo-aléatoires. La bibliothèque standard C rand est généralement et non un bon PRNG (bien que cela dépend de l'implémentation de votre bibliothèque C). Si vous utilisez une plate-forme POSIX, vous pouvez utiliser lrand48 à la place. Votre système peut avoir d'autres RNG. Si vous n'avez rien sur votre plate-forme, un très bon RNG en très peu de code est générateur G. Marsaglias KISS - vous pouvez trouver le code here. Deuxièmement, si vous décidez toujours d'utiliser rand, sachez qu'il générera des nombres aléatoires entre 0 et RAND_MAX. Pour beaucoup d'implémentations, RAND_MAX est seulement 32767, donc l'habituel rand() % count aura un biais très évident et mauvais si count est plus grand que 32768. Troisièmement, rand() % count (ou lrand48() % count ou quelque chose de similaire) est en fait une mauvaise idée aussi, car elle introduit aussi un parti pris. Si count n'est pas une puissance de 2, certains nombres auront une probabilité plus élevée que d'autres. De plus, dans beaucoup de générateurs, les bits de poids faible sont beaucoup moins aléatoires que les bits de poids fort. Vous pouvez essayer de contourner ce problème en utilisant (long long) rand() * count/RAND_MAX ou quelque chose de similaire, mais vous êtes vraiment mieux d'utiliser un bon RNG à la place. La bonne façon de générer des nombres aléatoires sans biais entre 0 (inclus) et k (exclusif) est la suivante: Tout d'abord, obtenir un PRNG approprié qui vous donne un nombre aléatoire assez grand (disons 32 bits aléatoires). Réduisez ensuite à la puissance suivante de 2 plus grand que k. Enfin, si la valeur est supérieure ou égale à k, réessayez. Ceci est une méthode complètement impartiale, et donnera des résultats qui sont aussi bons que votre PRNG peut les faire. Le code ressemble à ceci:

static unsigned int random(unsigned int k) 
{ 
    // You can get rid of this loop using bit tricks, but I keep it for clarity  
    unsigned int n, nextpow2 = 1; 
    while (nextpow2 < k) 
    nextpow2 *= 2; 

    do { 
    n = random32() & (nextpow2 - 1); // random32 is your 32-bit RNG 
    } while (n >= k); 

    return n; 
}