Discussion :

[fadex]

Bonjour

Je veux écrire un programme php pour sélectionner 16 points aléatoires à partir de 400 points dans ma base de données

(tableau de points: id - Titre - latitude - longitude).

exemple de point :
id : 1
titre : un titre
latitude : 37.9824
longitude: -87.5781547

exigences, 16 points aléatoires, dont chaque point est au moins à 1km de l'autre point.

par exemple:

si le programme sélectionne 3 points A, B et C.

la distance entre les point doivent être:

A et B >= 1 KM

A et C >= 1 KM

B et C >= 1 km

ps : j'ai crée une table distance sur la quelle il y a la distance entre chaque deux points :

exemple :

point_1 : 1
point_2 : 2
distance : 1200

point_1 : 3
point_2 : 6
distance : 800

ma question est comment sélectionner les 16 points aléatoires, dont chaque point est au moins à 1km de l'autre point.

Merci d'avance

[Benjamin Delespierre]

Quelle est ta question ?

[fadex]

ma question est comment sélectionner les 16 points aléatoires, dont chaque point est au moins à 1km de l'autre point.

[Benjamin Delespierre]

Une solution simple serait de récupérer toutes les cordonnées éloignées d'1km, de les mettre en cache, de les mélanger et d'en sortir 16

[fadex]

tu peux développer plus votre solution ( simple ) ??
- vu que je ne pence pas que c aussi simple

[Benjamin Delespierre]

Je pensais à quelque chose dans ce genre (en utilisant PDO):

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
<?php
define("CACHE_FILE", "coords.cache");
 
if (!is_file(CACHE_FILE) || !@include(CACHE_FILE)) {
	$query = "SELECT x,y,z FROM table WHERE blah";
	if (!$results = $pdo->query($query))
		throw new RuntimeException("Query execution fails");
	$data = $results->fetchAll(PDO::FETCH_ASSOC);
	// écriture du cache
	if (!file_put_contents(CACHE_FILE, '<?php $data='.var_export($data,true).';')) {
		throw new RuntimeException("Could not write cache file " . CACHE_FILE);
	}
}
 
// sait on jamais
!empty($data) or $data = array();
 
shuffle($data);
$firsts = array_slice($data, 0, 16);
 
var_dump($firsts);

A toi de jouer

[Marc3001]

Je pense que tu dois y aller point par point.

1/ Tu récupères un point aléatoire en base (via point)
2/ Tu récupères tous les points à au moins 1 km de celui récupéré en 1/ (via distance )
3/ Tu sélectionnes un point (ou plusieurs) au hasard dans la liste en 2/
4/ Tu recommences depuis le 1/ avec le (ou les) points récupéré(s) en 3/

[Benjamin Delespierre]

Tu peux aussi utiliser l'algorithme de Dijkstra, ce serait marrant en plus à implémenter

[Marc3001]

Tu peux aussi utiliser l'algorithme de Dijkstra, ce serait marrant en plus à implémenter

J'suis pas sûr que ça colle avec le besoin....

[Benjamin Delespierre]

Non bien entendu, ce serait utile s'il voulait trouver un parcours de points éloignés de 1km (en modifiant un peu l'algo) plutôt qu'un parcours aléatoire.

[ericd69]

lol benjamin scéance

dijkstra ou A* sont des algorithmes de parcours de GRAPH...

tu te fais une procédure stockée qui:

• crée une table temporaire temp(idpoint int)
• tant que count(idpoint)<16 faire:
  
  • utiliser la requête de génération de point
  • si un point a été généré l'insérer
• faire un select sur la table temporaire

la requête serait un truc du genre:

Code sql :

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

1
2
3
4
5
6
7
8
9
10
 
select count(t.idpoint)
from temp t
inner join distance d on d.point_1=t.idpoint
and d.point_2=
    (select point_2
    from distance
    where distance>1000 and point_1>=(select max(id)*rand() from points)
    limit 1)
and d.distance>1000

mais vu que l'optimiseur mysql bug parfois avec les sous requête on va diviser pour mieux régner...

la procédure serait:

Code sql :

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
delimiter $$
drop procedure points$$
create procedure points()
begin
    declare nb,i int default 0;
    declare b bool;
    create temporary table temp(idpoint int);
    while nb<16 do
        -- on récupère un point au hasard qu'on stocke dans i
        select point_2 into i
        from distance
        where distance>1000
            and point_1>=(select max(id)*rand() from points)
        limit 1;
        if nb=0 then
            insert into temp(idpoint)values(i);
        else
            -- on teste si le point est à 1000m mini de ceux déjà sélectionné
            select count(t.idpoint) into b
            from temp t
            inner join distance d on d.point_1=t.idpoint
                and d.point_2=i
            and d.distance>1000;
            if b then
                insert into temp(idpoint)values(i);
            end if;
        end if;
    end while;
    select idpoints from temp;
end$$
delimiter ;
-- appel
call points;

ça devrait marcher... j'ai pas testé...

[stealth35]

ta table distance est complète ?

si t'as 3 points A B C

y'a :

A B distance
A C distance
B A distance
B C distance
C A distance
C B distance


?

sinon 16 requêtes c'est pas la mort, vaut mieux lui passer plein de petites requête qu'une grosse

[ericd69]

logiquement il a environ 400²=160000 combinaisons donc lignes (en fait, la formule exacte est n(n-1) donc 400*399=159600 lignes exactement vu qu'il a 400 points)

mais le pb c'est que tous les points sélectionnés doivent être à 1000m mini les uns des autres... d'où la boucle pour retirer des points tant qu'on en a pas 16 qui répondent à la contrainte...

en plus là y a 1 seul échange mysql/php donc moins de bande passante et de latence à cause de ça

[stealth35]

en plus là y a 1 seul échange mysql/php donc moins de bande passante et de latence à cause de ça

non ça mettra plus de temps

[Marc3001]

non ça mettra plus de temps

Je pense que c'est tellement dépendant des requêtes (jointures, tris,...) que seul un bench ou une analyse des plans d'exec peux répondre à cette question.

[NoSmoking]

Bonjour,

comme l'a dit Marc3001

1/ Tu récupères un point aléatoire en base (via point)

puis tu fais ta requête comme vu sur ce post http://www.developpez.net/forums/d11...s/#post6266103, en adaptant la distance et le nombre de retour.

[ericd69]

non ça mettra plus de temps

Tu te bases sur quoi pour dire ça?

Petite réflexion:

Quoiqu'il arrive et quelque soit l'algorithme, étape 1:

• échange(s) TCP/IP: requête DNS (ou résolution local si sur même host)... rappel: échange limité par la connexion réseau, en général entre 100Mo et 1Go de bande passante maxi en interne ou avec fibre et si tu es en ADSL 20Mo/s max mais en réalité plus souvent 2 à 5 car toute la bande passante n'est jamais utilisée...
• connexion tcp/ip (même en local)
• échange tcp/ip: identification

étape 2 (à chaque requête SQL):

• échange tcp/ip: envoi requête
• analyse requête (interprétation, optimisation, exécution)
• mise en cache résultat coté mysql
• échange tcp/ip: envoi résultat
• mise en cache coté php

Le problème vois tu, c'est que le goulot d'étranglement c'est le réseau... car tu as des temps d'accès niveau disque dur entre plusieurs centaines de Mo/s (SATA DD mécaniques) à plusieurs Go/s (en SATA SSD)... et selon la taille de ta requête, du coup, l'échange et la double mise en cache peuvent devenir plus long que l'exécution de la requête...

Dans la conception classique php/mysql, tu as:

• l'étape 1
• autan d'étape 2 que tu as besoin de fois d'interroger la BD, l'algorithme se partage entre php et mysql

Dans une conception plus avancée (attention, tout ne pouvant pas être fais coté mysql comme les remplacements à base de regex par exemple...), tu as:

• l'étape 1
• l'étape 2 (l'algorithme est entièrement coté mysql donc plus d'échanges tcp/ip et de double bufferisation des résultats intermédiaires coté php et mysql). le langage procédural SQL est au moins aussi rapide (voir bien plus que php, car plus simple)

Donc quand tu as des traitements qui peuvent être lourds et/ou répétitifs sans réellement avoir besoin de faire un truc coté php pourquoi ne pas faire ça finalement coté mysql et s'éviter des échanges TCP/IP et mises en cache inutiles?

Et là je rappelle le problème tirer 16 points aléatoire parmi 400 tous distants au moins de 1000m les uns des autres...

un algorithme s'analyse en terme de nombre d'opérations (complexité):

• au mieux
• en moyenne
• au pire

[stealth35]

parce que la procédure présenté est compliquer et demande beaucoup de ressource, une connexion demande pas grand chose un retour avec un petit résultat non plus.

faudrait que je retrouve le brench, mais sur certain fonction de PHP (genre de Date) c'est pourquoi plus rapide de se connecté au serveur mysql lui dire de faire la même chose, renvoyé le résultat et l'afficher

c'est beaucoup moins couteux de récupérer plein de petit résultat que 1 gros, c'est que fait Doctrine par exemple, au lieu de faire un JOIN pour récupéré les donnée, tu fais un requêtes préparée sur chaque ligne

[ericd69]

compliqué?

beaucoup de ressources?



tu dois pas souvent aller voir sur le forum mysql notamment la partie procédurale...

parce que ton script php interprété à la volée il en consomme pas?

elle consomme moins de ressources que les 16 allers-retours (étape 2) de ta solution (au mieux car en moyenne tu risques de devoir en faire plutôt beaucoup plus que 16)... du fait, que plus tu va tirer de points plus tu vas avoir des points qui ne seront pas bon avec la conditions de distance, t'obligeant à recommencer le tirage...

[stealth35]

Non 16 requête (et peu être même moins), il suffit de de prendre un point au hasard et tourner en spirale autour du point

EDIT : non c'est nul