Bonjour,
 
J'affiche sur une google map des points dont les coordonnées gps sont stockées dans une base mysql.
Il y a beaucoup de points (plusieurs milliers), alors je ne charge que ceux qui sont dans le cadre visible par l'utilisateur.
Si celui-ci se déplace sur la map, je fais une requete ajax qui va chercher les nouveaux points à afficher.
Comme je ne souhaite pas que le serveur renvoit plusieurs fois des points que l'utilisateur a déjà sur sa map (ce qui serait inutile), je souhaite utiliser une structure afin de permettre au serveur de déterminer si un point a déjà été envoyé ou non.
Donc a chaque nouvelle requete ajax, le serveur fait une requete mysql et récupere les points qui correspondent à la nouvelle position de l'utilisateur.
Ensuite, point par point, il regarde dans cette structure s'il a déjà envoyé ce point (la comparaison se faisant par l'id du point).
Si oui, il ne fait rien. Si non, il ajoute ce point dans la liste d'envoi, et il l'ajoute dans la structure.
 
J'ai commencé avec un array() classique. Pour chaque point, le serveur se tape la recherche itérative sur toute l'array.
Il existe sans doute mieux.
 
J'ai ensuite utilisé un arbre binaire.
Le problème, c'est que les id de la requete viennent en ordre croissant, vu que la requete mysl n'impose aucun ordre.
Du coup, le point n+1 est toujours plus grand que le point n. L'arbre se remplit donc toujours du meme coté, et il finit par devenir une grande liste chainée, et on perd tout l'avantage de l'arbre, qui n'est efficace que s'il est a peu pres équilibré.
 
Je me suis donc tourné vers les AVL, qui se rééquilibrent systématiquement à chaque ajout.
 
 
Mais rien n'y fait, aucun de ces deux arbres ne va aussi vite qu'avec l'array, chronometre à l'appui.
La solution avec l'array va environ 3 fois plus vite...
 
Hypothèses :
 
 
- Peut-être est-ce du au fait que l'array est un type natif, et que les classes des arbres doivent etre lexées, parsées et exécutées ?
 
- J'ai fait mes tests avec environ 2000 points. Peut-être qu'à cause de cette limitation citée ci-dessus, les arbres ne deviennent rentable qu'à partir d'un certain important nombre de points ?
 
- L'insertion dans un AVL est assez lente, puisqu'il faut à chaque fois rééquilibrer l'arbre ?
 
Pouvez-vous me donner quelques pistes, ou m'indiquer une structure plus adaptée ?
 
Merci d'avance  

Je pense que t'as moyen d'avoir les coordonnées de la zone affichée et probablement celle de la nouvelle zone quand l'utilisateur se déplace.
 
Tu peux donc calculer les coordonnées de la nouvelle zone pour laquelle il manque les points à afficher (calcul d'intersection de 2 rectangles ). Ensuite, plus qu'à faire une requête sql sur ta BD pour trouver tous les points compris dans la zone à laquelle il manque les points et t'envoies le tout sous forme d'un array. Pas besoin de structure particulière à priori...

Oui je viens de penser à ca à l'instant même    
 
Je pensais garder juste les coordonnées des rectangles déjà stockés, et les exclure de la requete directement.
Je vais plancher la dessus, et je reviens aux news
 
Merci  
 
 
EDIT : Par curiosité, tu as un avis sur la lenteur de l'utilisation des arbres en php ? C'est curieux que ca soit plus lent que la liste...  

En général, j'évite autant que possible de faire des traitement sur des grosses structures de données php. Je préfère, pour les perfs, faire plus de traitement en BD et stocker le résultat final dans un tableau associatif php (sans post traitement si ce n'est son affichage ou transmission).
 
Pour info, j'ai préféré faire calculer à Mysql le produit de 2 grosses matrices (5000x4000) plutôt qu'à php, ça allait nettement plus vite

Oki je prends note.
Ca fonctionne tres bien en sauvegardant les rectangles.
Par contre la requete risque de grossir au fur et a mesure que l'utilisateur parcours la map.
Je réflechissais à un moyen de déterminer si le nouveau rectangle se supperpose entierement aux autres (ie: inutile d'aller chercher des nouveaux points).
Mais à part des méthodes mathématiques chronophages, rien ne me vient à l'esprit...

ben je t'as dit, tu récupères les coordonnées de la zone visible courante. Quand l'utilisateur se déplace, tu récupères, les nouvelles coordonnées de la zone visible. Tu calcules la portion de la nouvelle zone qui est disjointe de la précédente : ça va te donner un rectangle plus petit que la zone couramment affichée ou alors la même si l'utilisateur a fait un "grand" déplacement. Après, plus qu'à récupérer les points de la zone que tu viens de calculer

Si j'enlève de mon nouveau rectangle toutes les zones couvertes par les précédents, je n'obtiens pas forcément un rectangle.
Si l'utilisateur se déplace en diagonale, cette zone aura une forme de croissant, inexploitable en sql

La zone de visualisation n'est pas rectangulaire

Si, mais si je ne me déplace que d'un centimetre sur la map, je veux éviter de renvoyer les points déjà envoyés qui sont à la fois dans l'ancienne et la nouvelle zones.
Je ne peux pas me contenter de renvoyer tous les points de la nouvelle zones.

 
J'ai l'impression que soit tu comprends pas ce que je veux dire, soit c'est moi qui comprends pas ton pb. Voici un petit schéma pour expliquer ma pensée :

 
La zone noire est la zone affichée précédemment, la rouge, la nouvelle zone suite à un déplacement de l'utilisateur et en bleu, la zone que tu calcules pour laquelle tu vas devoir afficher les nouveaux points. Alors effectivement, la zone calculée n'est pas un rectangle à chaque fois, ça peut être la composition de 2 rectangles.

On s'est bien compris. Mais ca deviens compliqué quand il y a plus d'un ancien rectangle.
 
En bleu, les zones déjà visitées, où les points sont déjà chargés.
En rouge, la nouvelle zone.
En rayé la zone dans laquelle les points devront être envoyés.
 

 
Comme tu le vois, la forme deviens compliquée, et la génération des conditions SQL est assez compliquée, puisqu'elle n'utilise que des comparaisons de coordonnées.

Je vois ton pb. Dans ma méthode, je ne faisait le différentiel qu'avec la zone N-1. Toi, tu sembles vouloir le faire sur toutes les zones que l'utilisateur a visités depuis le début de sa navigation. Ca risque de fortement compliquer les choses :
1) en cas de longue navigation, le navigateur va se retrouver avec une liste de points énorme (potentiellement en tout cas) en RAM
2) si l'utilisateur ouvre un nouvel onglet et commence une nouvelle navigation, y'a pas un risque que ton appli se mélange les pinceaux entre les données à envoyer aux différents onglets du navigateur?
3) certes, avec ma méthode, on va renvoyer potentiellement plusieurs fois le même point au cours de la navigation (si l'utilisateur fait des va-et-vient). Mais si des points ont été créés entre-temps, il aura les données à jours alors que dans ton cas, va falloir gérer ce cas de figure...

1) Oui Je n'ai pas encore trouvé de solution idéale pour éviter d'afficher tous les points. J'ai essayé de faire du clustering, mais c'est pas très beau visuellement.
 
2) Très bonne remarque. Pour ce qui est des requete ajax, normalement il n'y a pas de confusion. Par contre les rectangles sont stockés en session, donc si l'utilisateur ouvre un deuxieme onglet et commence à naviguer sur la map, les points affichés dans le premier onglet n'apparaitront pas sur le deuxieme.
Je vais faire un systeme d'id unique à chaque page. Ainsi il y aura 1 tableau de rectangle par onglet.
 
3) Ce point là n'a pas d'importance. Les points sur la maps sont des lieux statiques et qui ne changeront probablement jamais

Perds pas de vue qu'un algo compliqué peut amener à dégrader le temps de réponse par rapport à un algo simple. Le mien à l'avantage qu'en 2 requêtes SQL, t'as l'ensemble des nouveaux points à afficher.
 
Toi, vu la forme complexe de la zone, tu vas déjà en baver pour la calculer puis tu vas devoir faire x requêtes SQL (du reste, bonjour pour en déduire les requêtes à partir du contour de la forme ). Du coup, pas dit que ton temps de réponse soit meilleur. En plus, vu la complexité de l'algo, tu auras plus de risques de bugs et va compliquer la maintenance, pas le mien
 
Je pense que ce qui va faire gagner en perfs ou pas, c'est le nb de points en moyenne que tu dois afficher dans en zone. Si c'est qq points voire qq dizaines, le mien devrait être plus adapté. Si t'es dans les centaines, l'économie en bande-passante devrait faire que ton algo sera préférable...
 
Mais franchement, si tu te poses ce genre de question pour savoir si au lieu d'en envoyer 10, ton algo va faire que t'en enverras plus que 5-6, là, tu te prends la tête pour rien

Sur certaines région, c'est de l'ordre de plusieurs centaines. Donc je ne pense pas que ce soit si négligeable que ca
Là où je compte gagner en perf, c'est en faisant une synthese plus légere des points, afin d'éviter au serveur de devoir envoyé 2000 points d'un bloc.

Effectivement, si c'est dans les centaines, ton algo se justifie. Après, voir aussi du côté d'un système de mise en cache commun aux utilisateurs pour éviter de rechercher dans la BD. Si y'a des zones demandées et déjà servies en points, tu peux prendre dans le cache, sinon dans la bd puis mise en cache et envoi à l'utilisateur...

Le problème c'est que les zones sont rarement exactement à la même position (Ce n'est pas une grille avec des unités quantifiées). Par conséquent cette optimisation risque de couter cher en espace (stockage de chaque point par rectangle stocké) et n'apporte que peu d'amélioration (les cas de réutilisation seront très improbables).