Cách nhanh nhất để sắp xếp nhiều vị trí trên khoảng cách là gì?

Question

Tôi muốn sắp xếp nhiều vị trí (điểm tham chiếu) về khoảng cách của chúng từ vị trí hiện tại. Vị trí hiện tại là, tất nhiên, một mục tiêu di động, vì vậy đối với mọi cập nhật vị trí, việc tính toán lại khoảng cách cho mọi vị trí là cần thiết. Nhưng chỉ tính toán lại cho các vị trí cận kề sẽ đủ.

Tôi hiện đang sử dụng dữ liệu lõi và lưu khoảng cách đến vị trí hiện tại làm thuộc tính trong bảng (nhưng chỉ cập nhật là khi nó được thay đổi) từ bên trong phương thức configureecell: atindexpath:. Loại tác phẩm đó, nhưng ứng dụng không phản hồi trong khi dữ liệu lõi tự động cập nhật tất cả các khoảng cách. Điều này làm việc cho 250 địa điểm, nhưng cho 5000 địa điểm bị treo. Tôi cần nó để làm việc cho 10.000 địa điểm, mặc dù tôi có lẽ chỉ cần 1000 địa điểm gần nhất.

Ý tưởng mà tôi chưa thử: Lưu trữ tất cả các khoảng cách trong một mảng trong bộ nhớ riêng biệt mà không có gì ngoài id hồ sơ và khoảng cách. Sau đó sắp xếp mảng trên khoảng cách. Vấn đề là sau đó tôi không thể sử dụng một FetchedResultsController vì không có trường sắp xếp trong cơ sở dữ liệu.

Lọc vị trí dựa trên vĩ độ và kinh độ của chúng bằng cách sử dụng vị từ. Sau đó, chỉ hiển thị các vị trí được lọc.

Thực hiện tính toán lại khoảng cách trong một chuỗi riêng biệt.

Không có ý tưởng nào có vẻ dễ dàng để chỉ dùng thử.

Bất kỳ ai có đề xuất, ý tưởng khác, biến thể về ý tưởng của tôi?

Answer 1

Giải pháp cuối cùng của tôi như sau: Tôi chọn tất cả các điểm tham chiếu trong phạm vi 1 độ vĩ độ và kinh độ (khoảng 1000 điểm thông thường) và sau đó tính toán và lưu khoảng cách đến vị trí hiện tại trong bảng. Sau đó tôi có thể sắp xếp theo khoảng cách. Điều chậm sẽ là tiết kiệm trong Core Data. Nhưng sau khi sắp xếp (và tìm nạp), tôi chỉ cần hủy các thay đổi. Việc tiết kiệm đã chiếm hơn 90% của toàn bộ điều, do đó, điều này làm việc khá tốt.

Answer 2

Có vẻ như bạn cần chuyển đổi vị trí của mình thành các vị trí trên đường cong Hilbert - sau đó chỉ "gần" bạn là phép trừ đơn giản?

Mapping N-dimensional value to a point on Hilbert curve

Không thể nói tôi biết kỹ thuật trong ra ngoài, nhưng đó là nơi tôi muốn bắt đầu nhìn

Answer 3

Nếu điều quan trọng là thứ tự (như trái ngược với việc khoảng cách chính xác), bạn có thể sắp xếp các lát của chuỗi điểm tham chiếu trong cửa sổ di chuyển (tức là, sắp xếp các mục i đến i + n, trong đó i thay đổi). Bắt đầu từ đầu trình tự waypoint. Sắp xếp n mục (n = 10 là một nơi tốt để bắt đầu). Nếu bất kỳ mục nào đã thay đổi vị trí, hãy di chuyển cửa sổ về phía trước bằng cách n/2 (thử nghiệm với các offset hoặc thuật toán khác nhau để chọn độ lệch) và lặp lại. Tùy thuộc vào cách điểm mốc dày đặc ở gần vị trí hiện tại, tôi hy vọng điều này sẽ dừng lại chỉ sau một vài loại.

Lưu ý rằng tôi đã không nghĩ về điều này đủ lâu để nói liệu điều này có thực sự hoạt động hay không.

Trong ba tùy chọn bạn đề cập, tôi thích sử dụng các chủ đề nhiều nhất. Đó là cách cổ điển để xử lý giao diện người dùng không đáp ứng khi bị chặn bởi tính toán nặng.

Answer 4

Tôi lưu trữ vị trí của mình trong mô hình dữ liệu dưới dạng toạ độ kinh độ/vĩ độ. Sau đó, tôi đã viết một số phần mở rộng của trình trợ giúp để tìm một vùng tọa độ bán kính của tọa độ vĩ độ/kinh độ và truy vấn theo đó. Đây là mã tôi đang sử dụng. Tôi biết câu hỏi này là cho Objective-C nhưng câu hỏi là cũ và có thể hầu hết mọi người đang tìm kiếm một câu trả lời Swift anyway bây giờ.

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