[SQL] Génération de coordonées aléatoires inutilisées

[Zenol]

Bonjour,

Je poste ici car j'ai un petit problème qui me tracasse :
J'ai une table qui liste des objets physique auquel est associer des coordonnées x, y et z, mais ne peut y avoir qu'un objet à chaque coordonnée.
Seulement, je voudrait ajouter un objet et le positionner de façon aléatoire en x, y et z. Mais je me demande comment gérer le fait qu'il ne peut y à avoir qu'un objet par emplacement.

La solution la plus simple serait de générer au hasard une position x;y;z puis de vérifier qu'elle n'est pas déjà prise, seulement ceci devient problématique quand il ne reste plus que quelques dizaines d'emplacement parmi les 125 000 ^^

Donc, auriez vous une meilleur solution en terme de performance? Peut-être une instruction SQL permettrait de générer ces termes de façon automatique l'ors de la requette insert?

[u115rcu]

Salut,
déplace le problème ;-)
Soit x,y,z défini dans E^3, soit F^3 l'ensemble des points x,y,z qui existent déja.
Soit alors E/F, c'est à dire E privé de F, c'est à dire tous les points qui ne sont pas pris.
Tu divises E/F en trois sous espace efx efy efz, qui contienne la liste des points encore libre (si le nombre de point est sup a la moitié) ensuite tu fais un random sur l id de ces 3 listes.

Cette première proposition est assez lourde car tu dois stocker dans trois bases toute les valeurs libres!

Sinon faudrai optimiser ca en faisant un code évolutif et donc en incluant le test dont tu parlais si c'est déja pris on suit la loi d'évolution qui est faite de telle sorte qu'on tombe forcément et le plus vite possible sur un trou..

Mais je te conseille d'essayer de ruser en perdant une dimension et en faisant des test qui combien les coordonnées x y z pense par exemple au polynome aX²+bX+c avec a b et c tes coordonnées.

Bref quelques pistes mais ton problème demande une réflexion a mon avis.

[Zenol]

Envoyé par u115rcu

Salut,
déplace le problème ;-)
Soit x,y,z défini dans E^3, soit F^3 l'ensemble des points x,y,z qui existent déja.
Soit alors E/F, c'est à dire E privé de F, c'est à dire tous les points qui ne sont pas pris.
Tu divises E/F en trois sous espace efx efy efz, qui contienne la liste des points encore libre (si le nombre de point est sup a la moitié) ensuite tu fais un random sur l id de ces 3 listes.

Cette première proposition est assez lourde car tu dois stocker dans trois bases toute les valeurs libres!

Sinon faudrai optimiser ca en faisant un code évolutif et donc en incluant le test dont tu parlais si c'est déja pris on suit la loi d'évolution qui est faite de telle sorte qu'on tombe forcément et le plus vite possible sur un trou..

Mais je te conseille d'essayer de ruser en perdant une dimension et en faisant des test qui combien les coordonnées x y z pense par exemple au polynome aX²+bX+c avec a b et c tes coordonnées.

Bref quelques pistes mais ton problème demande une réflexion a mon avis.

Heu wé.... tout comme tu a dit...

Sérieusement j'ai un peut de mal à suivre

Utiliser des coordonnées en un seul nombre un peut comme l'on fait pour les vecteurs? (Avec X valeur maximum de c et X² = X*Valeur maximume de b ? [Dans ce cas la valeur maximum de c serait quelque chose comme 14 et celle de b quelque chose comme 999 ^^])
Impossible d'utiliser une tel méthode, je doit à partir de l'objet (lier à un propriétaire via un champ ID) pouvoir récupérer sa position.

Faire une liste des coordonnées disponibles et ensuite faire un random? C'est lourd mais meilleur que la première solution que j'ai, effectivement.

J'aurai plutôt vu quelque chose dans le genre :

Insertion `` VALUES(Nombre aléatoire ( Sélection des coordonnées libre))

Une requette qui relègue le tout à MySQL, mais je ne sais pas si c'est possible.

Seulement pour la sélection c'est loin d'être limpide... Déjà, comment sélectionner les valeurs qui n'existent pas dans la table? (Connaissent le minimum et le maximum permit des champs)
Comment faire une recherche qui porte sur 3 champs avec des conditions "entre eux" (10;1 est différent de 11;1 et de 12;1, bien qu'à chaque fois z=1 :s)

[u115rcu]

J'ai pas été très clair je dois l'avouer et ce n'était pas une solution mais une vision des choses peut etre un peu trop mathématique.
Pour faire ta table des existants si cette solution te semble a tester alors parcours peut etre la plage de solution en partant du minimum existant.
Prenons un exemple sur X.
Tu fais la recherche du minimum en x existant soit xmin ce mini.

Au fait tes axes sont de type entier? je suppose que oui.
Alors tu fais alors un pointeur que tu places initialement sur xmin
et tu es dans la boucle de rang 0:


Fonction recherche minimum sur la coordonné i: i=X Y ou Z
Valeur du minimum en i:Imin >>Faire une requette SQL pour le trouver
Fonction i libre minimum;
I libre minimum>> $pointeurI=$Ilibr

LBL1 (etiquette)
recherchemini(X)
libremini(X)
LBL2
recherchemini(Y)
libremini(Y)
LBL3
recherchemini(Z)
libremini(Z)

Pour que ca marche et qu'on trouve tout les points libres il faut pouvoir boucler cela donc je modifie les fonctions en leur ajoutant la ccordonné a partir de laquel il cherche le mini, au début pour chaque axe cette coordonné est au mini ensuite on la calle par rapport au pointeur+1
soit alors la fonction recherchemini(I) qui devient recherchemini(I,Pointeur)
ce qui donne pour mon idée le schéma suivant:

Fonction recherche minimum sur la coordonné i: i=X Y ou Z
Valeur du minimum en i à partir du pointeur:Imin >>Faire une requette SQL pour le trouver
Fonction i libre minimum;
I libre minimum>> $pointeurI=$Ilibr

LBL1 (etiquette)
recherchemini(X,$pointeurX(n))
libremini(X) >> Renvoi $pointeurX(n+1)
LBL2
recherchemini(Y,$pointeurY(n))
libremini(Y) >> Renvoi $pointeurY(n+1)
LBL3
recherchemini(Z,$pointeurZ(n))
libremini(Z) >> Renvoi $pointeurZ(n+1)

Le bouclage maintenant, tu es sur le premier X non pris alors ca signifie que tu as une droite solution donc tout couple Y Z convient, tu dois donc ajouter une quatrième colone pour donner la dimension de la solution ce qui permettra d alleger le code au départ

Table emplacement libre:
ID EMPLACEMNT
ID X
ID Y
ID Z
Dimension

Si tu détecte donc au premier test sur X qu'un X est jamais pris alors tu rentre (prenons X=10)

1,10,NA,NA,2 2 signifie que tu es sur un plan solution avec comme définition le X (Note: tu n'a pa besoin de ce nouvelle colone finalement il suffit de compter le nombre de NA:Non attribué mais bon..).

Donc a ta boucle du label 1 (LBL1) finalement tu va repérer tout les plan solution
ensuite dans un second temps tu regarde pour les X qui ne sont pas plan solution et tu passes a Y
pour Y meme histoire tu va repéré cette fois ci les droites solutions (si un Y est pas pris alors tu as tout les Z solution associé a ce Y, attention on es indexé aussi par la structure sur X pour le balayage de toute les solutions).
Enfin tu arrives au Z.

Donc ce qui est exposé au dessus te permet de générer toutes les positions libre mais au finale tu n'a peut etre pas besoin de les avoir toute et de tirer dedans au hasard, on voit bien que c'est super long!
Une autre idée serait d utiliser le concept si dessus en tirant la position de départ des pointeurs au hasard! ainsi tu conserves le hasard et tu arrete en plus le code que j'ai exposé dès que tu as soit un plan solution, soit une droite solution ou soit un point.
Si tu as un point alors le tour est joué.
Si tu as une droite alors il te reste a tirer au hasard dessus.
Si tu as un plan tu tire deux coordonnées au hasard.
Soit si on revient au code:

Fonction recherche minimum sur la coordonné i: i=X Y ou Z
Valeur du minimum en i à partir du pointeur:Imin >>Faire une requette SQL pour le trouver
Fonction i libre minimum;
I libre minimum>> $pointeurI=$Ilibr

Je tire au sort le point de recherche de départ
ce qui m initialise mes pointeurs
$pointeurX(n=0)
$pointeurY(n=0)
$pointeurZ(n=0)
LBL1 (etiquette)
recherchemini(X,$pointeurX(n))
libremini(X) >> Renvoi $pointeurX(n+1)

>>Ici si on a trouver une place libre:
Alors Exit de la recherche (et alors tu as un plan solution)
sinon on remet le pointeur X a $pointeurX(n=0) on passe a la seconde boucle
(attention met un compteur dans la boucle des X)

LBL2
recherchemini(Y,$pointeurY(n))
libremini(Y) >> Renvoi $pointeurY(n+1)
IDEM passons au cas ou les trois donne aucune solution de dimension sup ou égal a 1
Alors tu te retrouve dans un schéma de balayage par incrément genre si tes pointeurs étaient au départ tiré au hasard a (5,8,16) et que aucun X Y Z n est libre (indépendament) alors ma structure de code va évoluer en balayant point par point c'est la son point faible mais tu peux y remédier mais si on pousse plus loin je ne peux pas trop te dire car il faudrait connaitre le but de la chose.

METHODE 2:
Car je pense a une autre solution la voici:
Soit N le nombre de valeur entière dans X (pareil pour Y et Z par exemple si X va de zero a 10 tu as N=11)
Si tu choisi X Y et Z ton idée pour te renseigner sur ce choix est de faire un select avec as t on de pris e point (Xchoisi,Ychoisi,Zchoisi) mon idée a moi est plutot avec ce (Xchoisi,Ychoisi,Zchoisi) de regarder :
Primo:Combien de point existant on la coordonné Xchoisi soit Nx ce nombre
Seoncdo idem avec Ychoisi >>Ny
Tertio:idem avec Zchoisi: >>Nz
Alors tu regardes quelle est le m1=min(Nx,Ny,Nz)
Alors tu gardes cette valeur si cette valeur vaut N soit 11 dans notre exemple alors aucun point n a cette valeur c'est fini
sinon tu t'es placé dans les conditions optimum pour poursuivre (je te montre sur un petit exemple après).
tu regarde alors m2=min(Ny,Nz) idem tu fixe la plus petite
on a donc en prenan Nx et Ny comme exemple de plus petite valeur de Nx,Ny,Nz le point de départ de recherche (Xchoisi,Ychoisi,?) tu balaye alors tout les Z.
Si tu trouves rien tu divises en deux:
Soit tu sais que tu as encore beaucoup de place de libre alors tu retires au hasard X Y et Z
Soit tu sais qu'il n y as plus trop de place de libre alors tu fais évoluer linéarement ta recherche soit nouveau X=Xchoisi+1 par exemple.


Prenons un exemmple sur (X,Y) avec come valeur de X de 0 a 4 et Y de 0 a 4
les valeurs suivantes sont prises:
(0,1)
(1,0)
(1,3)
(1,4)
(1,5)
(2,4)
(3,1)
(4,2)
(4,0)

Je tire au hasard: (1,0) mince il existe :
Alors Nx=3 et Ny=1
J'ai dis dans ma logique que tu avait une recherche optimum d une solution
en gardant le N mini soit ici en gardant le Y=0 en effet:
Les points restant pour Y=0 sont au nombre de 4-Ny=3 alors que les points restant pour X=1 sont au nombre de 4-Nx=1
Donc tu te place a un point (?,0)
La je t'ai dit tu recherches sur toute la place en faisant varier la dimension non fichier ici X, solution simple tu fais avancé de 1 en 1 en partant de X=0 donc tu testes: (0,0) coup de chance c'est libre !
Mais la aussi tu peux optimser en ne partant pas au hasard mais par rapport au chiffre le moins pris en X en faisant une petite requete tu sors qu'en X on a
0 pris une fois
1 pris 4 fois
2 pris une fois
3 pris une fois
4 pris deux fois
Alors tu testes d'abord les points qui sont pris le moins de fois donc 0 2 et 3...


Voila bon j'arrete la ce sujet est très interessant j'espere t'avoir aider un peu meme si je ne te donne pas de code directement.

(PS je viens de me relire ma méthode 2 est la plus interessante je trouve, rajoute comme meme un test pour savoir si les coordonnés sont prises directement après avoir pris les points)

[u115rcu]

En tout cas je suis intimement persuadé que la piste des polynomes est la meilleure...

[Zenol]

*Murmure : Vous auriez la version sous titrer? *

Hum, pour la première solution ce n'est déjà pas très claire. En plus ton pseudocode ne veut pas dire grand chose pour moi ^^'

Déjà, à la place des étiquettes, tu pourrait pas utiliser des boucles? :s
Les >> ça me rappelle les opérateurs de flux C++ donc je voit pas trop ce que tu veut dire avec O_o
Les pointeurs pour toi c'est un identifiant qui correspond au premier élément d'une liste?
$truc(var) c'est quoi? Un pointeur de fonction? Un tableau? Une variable toute simple? Une fonction?
J'ai aussi un peut de mal à voir là ou commence les fonctions/là ou elles se finissent O_o *Pas contre un chouilla d'indentation*

Je ne veut pas stocker les coordonnées des emplacements libre dans une autre table, ça rendrait le tout encore plus lourd que ça ne l'est déjà.

Point droite plan espace, c'est une façon de voir les choses ^^ En réalité les coordonnées correspondent à boite/tiroir/emplacement mais ce qui reviens au même.

Les emplacements prit doivent l'être de manière aléatoire. Normalement, arriver à moitié de remplissage, le volume doit être remplit d'objet, un peut comme un nuage de poussière.

Pour l'exemple, NA c'est quoi...? ^^

Ensuite pour la deuxième partie là je suis vraiment perdu :s

Je suis peut-être un peut bébète mais je perd le file de l'histoire >.<

Pour ce qui est d'utiliser x + y*max_y + z*max_x*max_y ça parait effectivement simple.
Il suffirait de faire une liste des nombres disponible(Ou, des 300 premiers nombres disponible obtenu en partant de manière aléatoire d'un endroit de la table(Pour choisir l'endroit d'ou on part, on comptera le nombre d'enregistrement déjà existant) et d'en tirer un au hazard.
Mais après, comment à partir d'un nombre tel que 73204 qu'il proviens de 69930+3262+12 provenant de 12+233*14+5*14*999 ?

Edit : Trouver!

73204%14 = 12
(73204-12)/14 % 999 = 233
(73204-12-233*14)/(14*999) = 14

Heu....
n=x + y*max_x + z*max_x*max_y
n%max_x = x
(n-x)/max_x % max_y = y
(n-x-y*max_x)/(max_x*max_y) = z

Bah... alors suffit de faire un select limiter à 300 de `coordx` + `coordy`*14 + `coordz`*14*999 as `Position` ?