Поиск 25 ближайших мест от db в android является SLOW

Question

У меня есть база данных около 12 000 записей. Каждая запись дала широту, долготу и пустое расстояние. Мне нужно найти 25 ближайших записей из текущего местоположения GPS. Мой ORM - greenDao.

Есть 2 проблемы: Я не знаю расстояние между мной и записями, и я не могу загрузить все записи в ОЗУ, потому что, когда я это делаю, куча доходит до 70 МБ, а приложение вылетает из OutOfMemoryException (так что мне нужно используйте ленивую загрузку).

Я попробовал этот подход:

1. Получить итератор для данной таблицы
2. входа нагрузки, вычислить его расстояние от моей текущей позиции, сохранить запись в ArrayList буфер (флеш-буфер ввода каждые 1000 записей обратно в БД (это просто updateInTx (...)), а затем очистить его)
3. повторить точку 2 до iterator.hasNext();
4. запрос из записей с пределом (25) .orderAsc()
5. результат

Это работает, но с точки 1-3 это очень и очень медленно (занимает около 25 секунд на Nexus 7). Отдых занимает около 1,5 секунд.

Я должен делать это каждый раз, когда пользователь запускает обновление приложений или запросов. Любые идеи, как решить проблему лучше?

Благодаря

EDIT: Это функция для вычисления расстояния, так что его трудно сделать это в SQL :(

double getDistance(GPSCoords myPos, Place place) { 
    double dlong = (place.getLongitude() - myPos.getLongitude()) * d2r; 
    double dlat = (place.getLatitude() - myPos.getLatitude()) * d2r; 
    double a = Math.pow(Math.sin(dlat/2.0), 2) + Math.cos(myPos.getLatitude() * d2r) 
      * Math.cos(place.getLatitude() * d2r) * Math.pow(Math.sin(dlong/2.0), 2); 
    double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a)); 
    double d = 6367 * c; 

    return d; 
} 

Answer 1

Я не понимаю, почему именно вы чувствуете, что вам нужно ленить загружать свои записи. Количество кучи 70 Мбайт звучит довольно подозрительно, всего лишь 12 тыс. Записей. Вы хватаете всю строку только для вычисления расстояния? Попробуйте просто захватывая столбцы, нужно:

• Широта
• Долгота
• Первичный ключ

Предполагая, что каждый из 8 байт за штуку, это 24 * 12000 байт, или около 280 килобайт. Дайте ему некоторую верхнюю комнату для просто быть Java, но вы все еще смотрите на что-то очень управляемый.

Затем вы можете выполнять вычисления в коде и просто выплевывать первичный ключ для каждой из ближайших точек. Второй запрос может захватить только те 25 (вся строка на этот раз), и все готово!

Answer 2

Есть много примеров вычисления расстояний с использованием различных вкусов SQL Загружайте каждую строку из своей БД и вычисляйте, насколько она удалена, а затем сортировка и поиск ближайшего времени будет медленным только с обратной стороны в базу данных. Выполнение вычисления в SQL и получение только тех, которые вам нужны, будет намного более результативным.

Answer 3

Вы можете попробовать перевести расчет расстояния в sql db. вы также можете добавить более разумный код, который будет выполнять расчет расстояния до тех пор, пока он не найдет 25 мест, где их расстояние от текущего местоположения меньше x (вы выбираете). или даже менее 25 элементов (возможно, вам просто нужно 7 заполнить экран), а затем продолжить вычисление в фоновом режиме, когда пользователь уже находится в приложении. Это будет намного лучший пользовательский интерфейс.

Answer 4

Вы должны быть в состоянии позволить SQL сделать работу в базе данных:

select ((x - ?)*(x - ?) + (y - ?)*(y - ?)) as distsq from entries 
order by dist limit 20 

К сожалению SQLite не обеспечивает возведение в степень, поэтому необходимы дублированные термины.

Если это еще не достаточно быстро, то другой подход будет заключаться в том, чтобы запросы с ограничивающей прямоугольниками были центрированы по вашему местоположению, корректируя размер ограничительной рамки двоичным поиском, пока у вас не будет 30 или нескольких записей. Индексы на каждом из измерений x и y будут ускорять их.

Редактировать Поскольку ОП говорит, что кривизна земли важна, техника ограничивающих коробок, вероятно, является наилучшим подходом, который мы можем получить с помощью нерасширенного sqlite. Вот предлагаемый алгоритм:

Let P be the current position 
Let Slat = lat0 be the bounding box latitude half-size initialized with a "best guess" 
Let Slon = lon0 be the bounding box longitude half-size initialized with a "best guess" 
// NB the best guesses should cover an approximately square area on the ground 
loop 
    Let W = P.lon - Slon, E = P.lon + Slon, N = P.lat + Slat, S = P.lat - Slat 
    C = select count(*) from entries 
     where W <= lon and lon <= E and S <= lat and lat <= N 
    if C indicates the result is too big (e.g. for memory or read time), 
    Slat = 0.5 * Slat 
    Slon = 0.5 * Slon 
    else 
    Let R be the result of the same query for * instead of count(*) 
    Let D be the geometric distance from P to the nearest point on bounding box 
    Compute r.dist for all r in R (in memory) 
    Sort R by dist (in memory) 
    Throw away the tail elements of R where r.dist > D 
     // Can't use these because points outside bounding box might be closer! 
    If at least 20 remaining R elements, 
     return top 20 
    else 
     Slat = 2 * Slat 
     Slon = 2 * Slon 
    end if 
    end if 
end loop  

Обратите внимание, что вам нужны индексы для lat и lon. Я не знаю, насколько хорош оптимизатор запросов SQLite в этом случае. Хороший оптимизатор выберет либо индекс lat, либо lon, основанный на статистике, накопленной из прошлых запросов, используя это, чтобы быстро найти все точки в диапазоне ограничивающих прямоугольников для этого измерения, а затем выполнить проверку этого результата, чтобы получить окончательный результат. Если оптимизатор не настолько умный, вы хотите проиндексировать только измерение, которое может произвести наименьший исходный результат: в среднем случае это тот, который имеет наибольшую геометрическую протяженность (пройденное расстояние).

The r* tree index будет делать запросы с ограничивающей рамкой намного быстрее, но, по крайней мере, через Jelly Bean, вам придется предоставить собственный экземпляр SQLite с включенным расширением. Возможно, позже версии Android включили его? Я не знаю.

Кроме того, если вы дойдете до использования пользовательского SQLite с помощью приложения, было бы довольно легко добавить функцию расстояния (с кривизной) в качестве расширения.