Discussion :

[Small Bug]

Bonjour,
dans le cadre d'un petit utilitaire de recherche pour des objets dans un jeux vidéo, j'utilise une requête un peu originale, utilisant le & logique pour comparer rapidement toute une série de paramètres.

le but de mon message est de connaîre votre avis sur cette méthode sachant que si les opérateurs bits à bits sont présents, le support des nombres binaires est assez limité. On ne peut pas par exemple entrer un nombre par sa représentation binaire en PHP (par contre en hexadécimal, en octal et en décimal, on peut, évidement).

Du coup venons-en à mon exemple précis pour mieux cerner le problème.
Le but est de rechercher quelles sont les formules magiques qui peuvent améliorer un de vos objets.
une table "formules" contient diverses informations (nom, niveau, description, etc...) et le champ qui nous intéresse : `types` qui contient l'information sur les types d'objets qui peuvent être améliorés par cette formule.
Il existe 31 types d'objets (Armure, Casque, Bottes, ..., Bouclier, Epée, Hache, etc...)
`types` est un UNSIGNED INT(4) -> 32 bits
par exemple, une formule qui fonctionne sur les casques et boucliers aura comme type : '01010000000000000000000000000000'

PHP ne me permettant pas de travailler efficacement sur les bits, j'utilise une chaine de 32 caractères pour construire la valeur qui sera comparée dans la recherche. Si le joueur cherche "toutes les formules pour éléments d'armures", son type de recherche sera :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

$recherche = '11111111000000000000000000000000';

la requête de recherche sera donc basée sur la condition :
(`types` & $recherche )>0

et en réalité je suis obligé de faire une conversion, voici la version simplifiée de ma requête :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

SELECT * from `formules`WHERE (`types` & CAST(CONV(\''.$recherche.'\',2,10) AS UNSIGNED))>0

Une requête similaire serait d'avoir les 31 types dans des champs séparés et d'avoir une clause WHERE de 3kms : WHERE type1=1 || type2=1 || (etc...)

Les conversions ne semblent pas très rapides, donc si vous avez une meilleure idée je suis à votre écoute !
Merci d'avoir pris le temps de me lire !

[max44410]

Salut,

je pense que l'idée est bonne, c'est peut etre sur l'exécution que tu peux améliorer la vitesse. personnelement j'ai déja utilisé cette méthode, mais il y avait moins de possiblité.

par contre je pense qu tu n'a pas besoins de faire de '&' logique entre deux nombre binaire, avec des entier ça fonctionne très bien, donc déjà tu suprime ta conversion. ce que tu peux faire c'est un tableau avec un corespondance entre les amélioration et leur correspondance en nombre entier. par la suite ta requete boucle sur ce tableau et dte ressors les améliorations dispo pour ton objet.

PS : pour explication si je fait (12 & 54) > 0 ça fonctionne très bien ... pas besoin de binaire.

[Small Bug]

Je suis 100% d'accord et j'avais développé un idée similaire au début mais ça ne fonctionnait pas car PHP donne du fil à retordre : il ne gère pas les unsigned int.
Etant donné que j'ai besoin de "seulement" 31 bits, je vais réitérer mes essais en décalant dans la bdd d'un bit vers la droite.

merci pour tes commentaires et plutôt que de faire des correspondances je vais créer une fonction pour créer l'entier à partir de sa représentation binaire

(dans la requête SQL c'est bien un & entre 2 entiers et non 2 représentations binaire que je fais, SQL ne gère pas non plus les représentations binaires; mais contrairement au php il permet de faire les conversions de bases et le cast en unsigned plus facilement)

[Small Bug]

voilà j'ai fait mes modifications, cela marche parfaitement !
(voilà un petit bout : )
$types est le tableau de la représentation binaire.
$itypes est sa trnsformation en entier.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
$itypes=0;
for($i=0;$i<31;$i++) if($types[$i]) $itypes += pow(2,$i);
$sql.='AND (`types` & '.$itypes.')>0 ';

Merci pour tes commentaires, ma question est réglée.

[doof]

Salut, comme ta technique m'interesse, j'aurais une question en réaction a ta dernière modif.

En effet, je vois que tu fais la comparaison maintenant directement sur un entier "normal" de php, tu n'a donc plus de probleme avec le poids des bits ? aurais-tu adapté les valeurs dans ton champ mysql pour qu'elles correspondent avec php ? les valeurs stockées dans dans mysql sont elles-issues du même traitement php ?

Sinon, j'avais fait une petite fonction pour générer le nombre, il me semble un poil plus rapide :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
function magicNumber($arr)
{
    $nb = 0;
    foreach ($arr as $val) $nb += 1 << $val;
    return $nb;
}

J'effectue un décalage plutot que calculer par puissances, je pense que c'est plus rapide.
Elle marche avec un tableau des valeurs que l'on recherche, par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
//recherche des formules agissant sur les objets 0, 4 et 5
$rechArray = array(0, 4, 5);
$recherche = magicNumber($rechArray);

Ensuite en sql, on peut affiner la recherche :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
//Une formule agissant sur au moins un de ces objets :
$sql.='AND (`types` & '.$recherche.')>0 ';
//une formule agissant exactement sur tous ces objets :
$sql.='AND `types` = '.$recherche.' ';
//une formule agissant au moins sur tous ces objets
$sql.='AND `types` >='.$recherche.' ';

...Enfin, l'essentiel de mon intervention est de savoir si tu stock des "entiers" normaux issus d'un même traitement php ou si tu as du les traiter au préalable coté mysql ?

[edit]je viens de m'appercevoir que ma derniere requete est fausse, il faudrait la refaire en logique binaire aussi.

[Small Bug]

Salut, j'ai en fait en premier lieu utiliser les puissances de 2 pour tester rapidement.
Puis j'ai implémenter une fonction similaire à la tienne avec les décalages à gauche.
Et au final, j'ai été embêté en arrivant sur le bit signé (Php utilise des int 32 bits signés).

(ma technique a été étendue a 33 bits)

Du coup j'ai réaliser des tests dans la matinée :
MODULO symbolise pour les tests, le nombre maximum de bits travaillés.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
<?php
 
define('N_BOUCLES', 1000);
define('MODULO', 32);
 
function getmicrotime()
{
	list($usec, $sec) = explode(' ',microtime());
	return ((float)$usec + (float)$sec);
}
////////// TEST 1 classic pow
$start = getmicrotime();
$test=0;
for($i=0;$i<N_BOUCLES;$i++) {
	$test += pow(2,i%MODULO);
}
echo $test.' '.(getmicrotime()-$start).'<br/>';
 
////////// TEST 2 BC pow
$start = getmicrotime();
$test=0;
for($i=0;$i<N_BOUCLES;$i++) {
	$test = bcadd($test, bcpow('2',strval($i%MODULO),0),0);
}
echo $test.' '.(getmicrotime()-$start).'<br/>';
 
////////// TEST 3 BC multiply
 
$start = getmicrotime();
$test=0;
for($i=0;$i<N_BOUCLES;$i++) {
	if($i%MODULO==0) $bit = '1';
	$test = bcadd($test, $bit,0);
	$bit = bcmul($bit,'2',0);
}
echo $test.' '.(getmicrotime()-$start).'<br/>';
 
////////// TEST 4 GMP pow
$start = getmicrotime();
$test=gmp_init(0);
for($i=0;$i<N_BOUCLES;$i++) {
	$test = gmp_add($test, gmp_pow('2',$i%MODULO));
}
echo $test.' '.(getmicrotime()-$start).'<br/>';
 
////////// TEST 5 GMP setbit
$start = getmicrotime();
$test=gmp_init(0);
for($i=0;$i<N_BOUCLES;$i++) {
	$test = gmp_setbit($test, $i%MODULO);
}
echo gmp_strval($test).' '.(getmicrotime()-$start).'<br/>';
 
 
////////// TEST 6 Bit to bit Classic
 
$start = getmicrotime();
$test=0;
for($i=0;$i<N_BOUCLES;$i++) {
	if($i%MODULO==0) $bit = '1';
	$test += $bit;
	$bit = $bit<<1;
}
echo $test.' '.(getmicrotime()-$start).'<br/>';
?>

Mes Résultats :
1) au delà de 31bits, on ne peut compter que sur l'utilisation des librairies gérant les grands nombres. (on arrive sur le bit signé sur le bit 32)
2) GMP n'est pas géré par mon hébergeur, dommage, la fonction setbit était idéale pour mon utilisation.
3) En dessous de 32 bits, le décalage bit à bit est évidement beaucoup plus rapide.
4) Malgré tout, le PHP n'est pas du C et le décalage bit à bit n'est que "20 fois plus rapide" . Plus sérieusement, la fonction power est quand même rapide. Les multiplications régulières, le sont plus.
résultats :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
1000 BOUCLES
TEST1 1000 0.069514989852905   // résultat faux, 0.07 seconde
TEST2 133143986400 0.1068000793457 // résultat OK, 0.10 seconde
TEST3 133143986400 0.041554927825928 // résultat OK, 0.04 seconde
TEST6 224 0.0028469562530518 // résultat faux, 0.003 seconde

pour le stockage MySQL ma colonne est maintenant du type UNSIGNED BIGINT Et la table a été réalisée par un traitement similaire en PHP.

Edit :
mais durant mes essais j'ai eu courament usage de la fonction CONV('représentation binaire', 2, 10) pour convertir en SQL de la base binaire à un entier classique.
Attention à un détail très important, pour la récupération de la représentation binaire en mySQL on peut utiliser CONV(X,10,2) mais les "Leading 0" ne seront pas présents ! dans ce cas le changement de la colonne en UNSIGNED ZEROFILL devrait faire l'affaire.

Enfin pour les autres tests binaires j'utilise aussi (types & recherche) =recherche // Qui veut dire que l'ensemble recherche doit contenir la globalité de types.

[doof]

Ah c'est sur, s'il y a plus de 31 bits, le décalage aura de sérieux problèmes

Je ne connaissai pas la technique des les multiplications régulières, et ça risque d'être fort utile pour aller jusqu'à 64 bits (limitation mysql il me semble).

En tous cas, merci pour l'idée et toutes ces précisions, je sauvegarde ce précieux sujet avant qu'il ne passe à la trappe.