Qual è il modo più veloce per ordinare molte località sulla distanza?

Question

Desidero ordinare molte posizioni (waypoint) sulla loro distanza dalla posizione corrente. La posizione corrente è, ovviamente, un bersaglio mobile, quindi per ogni aggiornamento di posizione, è necessario ricalcolare la distanza per ogni posizione. Ma solo ricalcolare per le posizioni vicine sarebbe sufficiente.

Attualmente utilizzo i dati di base e memorizzo la distanza della posizione corrente come attributo nella tabella (ma solo l'aggiornamento è quando viene modificato) all'interno del configurecell: atindexpath: method. Questo tipo di funziona, ma l'applicazione non risponde mentre i dati del core aggiornano automaticamente tutte le distanze. Questo funziona per 250 posizioni, ma per 5000 si blocca. Ho bisogno che funzioni per 10.000 località, anche se probabilmente ho solo bisogno delle 1000 località più vicine o giù di lì.

Idee che non ho ancora provato: Memorizza tutte le distanze in un array separato in memoria con nient'altro che ID e distanza di registrazione. Quindi ordina la matrice sulla distanza. Il problema è che quindi non posso usare FetchedResultsController perché non esiste un campo di ordinamento nel database.

Filtra le posizioni in base alla latitudine e alla longitudine utilizzando un predicato. Quindi presentare solo le posizioni filtrate.

Eseguire il ricalcolo delle distanze in una filettatura separata.

Nessuna idea sembra abbastanza semplice da provare.

Chiunque abbia suggerimenti, idee diverse, una variazione delle mie idee?

Answer 1

La mia soluzione finale è la seguente: Seleziono tutti i waypoint entro 1 grado di latitudine e longitudine (circa 1000 waypoint normalmente) e quindi calcoliamo e memorizziamo la distanza dalla posizione corrente nella tabella. Posso quindi ordinare sulla distanza. La cosa lenta sarebbe il risparmio in Core Data. Ma dopo l'ordinamento (e il recupero), annullo semplicemente le modifiche. Il risparmio ha richiesto più del 90% del totale, quindi ha funzionato abbastanza bene.

Answer 2

Sembra che sia necessario convertire le posizioni in posizioni su una curva di Hilbert, quindi i punti "vicini" sono una semplice sottrazione?

Mapping N-dimensional value to a point on Hilbert curve

Non posso dire che conosco la tecnica dentro e fuori, ma è lì che mi piacerebbe iniziare a guardare

Answer 3

Se ciò che è importante è l'ordine (invece di avere distanze precise), si potrebbe ordinare le sezioni della sequenza di waypoint in una finestra in movimento (ovvero, ordinare gli articoli i a i + n, dove i modifiche). Inizia dall'inizio della sequenza del waypoint. Ordina n elementi (n = 10 è un buon punto di partenza). Se alcune voci cambiano posizione, sposta la finestra in avanti di n/2 (sperimenta offset o algoritmi diversi per scegliere un offset) e ripeti. A seconda di quanto sia denso il waypoint vicino alla posizione corrente, mi aspetto che questo si fermi dopo solo alcuni tipi.

Nota che non ho pensato a questo abbastanza a lungo da dire se funzionerà o meno.

Delle tre opzioni menzionate, mi piace usare i fili di più. Questo è il modo classico di gestire un'interfaccia utente non reattiva quando è bloccata da calcoli pesanti.

Answer 4

devo conservare le mie posizioni nel modello di dati come le coordinate di latitudine/longitudine. Poi ho scritto alcune estensioni helper per trovare una regione semirettangolare di coordinate lat/lon e interrogare per quello. Ecco il codice che sto usando. So che la domanda era per Objective-C ma la domanda è vecchia e probabilmente la maggior parte delle persone sta cercando una risposta rapida comunque.

Swift 3

extension CLLocationDistance { 
     var feet: Double { 
      return self * 3.28084 
     } 
     var miles: Double { 
      return self.feet/5280.0 
     } 
    } 

    extension CLLocationDegrees { 
     static var north: CLLocationDegrees { 
      return 90.0 
     } 
     static var south: CLLocationDegrees { 
      return -90.0 
     } 
     static var east: CLLocationDegrees { 
      return 180.0 
     } 
     static var west: CLLocationDegrees { 
      return -180.0 
     } 

     var radians: Double { 
      return Double.pi * self/180.0 
     } 
    } 

    extension CLLocationCoordinate2D { 
     static var origin: CLLocationCoordinate2D { 
      return CLLocationCoordinate2D(latitude: 0.0, longitude: 0.0) 
     } 

     static var northPole: CLLocationCoordinate2D { 
      return CLLocationCoordinate2D(latitude: 90.0, longitude: 0.0) 
     } 

     static var southPole: CLLocationCoordinate2D { 
      return CLLocationCoordinate2D(latitude: 90.0, longitude: 0.0) 
     } 

     var metersPerDegreeLatitude: CLLocationDistance { 
      return 111319.4907932736 
     } 
     var metersPerDegreeLongitude: CLLocationDistance { 
      return max(0.0, cos(self.latitude.radians) * self.metersPerDegreeLatitude) 
     } 
    } 

    extension CLCircularRegion { 
     var northernmostLatitude: CLLocationDegrees { 
      let longitude = self.center.latitude + self.radius/self.center.metersPerDegreeLatitude 
      return min(longitude, .north) 
     } 

     var southernmostLatitude: CLLocationDegrees { 
      let longitude = self.center.latitude - self.radius/self.center.metersPerDegreeLatitude 
      return max(longitude, .south) 
     } 

     var easternmostLongitude: CLLocationDegrees { 
      guard self.northernmostLatitude <= .north else { 
       return .east 
      } 
      guard self.southernmostLatitude >= .south else { 
       return .east 
      } 
      return min(.east, self.center.longitude + self.radius/(self.center.metersPerDegreeLongitude + 0.0001)) 
     } 

     var westernmostLongitude: CLLocationDegrees { 
      guard self.northernmostLatitude <= .north else { 
       return .west 
      } 
      guard self.southernmostLatitude >= .south else { 
       return .west 
      } 
      return max(.west, self.center.longitude - self.radius/(self.center.metersPerDegreeLongitude + 0.0001)) 
     } 

     func buildPredicate(latitudeName: String = "latitude", longitudeName: String = "longitude") -> NSPredicate { 
      let args = [self.southernmostLatitude, self.northernmostLatitude, self.westernmostLongitude, self.easternmostLongitude] 
      return NSPredicate(format: "\(latitudeName) >= %@ && \(latitudeName) <= %@ && \(longitudeName) >= %@ && \(longitudeName) <= %@", argumentArray: args) 
     } 
    }