Имя: Пароль:
IT
 
Поиск в списке значения максимально приближенного к заданному
,
0 Торин
 
25.08.16
14:24
Здачка такая -- есть таблица координат -- трек движения автомобиля с сайтика Виалон. Есть координаты фиксированной точки. Требуется понять в какое время машина была в этой точке. Проблема в том, что ТОЧНО в этой точке она скорее всего никогда не была, а была скажем на 30 метров левее или правее. Значит поиск по точному совпадению координат не подходит. Надо найти в таблице точку, МИНИМАЛЬНО отличающуюся от фиксированной. Вопрос -- как?

Простым перебором строк таблицы не предлагать -- в таблице полторы-две тысячи строк, а точек 5-10 и всю эту лабуду надо повторить около ста раз (т.е. для каждой машины из парка). Есть какие-нить идеи? Буду очень благодарен...
1 Лодырь
 
25.08.16
14:25
Запрос?
2 Торин
 
25.08.16
14:26
Ну скорее всего да. А идею запроса можете предложить?
3 Лодырь
 
25.08.16
14:28
Соединение таблицы точек с таблицей треков. Вычисляешь расстояние как сумму квадратов разностей координат. Выкидываешь больше некой минимальной дельты. Получившаяся таблица - время и дата пребывания машины в искомых точках. Делов то.
4 RomanYS
 
25.08.16
14:29
Вопрос про 1С?

Современный процессор делает миллиарды операций в секунду, и твоя задача выполнится за доли секунды. Ну на 1С это будут секунды.
5 Торин
 
25.08.16
14:33
(3) Спасибо, сейчас попробую
(4) если бы секунды... На практике прямой перебор для 96 машин и 470 фиксированных точек проработал около сорока минут
6 Chum
 
25.08.16
14:33
(0) ты в школе информатику прогуливал?

https://acmp.ru/article.asp?id_text=159
7 Торин
 
25.08.16
14:36
(6) ага, и эту операцию придется повторить
2000 строк таблицы * 5 точек * 100 машин = ОДИН МИЛЛИОН раз...

Мне что-нить побыстрее надо
8 Лодырь
 
25.08.16
14:38
Метрику можешь брать другую, не обязательно сумму квадратов. Сумма модулей разности будет быстрее скорее всего. А точность тебе нафиг не нужна.
9 Лодырь
 
25.08.16
14:38
Да и вообще у тебя там система координат хз какая ) Сам придумывай попроще метрику.
10 Masquerade
 
25.08.16
14:38
(0)

Значит поиск по точному совпадению координат не подходит.

А как ты думаешь - если у координат последние цифры заменить нулями - во что превратится "точка"?
11 МихаилМ
 
25.08.16
14:45
ябы построил (подобрал) систему координат. в этом случае на поиск точки потребуется 1-4 выбора точек , тк попадаем сразу в нужный "квадрат". естественно при добавлении новой точки   придется пересчитывать.

смотрите в сторону реализации пространственных индексов.
12 Chum
 
25.08.16
14:48
(10) точка и будет, только сместится хз куда
13 RomanYS
 
25.08.16
16:19
(7) "ОДИН МИЛЛИОН" арифметических операций это даже для 1С смешная нагрузка. А вот если ты в этом цикле данные из БД будешь тянуть, тогда да... кранты. Запрос должен быть один.
14 Garykom
 
гуру
25.08.16
16:29
(0) ТС кури про индексы и метод половинного деления на отсортированных данных
15 Garykom
 
гуру
25.08.16
16:34
(14) индексы в смысле обычное деревья
16 МихаилМ
 
25.08.16
16:59
17 Mort
 
25.08.16
20:37
Можно сделать в два прохода, сначала ограничить точки входящими в квадрат +/- 50 м, потом найти ближайшую. Одним пакетником, конечно.
18 Garykom
 
гуру
25.08.16
20:54
Только сообразил что задачка действительно в 2 приема решается ))

1. Сначала добавляем колонку расстояние до фикс точки (формула расстояния между точками на плоскости).
2. Затем берем запись с этим минимальным расстоянием.
19 lvz
 
25.08.16
20:58
задать два условия:
( < x < ) и ( < y < )
20 Garykom
 
гуру
25.08.16
21:02
(19) Да это 0 этап сокращения выборки для уже более точного нахождения искомой "ближайшей точки" к фиксированной.
Если точность не нужна полная (именно ближайшую точку траектории отыскать) то вполне его хватит чтобы понять.

Но лучше все же найти точную иначе если машина долго стояла рядом с точкой то время будет не верное
21 Jija Grenkov
 
25.08.16
22:43
Расстояние между точками на плоскости не прокатит. Для gps координат формула сложнее. Я такое тупым перебором считал. Когда точек стало много заюзал ком объект куда вынес многопоточных расчёт. Код был на шарпе на 1 потоке скорость расчёта примерно в 100-200 раз выше чем в 1с, при распаралеливании ещё выше.
22 Михаил Козлов
 
26.08.16
12:02
(18) Прямо в запросе можно выбрать точку с минимальным расстоянием. Не знаю, будет ли это значительно быстрее.
23 Jija Grenkov
 
26.08.16
12:46
(22) Как? там нужно тригонометрические функции использовать дял расчета. Теорема пифагора не катит
24 vasbur
 
26.08.16
12:56
(0) бери не все точки, а например каждую 100-ю. ищи ближайшие среди них.
потом бери все точки, которые расположены рядом с этими ближайшими в в треке - и ищи среди ник
25 Jija Grenkov
 
26.08.16
13:02
(24) а что значит найти ближайшие? перебрать все и посчитать расстояние до заданнйо точки? Тут конечно можно представить данные в виде удобного дерева, но для этого может понадобится больше расчетных ресурсов чем для тупого перебора.
26 vasbur
 
26.08.16
13:02
(5) >На практике прямой перебор для 96 машин и 470 >фиксированных точек проработал около сорока минут
а ты для каждой точки заново все трэки перебирал? и заново их из базы вычитывал?

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

т.е. в первую очередь нужно минимизировать количество запросов к БД, миллион операций с оперативной памятью - плевое дело
27 vasbur
 
26.08.16
13:03
(25) как-то так да.
но правильно решение зависит от того, как хранятся данные и насколько дорого их вычитывать в память
28 Jija Grenkov
 
26.08.16
13:06
Да просто автору можно сделать предрасчет и записать уже подготовленные данные в регистр. 40 минут это фигня, на сервере может и быстрее будет. Можно запустить по 1 фоновому заданию на машину
29 Михаил Козлов
 
26.08.16
13:16
(23) Не обижайте Пифагора: для небольших расстояний (надеюсь, ближайшая точка не в сотне километров от точки) поверхность Земли можно считать плоскостью. Да и сама метрика не важна: ищется же не точное расстояние, а ближайшая точка: для любой разумной метрики у "ближайшей" точки и расстояние будет минимальным.
30 Jija Grenkov
 
26.08.16
16:29
(29) ваша область будет не круглой а овальной. Получится с 1 стороны можно на 200 метров нужно подъехать, а с другой на 100. Посмотрите на карту на соотношение долготы
31 Gary417
 
26.08.16
16:36
вроде бы есть специальные БД, типа Postgis... там одним запросом такие операции делаются
32 Gary417
 
26.08.16
16:37
типа в массиве отправляешь список координат и координату точке, и оно возвращает минимальное расстояние...

точнее не подскажу, давно шашку в руки не брал
33 Gary417
 
26.08.16
16:37
очень быстро работает
34 ovrfox
 
06.09.16
17:41
Теория : поиск в неупорядоченном массиве это перебор всех значений.
Вывод задача с указанными условиями - не разрешима.
А вообще исследование трекинга - необязательно с расчетом расстояния, достаточно найти "попадание", например с условиями (X-Xo)<30 и (Xo-X)<30 и (Y-Yo)<30 и (Yo-Y)<30
Уже по ним вычислить реальное рассточние и выбрать минимум
Ускорение для множества точек и автомобилей - как уже было сказано ранее - это отбор необходимых данных за один проход. Но в любом случае, пофакту это полный перебор всех строк.
35 Loky9
 
06.09.16
22:37
(21) Считать расстояние в градусах и всё прокатит.
(0) Соединение по условию. Рекомендую индексы.