Optimisation Array
Alak
Membre
Bonjour,
Je vous expose la situation. J'ai une class Store :
import Foundation
import CoreLocation
class Store {
let name: String
let location: CLLocation
var distance: CLLocationDistance!
init(data: [String]) {
...
}
func updateDistance(userLocation: CLLocation) {
distance = userLocation.distanceFromLocation(location)
}
}
J'ai un array de store dont je connais la location, je connais ma location et je souhaite avoir un array des 10 stores les plus proches de moi.
J'utilise cette method :
func closestStores(location: CLLocation) -> ArraySlice<Store> {
for store in stores {
store.updateDistance(location)
}
stores.sort { $0.distance < $1.distance }
return stores[0..<10]
}
Je voulais savoir quel moyen plus optimisé vous auriez utilisé? (l'Array store a environ 1000 entrés non-ordonné)
Alak
Mots clés:
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Je ne suis pas sûr que changer la structure de tes données (en arbre ou graphe ou autre par exemple) puisse vraiment t'aider (ça pourrait être une idée pour rapidement couper dans l'arbre de décision tôt dans le parcours, façon algo A*, si tu vois que tu pars un peu loin dans les distances, mais le problème c'est que si un store A est à 10km de ta position et qu'un store B est à 10km du store A, ça peut vouloir dire que B est à 20km de toi, comme à 0km et juste à côté...)
A mon avis ce qui prend le plus de temps ce n'est pas tant l'algo de tri, mais plutôt le calcul de la distance sur chacun des 1000 stores. D'autant qu'un calcul de distance géodésique n'est pas aussi simple qu'une simple formule de pythagore.
Il y a sans doute moyen d'optimiser ça quand même, en découpant tes stores en zones dans un quadrillage de NxN km, et en ne considérant d'abord que les stores qui sont dans la même "case" que ta position à toi. Comme ça tu ne calcules la vraie distance que sur ces stores qui sont dans cette case, et pas sur les 1000 stores, donc ça limite le calcul de la distance à beaucoup moins de stores. Ensuite tu les tries, et si tu en as au moins 10 t'as fini. Si tu n'en trouves pas 10 dans ton carré, déjà fonctionnellement c'est à se demander si ça vaut le coup de les afficher (après tout, si les autres sont pas dans ton carré c'est qu'ils sont peut-être un peu trop loin de toute façon ?), mais si tu veux vraiment, tu peux étendre ta recherche aux carrés voisins, jusqu'à ce que tu en trouves assez.
Après, de là à savoir si ça vaut le coup de faire l'effort de mettre en place un tel algo, qui va un peu complexifier ton code, pour ça, ou pas, je suis pas sûr. Et faut aussi réfléchir si ce genre d'algol marche toujours aussi bien aux pôles (où la zone "voisine" de toi s'approche de moins en moins d'un carré et de plus en plus d'un triangle). Mais comme c'est certainement le calcul de distance qui est le plus consommateur, au moins réduire le nombre de stores que tu considères en faisant un filtrage grossier en première passe me semble utile.
Merci beaucoup de ta réponse Ali.
Mon cas était plus tot un exercise théorique.
Donc si ma liste de stores est toutes villes confondue, faire un premier filtre par ville puis calculer de distance ferait gagner en temps de réponse. (comparaison de String, plus rapide que le calcule de distance).
Ainsi moi j'habite à la frontière de Rennes, s'il y a un store à 500m de chez moi mais qu'il est à Cesson-Sévigné juste à côté de Rennes et pas officiellement sur la ville de Rennes, tu risques de le filtrer et de ne pas me le retourner !
D'où l'intérêt de quand même filtrer par coordonnées géographiques, mais la première passe de filtre ne va pas se faire sur la ville, mais plutôt sur un calcul du genre "if abs(store.latitude - location.latitude) < N && abs(store.longitude - location.longitude) < N" " qui est plus rapide que la formule de pythagore et encore plus rapide qu'un calcul de distance géodésique qui prend en compte ta latitude pour ajuster le calcul selon si tu es proche de l'équateur ou des pôles etc. Comme ça même le store qui est à côté de chez moi mais pas dans la même ville sera trouvé.
En regardant vite fait j'ai une idée mais je sais pas ce quelle vaut car je ne l'ai pas implementée.
L'idée serait un arbre binaire trié de n éléments. Tu le rempli quand tu as besoin, cad quand tu as encore de la place dans l'arbre ou quand tu as une distance plus petite que le max. Logiquement tu éjecte le max.
L'arbre serait genre
Donc ton code donnerait ça:
Il te reste qu'à comformer Store a Comparable et à implementer l'arbre.
J'ai pas calculé O parce que je suis pas bon pour faire ça mais d'instinct je dirait que c'est plus rapide que le sort.
C'est ce que je ferai aussi, faire un pré-découpage des stores par proximité géographique, pour ne pas examiner 1.000 positions dans la boucle de recherche.
Pour la petite histoire, il m'est arrivé d'être le point de référence géographique de la France. 8--)
Le point "0" de toutes les distances française (cartes, panneaux routiers, etc..) est une dalle sur le parvis de Notre-Dame, signalée par une plaque. Chaque fois que je passe dans le coin, je me place dessus quelques minutes, en prenant un air avantageux.
https://fr.wikipedia.org/wiki/Point_zéro_des_routes_de_France
Personnellement je calcule les distances au carré (dx*dx+dy*dy) sans utiliser le calcul de la racine qui prend du temps et je compare avec le carré de mon rayon d'action.
Ce qui n'est qu'une approximation qui ne marche que sur des distances à échelle réduite (échelle d'une région voire de la France au Max, mais plus la distance est grande plus cette approximation sera fausse) et que dans nos latitudes évidemment, beaucoup moins bien au Canada ou Groenland
Après en général suffisant pour un premier filtrage, mais faut être conscient de la limitation et que distance euclidienne et géodésique ne sont pas la même chose !
Sauf si tu es un Neutrino.
C'est surtout que le Neutrino n'a quasiment aucune interaction avec la matière ordinaire, ce qui lui permet de se déplacer en ligne droite, à travers la terre, au lieu de la contourner.
D'un autre coté, si on quitte le domaine de la mécanique classique, on entre dans celui de la mécanique quantique et ça devient compliqué. Les physiciens passent leurs temps à se disputer sur le nombre de dimensions existants dans l'univers, de 2 à 17 selon les modèles. Pas simple de calculer une distance dans un univers à 17 dimensions, dont la plupart sont recourbées sur elles-mêmes.
Je dispute légèrement ton analyse. La distance n'est pas vraiment une propriété du Store parce que le Store ne peut pas avoir une distance toute seule. On ne peut pas savoir ou calculer la distance sans la position de l'utilisateur ; du coup, la distance est plutôt une propriété d'une classe telle que DistanceCalculation :
On tourne un peu en rond là .
Dans ce cas on pourrait faire une extension. Peut-on mettre des variables dans les extensions en swift ?
Ou un pattern type façade pour représenter le fait que cette variable a une durée de vie limitée.
Il y a peut-être moyen de stocker la liste des boutiques les plus proches dans un fichier, pour ne pas faire une recherche à chaque fois. Et relancer un tri seulement si la position courante de l'utilisateur est différente de la dernière recherche, avec un seuil de déclenchement.
Si l'utilisateur est à 500 mètres de sa dernière recherche et que la boutique la plus proche était à 10 km, pas besoin de tout refaire.
Je l'ai fait, j'ai fait un system de significant location update en fonction de la boutique la plus proche.
D'un point de vu de l'architecture c'est vrai que l'a boutique n'a pas de distance, mais c'était plus pratique pour moi.
Pratique pour le tri mais pas pour l'affichage. Il va peut-être y avoir du code pour formatter la distance, peut-être une sous-vue avec juste les boutiques les plus proches.
Si c'est le cas, cela peut-être bien de prévoir une classe de modèle "proxy" pour stocker un pointeur vers le modèle store ainsi que la distance associée ; ainsi on pourra bien encapsuler les calculs et les méthodes de formattage pour l'affichage.
Du coup on pourra traiter ces objets comme des objets de modèle temporaire qu'on pourra mettre dans un tableau pour les trier et les afficher en tableau ou sur la carte, leur demander leur nom, leur position, et leur distance.
On retrouve le côté pratique d'avoir la distance dans le modèle et le côté propre du modèle sans donnée intermédiaire, une sorte de modèle "transient".
Question subsidaire : les Dictionaires sont-ils ordonnés dans swift ? Ce n'est pas le cas dans .NET où il y a deux classes : Dictionary et OrderedDictionary.
Oups ! Mais tu sais ce que je voulais dire
Oui oui, t'inquiète, et en plus tu as démontré que le copier-coller est surement la plus grande source de bugs.
Avoir un ViewModel qui fait proxy de l'objet modèle et rajoute juste les éléments nécessaires à la logique métier et à l'affichage.
Ce qui est embêtant, je ne l'ai pas copié-collé, je l'ai tapé directement du cerveau
Faut-il en déduire que ce cerveau est bugé ? Les nounous anglais ont-ils le même problème que les vaches anglaises ?
nounous ou nounours?
Meuh !
Voici un petit éclairage mathématique :
Notons les 3 distances suivantes entre 2 points A(x_A, y_A, z_A) et B :
d2(A,B ) = racine carrée de (x_A-x_B )^2+(y_A-y_B )^2+...
d∞(A,B ) = max ( |x_A-x_B|, |y_A-y_B|, ...)
d(A,B ) = la vraie distance (la distance géodésique)
Première chose, intuitivement, je pense qu'on a (en considérant la Terre sphérique)
d2(A,B ) ≤ d2(A,C) <=> d(A,B ) ≤ d(A,C). Donc, trier avec d2 ou avec d, c'est pareil.
Deuxième chose, on a :
On a : d∞ ≤ d2 ≤ sqrt(3) . d∞
Ce qui peut permettre de d'abord faire un tri avec d∞ et de pouvoir exclure certains stores.
Voilà !
Tu t'arranges pour que ton tri se fasse en live, tu fais apparaà®tre les résultats les meilleurs au fur et à mesure qu'ils sont calculés, avec un indicateur du pourcentage de complétion.