Comment générer de manière déterministe des entiers uniques à partir d'entrées ?

Génération déterministe d'entiers uniques à partir d'entrées

En cherchant une solution pour générer des entiers déterministes qui évitent les doublons, la question tourne autour de la recherche d'une transformation méthode qui mappe les nombres d'entrée à des sorties distinctes dans une plage donnée, comme un int64.

La réponse réside en appliquant l'arithmétique modulaire dérivée du chiffre affine :

f(P) = (mP + s) mod n

où :

• n = plage d'entiers possibles (par exemple, 2^64 pour int64)
• s ≪ n
• m est premier avec n (ce qui signifie qu'ils ne partagent aucun facteur commun autre que 1)

En choisissant un m et un s appropriés, cette formule garantit un mappage unique des nombres d'entrée à afficher des entiers dans la plage spécifiée. Par exemple, pour int64 :

m = 39293 (any non-even number)
s = 75321908 (any random number below 2^64)

Avec ces valeurs, la fonction de transformation :

func transform(p uint64) uint64 {
    return p*m + s
}

garantit que chaque entier d'entrée produit un entier de sortie unique, comme démontré dans le terrain de jeu Go suivant exemple :

https://go.dev/play/p/EKB6SH3-SGu

Pour les négatifs chiffres, la logique reste la même. Nous pouvons simplement convertir les entrées et les sorties entre uint64 et int64 pour conserver le mappage unique :

func signedTransform(p int64) int64 {
    return int64(transform(uint64(p)))
}

Cette approche garantit que tous les entiers possibles dans une plage donnée sont mappés sur des entiers de sortie distincts de manière déterministe et sans aucune collision.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!