|
Поиск в списке значения максимально приближенного к заданному | ☑ | ||
---|---|---|---|---|
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
|
||||
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) Соединение по условию. Рекомендую индексы. |
Форум | Правила | Описание | Объявления | Секции | Поиск | Книга знаний | Вики-миста |