Optimisation Array

AlakAlak Membre
août 2015 modifié dans Objective-C, Swift, C, C++ #1

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:

Réponses

  • AliGatorAliGator Membre, Modérateur
    Tu n'as pas vraiment de solution magique, car l'ordre de tri des stores changera à  chaque fois en fonction de ta position (c'est pour ça que tu fais un updateDistance() d'ailleurs) et nécessitera un re-tri.

    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.
  • AlakAlak Membre

    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).


  • AliGatorAliGator Membre, Modérateur
    Oui par exemple. Après ne filtrer les stores que par ville d'abord pour limiter le nombre de stores à  trier par distance, c'est bien, mais utiliser la ville comme critère de filtre est un peu violent.

    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



    protocol SortedTree<T: Comparable> {
    var min: T { get }
    var max: T { get }
    var array: [T] { get }

    init(capacity: Int)

    /// Ajoute l'élément et remplace min par son successeur.
    mutating func appendMax(element: T)

    /// Ajoute l'élément et remplace max par son prédécesseur.
    mutating func appendMin(element: T)
    }

    Donc ton code donnerait ça:



    func closestStores(location: CLLocation) -> Array<Store> {

    var tree = StructThatImplementSortedTree<Store>(capacity: 10)

    for store in stores {
    store.updateDistance(location)
    if store < tree.max {
    tree.appendMin(store)
    }
    }

    return tree.array
    }

    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.


     


     


  • DrakenDraken Membre
    août 2015 modifié #6


    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.

     




    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



  • Oui par exemple. Après ne filtrer les stores que par ville d'abord pour limiter le nombre de stores à  trier par distance, c'est bien, mais utiliser la ville comme critère de filtre est un peu violent.


    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é.




    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.

  • AliGatorAliGator Membre, Modérateur
    août 2015 modifié #8
    Effectivement pas besoin de prendre la racine carrée si tu fais le calcul d'une distance euclidienne.


    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.

  • AliGatorAliGator Membre, Modérateur

    Sauf si tu es un Neutrino.

    Même pas, puisqu'à  cette échelle ce n'est plus la mécanique classique qui s'affiche donc la distance dépend certainement de la vitesse à  laquelle tu te déplaces puisqu'alors ça contract l'espace-temps.
  • 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. 

  • Tu simplifies beaucoup le probleme en prenant une distance max. Tu peux commencer par extraire tous les points qui sont dans le rectangle déterminé par la distance maximale. Puis tu peux trier les résultats avec des calculs de distance exacte, voire des itinéraires routier si tu as peu de résultats.
  • Joanna CarterJoanna Carter Membre, Modérateur
    août 2015 modifié #13



    class Store {

    let name: String
    let location: CLLocation
    var distance: CLLocationDistance!

    init(data: [String]) {
    ...
    }

    func updateDistance(userLocation: CLLocation) {
    distance = userLocation.distanceFromLocation(location)
    }
    }



     


    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 :



    class DistanceCalculation
    {
    let storeLocation: CLLocation

    let userLocation: CLLocation

    init(storeLocation: CLLocation, userLocation: CLLocation)
    {
    self.storeLocation = storeLocation

    self.userLocation = userLocation
    }

    var distance: CLLocationDistance
    {
    return userLocation.distanceFromLocation(userLocation)
    }
    }



  • var distance: CLLocationDistance
    {
    return userLocation.distanceFromLocation(userLocation)
    }
    }



    On tourne un peu en rond là .
  • C'est bien quand même d'en faire une variable interne pour ne pas avoir à  recalculer la valeur à  chaque fois dans les tris et dans les affichages.

    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.
  • DrakenDraken Membre
    août 2015 modifié #16

    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.


  • AlakAlak Membre
    août 2015 modifié #17


    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.


  • AliGatorAliGator Membre, Modérateur
    Moi plutôt que de mettre la distance dans le Store alors qu'effectivement ce n'est pas une propriété intrinsèque du Store, ou d'avoir une classe DistanceCalculation, j'aurais juste fait un Dictionary<Store, CLLocationDistance>, que je remplis avec les distances par rapport à  ma position avant de faire le tri, et que je n'utilise que pendant le tri, et dont je peux me débarrasser après. Cela irait bien mieux avec la nature transitoire de ce calcul de distance.
  • FKDEVFKDEV Membre
    août 2015 modifié #19


    Moi plutôt que de mettre la distance dans le Store alors qu'effectivement ce n'est pas une propriété intrinsèque du Store, ou d'avoir une classe DistanceCalculation, j'aurais juste fait un Dictionary<Store, CLLocationDistance>, que je remplis avec les distances par rapport à  ma position avant de faire le tri, et que je n'utilise que pendant le tri, et dont je peux me débarrasser après. Cela irait bien mieux avec la nature transitoire de ce calcul de distance.




     


    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.


  • Joanna CarterJoanna Carter Membre, Modérateur

    On tourne un peu en rond là .




    Oups ! Mais tu sais ce que je voulais dire :)


  • 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.

  • AliGatorAliGator Membre, Modérateur
    août 2015 modifié #22
    Oui c'est l'idée du MVVM.

    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.
  • Joanna CarterJoanna Carter Membre, Modérateur

    Oui oui, t'inquiète, et en plus tu as démontré que le copier-coller est surement la plus grande source de bugs.




    Ce qui est embêtant, je ne l'ai pas copié-collé, je l'ai tapé directement du cerveau :lol:
  • DrakenDraken Membre
    août 2015 modifié #24

    Faut-il en déduire que ce cerveau est bugé ? Les nounous anglais ont-ils le même problème que les vaches anglaises ?


  • Joanna CarterJoanna Carter Membre, Modérateur
    Meuh ! ;)


  • 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?

  • Joanna CarterJoanna Carter Membre, Modérateur
    De mon avis, nounours :)
  • Meuh !

  • colas_colas_ Membre
    août 2015 modifié #29

    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à  !


  • Autre approche de ce problème : l'UX.


    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.
Connectez-vous ou Inscrivez-vous pour répondre.