Jaki jest najszybszy sposób sortowania wielu lokalizacji na odległość?

Question

Chcę posortować wiele lokalizacji (punktów trasy) na ich odległość od bieżącej lokalizacji. Bieżąca lokalizacja jest oczywiście ruchomym celem, więc przy każdej aktualizacji lokalizacji konieczne jest przeliczenie dystansu dla każdej lokalizacji. Ale wystarczyłoby tylko ponowne przeliczenie na najbliższe lokalizacje.

Obecnie korzystam z danych podstawowych i przechowuję odległość do bieżącej lokalizacji jako atrybut w tabeli (ale aktualizuję tylko wtedy, gdy jest zmieniana) z metody configurecell: atindexpath: method. Ten rodzaj prac, ale aplikacja nie odpowiada, podczas gdy dane podstawowe automagicznie aktualizują wszystkie odległości. Działa to w 250 lokalizacjach, ale w przypadku 5000 powoduje awarię. Potrzebuję go do pracy w 10.000 lokalizacji, chociaż prawdopodobnie potrzebuję tylko 1000 najbliższych lokalizacji.

Pomysły, których jeszcze nie próbowałem: Przechowuj wszystkie odległości w osobnej tablicy w pamięci z niczym oprócz identyfikatora rekordu i odległości. Następnie posortuj tablicę na odległość. Problem polega na tym, że nie mogę użyć kontrolera FetchedResultsController, ponieważ w bazie danych nie ma pola sortowania.

Filtruj lokalizacje na podstawie ich szerokości i długości geograficznej za pomocą predykatu. Następnie przedstaw tylko przefiltrowane lokalizacje.

Wykonaj ponowną kalkulację odległości w oddzielnym wątku.

Żadne z pomysłów nie wydaje się łatwe, wystarczy je wypróbować.

Ktoś z sugestiami, różnymi pomysłami, odmianą moich pomysłów?

Answer 1

Moje końcowe rozwiązanie jest następujące: Wybieram wszystkie waypointy w obrębie 1 stopnia szerokości i długości geograficznej (zwykle około 1000 punktów), a następnie obliczam i zapisuję odległość do aktualnej pozycji w tabeli. Mogę następnie sortować na odległość. Powolną rzeczą byłaby oszczędność w danych podstawowych. Ale po sortowaniu (i pobieraniu) po prostu anuluję zmiany. Oszczędności zajmowały ponad 90% całości, więc to działało całkiem dobrze.

Answer 2

Wygląda na to, że musisz przekonwertować swoje lokalizacje na pozycje na krzywej Hilberta - a następnie wskazuje "w pobliżu", że jesteś prostym odejmowaniem?

Mapping N-dimensional value to a point on Hilbert curve

Nie mogę powiedzieć, że znam techniki podszewki, ale właśnie tam zacząłbym szukać

Answer 3

Jeśli to, co ważne jest kolejność (w przeciwieństwie do posiadania dokładnych odległości), można sortuj przekroje sekwencji punktów drogi w ruchomym oknie (to jest, sortuj elementy i zmieniaj je). Zacznij od początku sekwencji punktów drogi. Sortuj pozycje: n (n = 10 jest dobrym miejscem do rozpoczęcia). Jeśli jakakolwiek pozycja zmieniła położenie, przesuń okno do przodu o n/2 (eksperymentuj z różnymi przesunięciami lub algorytmami, aby wybrać przesunięcie) i powtórz. W zależności od tego, jak gęsty jest punkt drogi w pobliżu aktualnej pozycji, spodziewałbym się, że zatrzyma się to po zaledwie kilku rodzajach.

Pamiętaj, że nie myślałem o tym wystarczająco długo, aby stwierdzić, czy to zadziała, czy nie.

Z trzech wymienionych opcji najbardziej lubię używać nici. To klasyczny sposób obsługi niereagującego interfejsu użytkownika, gdy jest on blokowany przez ciężkie obliczenia.

Answer 4

Przechowuję moje lokalizacje w modelu danych jako współrzędne szerokości/długości geograficznej. Następnie napisałem rozszerzenia pomocników, aby znaleźć pół-prostokątny region o współrzędnych lat/lon i zapytanie przez to. Oto kod, którego używam. Wiem, że pytanie dotyczyło Celu C, ale pytanie jest stare i prawdopodobnie większość ludzi szuka teraz odpowiedzi Swift.

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