Какой самый быстрый способ сортировки большого количества мест на расстоянии?

Question

Я хочу отсортировать множество мест (путевых точек) по их удалению от текущего местоположения.Текущее местоположение, конечно, является движущейся целью, поэтому для каждого обновления местоположения необходимо пересчитывать расстояние для каждого местоположения.Но достаточно только повторного вычисления для близлежащих местоположений.

В настоящее время я использую данные ядра и сохраняю расстояние до текущего местоположения в качестве атрибута в таблице (но только обновление происходит, когда оно изменяется) извнутри configurecell: atindexpath: метод.Это работает, но приложение не отвечает, в то время как данные ядра автоматически обновляют все расстояния.Это работает для 250 местоположений, но для 5000 это терпит крах.Мне нужно, чтобы он работал на 10.000 местоположений, хотя, вероятно, мне нужны только 1000 ближайших местоположений или около того.

Идеи, которые я еще не пробовал: хранить все расстояния в отдельном массиве в памяти, не используя ничего, кроме идентификатора записии расстояние.Затем отсортируйте массив по расстоянию.Проблема в том, что тогда я не могу использовать FetchedResultsController, потому что в базе данных нет поля сортировки.

Фильтрация местоположений на основе их широты и долготы с использованием предиката.Затем представьте только отфильтрованные местоположения.

Выполните пересчет расстояний в отдельном потоке.

Ни одна из идей не кажется достаточно простой, чтобы просто опробовать ее.

Любой, у кого естьпредложения, разные идеи, вариация моих идей?

Answer 1

Мое окончательное решение заключается в следующем: я выбираю все путевые точки в пределах 1 градуса широты и долготы (обычно около 1000 путевых точек), а затем вычисляю и сохраняю расстояние до текущей позиции в таблице.Я могу тогда сортировать на расстоянии.Медленная вещь будет сохранение в основных данных.Но после сортировки (и извлечения) я просто отменяю изменения.Экономия занимала более 90% всего этого, так что это работало довольно хорошо.

Answer 2

Если важен порядок (в отличие от точных расстояний), вы можете сортировать фрагменты последовательности путевых точек в движущемся окне (то есть сортировать элементы от i до i + n)., где i изменяется).Начните с начала последовательности путевых точек.Сортировать n элементов (n = 10 - хорошее место для начала).Если какие-либо элементы изменили положение, переместите окно вперед на n / 2 (поэкспериментируйте с различными смещениями или алгоритмами, чтобы выбрать смещение) и повторите.В зависимости от того, насколько плотная точка маршрута находится рядом с текущим местоположением, я ожидаю, что это остановится только после нескольких сортировок.

Обратите внимание, что я не думал об этом достаточно долго, чтобы сказать, сработает ли это на самом деле.

Из трех упомянутых вами вариантов мне больше всего нравится использовать нити.Это классический способ обработки неотвечающего пользовательского интерфейса, когда он блокируется тяжелыми вычислениями.

Answer 3

Звучит так, как будто вам нужно преобразовать ваши местоположения в позиции на кривой Гильберта - тогда точки "рядом" вы просто вычитаете?

Отображение N-мерного значения в точку на кривой Гильберта

Не могу сказать, что знаю технику наизнанку, но именно здесь я бы начал смотреть

Answer 4

Я храню свои местоположения в модели данных как координаты широты / долготы.Затем я написал несколько вспомогательных расширений, чтобы найти полупрямоугольную область координат широты и долготы и выполнить запрос по ней.Вот код, который я использую.Я знаю, что вопрос был для Objective-C, но вопрос старый, и, вероятно, большинство людей все равно сейчас ищут ответ Swift.