Расчет расстояния между точками Geo для больших наборов данных
Я создаю онлайн-приложение Symfony, и как часть процесса разработки мне было поручено отсортировать количество записей в базе данных по расстоянию от зарегистрированного пользователя; указанный пользователь может по своему желанию расширить радиус поиска до размеров всего мира.
В любой момент у меня есть доступ к GPS-координатам зарегистрированного пользователя, и в таблице базы данных я сохранил широту и долготу различных точек интереса.
В настоящее время в таблице POI есть только 400 записей, но из-за объема данных, которые я должен извлекать при каждом обращении к нему, время запроса уже немного превышает секунду. Добавление 400 тригонометрических функций к такой рабочей нагрузке вскоре приведет к тому, что такое время выполнения превысит допустимое.
Поэтому мне нужен быстрый и точный метод для расчета таких расстояний;
Я прочитал несколько статей, предлагающих формулу Haversine, но я нашел, что это слишком медленно для моих нужд, и даже обширную статью, такую как этот не может быть никакой помощи;
Учитывая, что я скоро смогу достичь тысяч POI с тысячами пользователей, зарегистрированных одновременно со всего мира, как я могу подойти (и, надеюсь, решить) такую проблему?
Я использую PHP 7.0, Symfony 3.2 и Doctrine; pdo для взаимодействия с сервером Mysql, с innoDB в качестве механизма базы данных
Мой клиент ценит точность по скорости, но не может ждать больше 5 секунд
Результаты запроса разбиты на страницы, поэтому делегирование сортировки клиенту невозможно
И база данных, и сервер php совместно используют один и тот же (ужасный) пул ресурсов, и такой пул должен использоваться совместно с другими приложениями.
На sidenote, некоторые из POI могут истечь после определенной даты
Решение
Вы попросили меня добавить это, так что я буду.
Вы уверены, что удар по производительности от Haversine? Мы успешно использовали PHP-реализацию этой формулы в своей работе около 2 лет, и мы выполняем большой объем поисков (около 150 тыс. В минуту в часы пиковой нагрузки).
Я не могу подробно рассказать о своей работе, но могу сказать, что мы используем комбинацию sphinx, mongoDB, mysql и RabbitMq.
В любом случае, и sphinx, и mysql страдают от плохой реализации вычислений расстояния, теряющих около 2 миль в точности на расстоянии 100 миль (именно поэтому мы используем его)
Одна вещь, которую вы можете сделать, это сравнить время, необходимое для запуска формулы Haversine, хороший сравнительный анализ — это первый шаг, когда у вас возникают проблемы с производительностью.
Хотя я не пользователь симфонии, у меня есть класс, который я сделал только для этой вещи. Это часть большей структуры, которую я строю в свободное время (Evolution). Вы можете получить класс здесь
https://github.com/ArtisticPhoenix/Evo/blob/master/Evo/Benchmark.php
Это очень просто в использовании
$mark = Benchmark::getInstance()->mark();
... code to time ...
echo Benchmark::getInstance()->format($mark);
И будет выводить что-то вроде
10 milliseconds
5 minutes 3 milliseconds
ect..
Он разработан так, что вы можете использовать несколько marks
$mark = Benchmark::getInstance()->mark();
... code to time ...
$mark1 = Benchmark::getInstance()->mark();
... more code to time ...
echo "TotalTime: ".Benchmark::getInstance()->format($mark);
echo "MethodTime: ".Benchmark::getInstance()->format($mark1);
etc..
Это в основном просто записывает microtime(true) (true как float), когда вы звоните mark() и возвращает идентификатор $mark тогда, если вы позвоните mark($mark) с идентификатором это вычтет это из текущего microtime(true), призвание format($mark) просто делает его более читабельным.
Надеюсь, это поможет вам!
Другие решения
Других решений пока нет …