Implémentation algo: générateur pseudo aléatoire MWC
Bonjour à tous !
Pour une application de sérialisation de structures de données graphes
j'ai besoin de générer des clés pseudo-aléatoires sur 4, 6 ou 8 digitss avec 52 positions (A_Za_z)
donc de la forme 'Cafe', 'pizzas' ou 'AptiTude'.
J'ai décidé d'utiliser des générateurs de nombres pseudo-aléatoires
car cela devrait me permettre de reproduire les résultats de cette expérience lors des phases de test (même caractéristiques et même graine => même séquence de clés)
et ai tenté d'adapter les générateurs MWC (Multply-With-Carry) en JS selon mes besoins.
Le hic est que ma version bouble sur des périodes très courtes (~10k valeurs) là où,
pour 4 digits Math.pow(52, 4) permttrait d'obtenir un cycle se comptant en millions...
Pour ce qui est du code du générateur c'est à peu à cela : une version custom de l'algorithme de wikipedia... n'ayant pas complètement compris l'implémentation proposée en C++,
j'ai repris ce document au niveau des équations théoriques, ce qui donne :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
// a = modulus (safe prime en principe)
// b = 52 (base)
// r = 3 (lag = décalage) interprété ici comme nombre de digits à produire moins 1
export const createMWC = (a, b, r) => {
// le tableau de travail
// xi = valuers
// ci = retenues (carries)
const xi = new Array(r + 1)
const ci = new Array (r + 1)
// les indices pour extraire X[n - r] et X[n - 1]
// vu qu'on ne fait pas "ramper" le tableau enconsommant les valeurs de tête
// et en poussant les nouvelles en fin de tableau !
let n0 = 0
let nr = r
// variables temporaires
let xn = 0
let cn = 0
// API JS exposée
return {
// la fonction d'initalisation
init (seeds) {
for (let k = 0; k < (r + 1); k++) {
xi[k] = seeds[k]
ci[k] = 0
}
},
// génération de valeurs
next() {
let result = new Array (r + 1)
// on décale à chaque appel à la fonction
n0 = (n0 + 1) % (r + 1)
nr = (nr + 1) % (r + 1)
// from wikipedia...
xn = (a * xi[nr] + ci[n0]) % b
cn = Math.floor((a * xi[nr] + ci[n0]) / b)
// écrase l'ancienne valeuret place la nouvelle à la place
xi[n0] = xn
ci[n0] = cn
// ultime twist...
/*
result = (n0 === 0)
? xi.slice(0)
: xi.slice(n0).concat(xi.slice(0, n0))
*/
// ou plus simple
for(let t = 0; t < r + 1; t++) {
//result[t] = xi[t]
result[(t + n0) % (r + 1)] = xi[t]
}
return result
}
}
} |
Pour ce qui est du code de test il est assez simple : il est basé sur des statistiques de base sur des tirs (shots) du générateur, avec en paramètre un modulus (a) et une graine, avec stockage des couples {valeurr: rang-dans-la-série} dans un opbjet hash, avec détection et arrêt à la premère collision :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
const MAX_LOOPS = 10000000
const b = 52
const r = 3
const output = (arr) => {
// console.log(arr)
//return arr.reduce((acc, val) => b * acc + val, 0)
return arr.join(':')
}
const shoot = (a, seeds) => {
const store = {}
const generator = createMWC(a, b, r)
let i = 0
let result = 0
let text = seeds.join(':')
let crashes = 0
generator.init(seeds)
store[output(seeds)] = 0
while (i++ < MAX_LOOPS) {
const generated = generator.next()
const val = output(generated)
text += ' ' + generated.join(':')
if(store.hasOwnProperty(val)) {
result = i
crashes++
// console.log('#### %s', i)
break
} else {
store[val] = i
}
// console.log('store[%s]: %s', val, store[val])
// console.log(' %s', generated.join(':'))
}
console.log('crashes: %s', crashes)
return result
} |
Enfin c'est assez baqieu mais pour l'instant cela ne me permet pas de comprendre
les basses performances de l'algorithme, d'autant plus qu'une version boguée précédente, et un autre avec tableau "rampant",
très coûteuse en termes d'allocation mémoire (push+unshift) donnaient de meilleurs résultats.
Vu que je ne trouve pas de solution évidente par moi même j'en appelle à vos lumières
pour tenter de trouver une solution. Quelqu'un aurait il une idée ?
2 pièce(s) jointe(s)
6.38M (confirmation de la théorie)
@Loralina: je n'avais pas lu ton avant-dernier post, aussi je viens de relancer le test avec MAX_LOOPS = 20M (voir image en pièce jointe), et cela donne :
- c'est très rapide : moins de 30s
- j'arrive à 6.84M valeurs
- 13,16M collisions
Sachant qu'il y a Math.pow(52, 4) ~ 7.3M de valeurs possibles... on a bien une efficacité qui remonte autour de 6.84 / 7.3 = 93% pour ce qui de l'efficacité, les collisions se produisant à 2/3 du temps...
En augmentant un peu le nombre de digits, on augemente énormément la plage de valeurs allouables :
Math.pow(52, 5) ~ 380M
Math.pow(52, 6) ~ 19,7G
etc...
faut que je teste encore, pour disons, 1M de blocks à allouer, ce que cela donne en termes de nouvelles valeurs et de collisions pour 5, 6, 7ou 8 digits. 5 ou 6 pourraient être de bons compromis. Il faut garder à l'esprit que chaque block alloué vient ajouter sa contribution en termes d(espace utilisé en caractères dans le fichier JSON (ou le flux).
En images :
- les résultats rapides du test 20M
- un diagramme représentant la structure de données envisagée, blocks, structure, relation qu'ils entretiennet entre eux et exemple d'application au stockage en vif d'un MCD (E/R diagram) de base.
