Вхід і реєстрація
Розробка · 24 вересня 2018, 14:20 5229
Iliya Isd, Software Engineer

За сколько времени вы смогли бы написать и закодить такой алгоритм?

Коллеги, добрый день. У нас тут вышла дискуссия об эстимейтах, поэтому, в рамках спортивного интереса, хотелось бы услышать мнение коллективного разума.

API Google Places умеет искать места в радиусе до 50 км. Чтобы найти места на территории большего радиуса, необходимо разбить её на несколько участков и сделать несколько запросов. Их должно быть минимально возможное количество, при этом территория должна быть покрыта полностью, но с как можно меньшей погрешностью. Также должна учитываться кривизна земной поверхности.

На вход функции поступают координаты центра и требуемого радиуса. На выходе должен быть возвращён массив кортежей вида (lat, lng, r), где lat, lng — координаты центра подокружности радиусом менее 10 км, для которой будет выполнен подзапрос, и r — её радиус.

Вопрос 1. За какое время, в часах, вы сможете составить и закодить на комфортном для вас языке программирования вышеописанный алгоритм?

Вопрос 2. За какое время, как вы считаете, эту же задачу может выполнить разработчик в Google? (Полагая, что он не пользуется служебным положением для изменения API.)

Спасибо. :)

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
anonymous 26.09.2018 21:22

хтось в курсі, аутентифікація у них тільки по токену, чи вони ще просять ip вашого сервера під’єднати?
А то ту такі ціни jumpshare.com/v/ufcVdOgz4Flu3AhWn5VJ
на автокомліт менше 3$ за 1000 запитів
Якщо прийдеться використовувати буду через проксі стукати))
Не то що я жлоб, любий проект не зразу приносить прибутки, вони з розціками щось погнали))

Відповісти
Підтримати
Tymchyshyn Vitalii Researcher 26.09.2018 04:02

Оо, прикольна задача. Ну вставлю і я свої 5 копійок.
* ця задача в точності відповідає задачі Томпсона з фізики, розв’язується таке лише чисельним моделюванням. З іншого боку, якщо один раз змоделити і зберегти отримані координати, то можна ними послуговуватись, доки радіус Землі не зміниться :)
* якщо питання хоч що-небудь робоче зліпити, то одразу приходить думка розбивати на шестикутники, бо радіус запиту значно менший радіусу Землі і на таких масштабах кривина майже не помітна, а значить шестикутники (найоптимальніше рішення для площини) не може бути аж дуже поганим. Генерувати їх можна починаючи з полюса сфери і далі «поясками». В кожному пояску буде приблизно 6*n шестикутників, а зміщення між ними по куту тета sqrt(3)*r/R (кутова відстань між центрами сусідніх шестикутників в радіанах). Далі можна накастувати поворот, щоб центральний шестикутник опинився на потрібних координатах і все. Буде трохи зайвих перекриттів, особливо для великих радіусів запиту, але я не думаю, що то так смертельно: для радіусу розміром з півпланети для запитів біля екватора середня відстань між центрами від оптимальної в приблизно 1.7*r впаде до 1.15*r (якщо не напутав в оцінках). Як би це могло виглядати прикинув нижче:

DISCLAIMER: всіх чутливих до якості коду прохання не читати, або запастись відром — зговнякано на як-попало в 3-й ночі, аби лише запускалось і хтось міг потрейсити. Можуть бути баги, невраховані кейси чи навіть визиватись ктулху. 

from math import *

def adjust(phi, theta, p_phi, p_theta): # theta than phi
    return [\
    atan2(sin(theta)*sin(phi), cos(theta)*sin(p_theta) + cos(p_theta)*cos(phi)*sin(theta)) + p_phi, \
    acos(cos(p_theta)*cos(theta) - cos(phi)*sin(p_theta)*sin(theta))]

def get_points(lat, lng, given_r, r=10.0, R=6371.0):
    phi, theta = (lng/180.0*pi, (lat+90.0)/180.0*pi) # latitude theta;  longitude  phi
    iters   = 1 + (int(given_r / r) if given_r <= 4.0 * r else 1+int(ceil(given_r / (sqrt(3) * r))))
    indices = sum([[[n,k] for k in xrange(0, 6*n)] for n in xrange(1, iters)],[])
    points  = [[0.0, 0.0]] + map(lambda x: [(x[1] + 0.5*(x[0] % 2))*pi/3.0/x[0], x[0]*sqrt(3)*r/R], indices)
    coords  = map(lambda p: adjust(p[0], p[1], phi, theta), points)
    geo_c   = map(lambda p: [p[1]/pi*180.0-90.0, p[0]/pi*180.0], coords)
    return geo_c

print get_points(30.0, 70.0, 100.0)
Відповісти
Підтримати
Tymchyshyn Vitalii Researcher 26.09.2018 22:53
заюзать уже готовые формулы для эллипсоидов, или даже просто код, что в опенсурсе пачками валяется

Тоді уже й повністю готове рішення можна забрати — впевнений, що у відкритому доступі є не те що код, а навіть готове достатньо дрібне розбиття поверхні Землі, лише в файл зберегти й користуватись потім. Але я ж так розумію, що челедж був самому щось якнайшвидше згавнокодити.

для эллипсоидов

та і так точність плюс-мінус лопата, не думаю, що врахування такого щось дасть. Середній радіус Землі 6371.0 km, а на екваторіальний та «полюсний» складають 6378.1 km та 6356.8 km відповідно. Це 0.2% похибки, тобто глобус радіусом метр (в двері вже не влізе) буде відхилятись від ідеальної сферичної форми всього на 2 мм.

Відповісти
Підтримати
anonymous
Vlad Stelmahovsky Software Engineer в Verity AG 26.09.2018 08:45

баги в таких делах самое долгое. так что месяц только на баги и edge cases

Відповісти
Підтримати
anonymous
Yuri Kravchik Senior Java developer 25.09.2018 18:14

Раз на входе окружность и искать можно только окружностями, то ясно что это гексовая сетка. На одной крайности у нас один круг, на другой — «круг» составленный из меньших кругов (расположенных на гексовой сетке). Можно ещё подтюнить размер этих кругов, если имеет смысл. 1ч первый работающий в-т, 1 день — с оптимизациями, тестами и кофе-брейками.

Відповісти
Підтримати
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 25.09.2018 17:46

Если честно, то я бы не городил огород и полученные координаты обрезал бы до bounding box задаными четырьмя парами lat, lng. Таким образом локально будет хранится сетка квадратов. Да, количество запросов будет несколко больше, чем если оперировать кругами или шестиугольниками, но далеко не факт, если потому нужно будет дозапрашивать маленькие перекрывающие кусочки. С использованием bounding box не нужно заморачиваться кривизной поверхности земли.

Відповісти
Підтримати
Iliya Isd Software Engineer 25.09.2018 17:48

Это действительно было бы намного проще, но именно это API гугла (places nearby search) не поддерживает квадраты.

Відповісти
Підтримати
Mike Gorchak
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 25.09.2018 18:23

Правильно, запрашивать окружность с радиусом равным половины диагонали квадрата. И потом по приехавшему сету пройтись и повыкидывать все координаты за пределами нашего локального квадрата.

Відповісти
Підтримати
Iliya Isd
Vlad Stelmahovsky Software Engineer в Verity AG 26.09.2018 08:48

именно так и делал

Відповісти
Підтримати
Mike Gorchak
Ivan Stelmakh senior .net developer в Ideals 26.09.2018 11:33

Говоря «квадрат», учтите, что градус широты по длине равен градусу долготы только на экваторе. Поэтому чтобы получить квадрат не забудьте умножить на косинус широты )

Відповісти
Підтримати
Mike Gorchak
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 25.09.2018 18:25

Просто есть сильное подозрение, что у них данные внутри всё равно хранятся квадратами, только в API радиус, поэтому надо быть осторожным с локациями на самой окружности, их гугл может просто по-обрезать из-за округления. И оперировать только квадратами, вписанными в эту окружность (то, что я предлагал выше).

Відповісти
Підтримати
Iliya Isd
Alex Koshterek погромизд 26.09.2018 11:35

а внутри какой-нибудь геохэш прямоугольный)

Відповісти
Підтримати
Mike Gorchak
Denis Pakizh Independent Software Engineer 26.09.2018 13:51

Пока жители Виллабаджо зубрят геометрию, жители Вилларибо прочитали документацию и уже пишут код

Відповісти
Підтримати
anonymous
anonymous 26.09.2018 20:59

так, але там прікол з Required parameters, текст обовязковий

Відповісти
Підтримати
anonymous
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 25.09.2018 18:32

Ты хоть раз пробовал смотреть на землю со стороны? :) Это летающая сморщенная картошка, никакой не эллипсоид и не геоид, так что те формулы — это сплошная аппроксимация для выпуклового тела и в низинах они будут давать охренительные погрешности при расчётах. Есть шанс, что гугл это всё учитывает у себя, нужно просто отсекать граничные координаты из полученного списка.

Відповісти
Підтримати
anonymous
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 25.09.2018 19:03
В общем посылаю тебя читать про эту тему и не придумывать про сморщенные картошки.

Специально для тебя: www.sciencealert.com/...​-actually-lumpy-not-round — обычный бесформенный астероид с налипшей биомассой.

Відповісти
Підтримати
anonymous
Tymchyshyn Vitalii Researcher 26.09.2018 04:15

Ви не праві. Радіус Землі близько 6000 км, висота найвищих гір 8 км, глибина Маріанської впадини 11 км, чи щось таке. Якщо Ви зробите модель планети радіусом 1 метр, то що гори, що впадини, не перевищать 2 мм, а Ви подивіться на цю модель, тут же деформації просто кінські. Якщо проглянути статтю, на яку Ви посилаєтесь, то там чітко написано, що то не справжня форма, а результати гравітаційних вимірювань. Деталей нема, але дозволю собі зробити припущення, як її отримано: міряється гравітаційне поле в кожній точці, а потім будується така модель, що матиме той самий розподіл при _рівномірній_густині_. Як приклад: я візьму кулю, половина якої з заліза, а половина з дерева. Частини я піджену одна до одної ідеально. Тепер поміряю їх гравітаційний вплив і виявлю, що залізна половина тягне сильніше. А тепер якщо відбудувати модель тіла в допущенні рівномірної густини (якби вона була з якогось деревозаліза), то залізна половина дико розпухне, бо їй треба тягнути куди сильніше ніж дерев’яній.

Відповісти
Підтримати
Mike Gorchak
Tymchyshyn Vitalii Researcher 26.09.2018 23:01

Так я не про помилку обчислень, а про те, що наша планета дуже слабо відрізняється від сферичної — всі ці випуклості-ввігнутості мають порядок десятих долей процента середнього радіуса. Якщо вся модель влазить на монітор, то таких незначних відхилень не повинно бути помітно (вони менше 1 пікселя будуть). А те що там на картинці так здеформовано що здеформовано і очевидно не відповідає справжній формі Землі.

Відповісти
Підтримати
anonymous
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 26.09.2018 23:07
а про те, що наша планета дуже слабо відрізняється від сферичної

NASA утверждает, что земля — это вообще груша %) www.youtube.com/watch?v=nTOE4Ar0Dfo

Відповісти
Підтримати
Tymchyshyn Vitalii
Tymchyshyn Vitalii Researcher 26.09.2018 23:13

То-то я думаю всі кажуть, що Земля довкола якоїсь осі крутиться, а то ж черенок від груші... :)

Відповісти
Підтримати
Mike Gorchak
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 26.09.2018 23:24

Кстати, забавный факт, что NASA не опубликовало ни единой нормальной фотки земли — всё, что есть — это продукт художников.

Відповісти
Підтримати
Tymchyshyn Vitalii
Tymchyshyn Vitalii Researcher 26.09.2018 23:19

Так правильно, а я ж хіба не так написав?

там чітко написано, що то не справжня форма, а результати гравітаційних вимірювань. Деталей нема, але дозволю собі зробити припущення, як її отримано: міряється гравітаційне поле в кожній точці, а потім будується така модель, що матиме той самий розподіл при _рівномірній_густині_. Як приклад: я візьму кулю, половина якої з заліза, а половина з дерева. Частини я піджену одна до одної ідеально. Тепер поміряю їх гравітаційний вплив і виявлю, що залізна половина тягне сильніше. А тепер якщо відбудувати модель тіла в допущенні рівномірної густини (якби вона була з якогось деревозаліза), то залізна половина дико розпухне, бо їй треба тягнути куди сильніше ніж дерев’яній.
Відповісти
Підтримати
anonymous
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 26.09.2018 23:21

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

Відповісти
Підтримати
Tymchyshyn Vitalii
Tymchyshyn Vitalii Researcher 26.09.2018 23:45
в теории вода должна прекрасно реагировать на такую гравитационную разницу

Ваша правда, повинна.

принимая форму гравитационного поля

Не зовсім так. Її задача не прийняти чиюсь форму, а мінімізувати потенціальну енергію системи, а то вже трохи різні речі. Тому рівень океану може там-сям трохи відрізнятися, в тому числі за рахунок нерівномірного гравітаційного поля, але на Еверест вода з океану не полізе, хоча там купа каменюк і вони притягують.

Відповісти
Підтримати
Mike Gorchak
Tymchyshyn Vitalii Researcher 27.09.2018 02:53

Знайшов прикольне посилання
www.scienceinthenews.org.uk/contents/?article=25
Там на початку є список міст і значення g для них, а ще далі є картинка, майже така як Ви приводили, і до неї текст:

The picture shows high gravity areas as red and low gravity areas as blue. The shape of the Earth has been vastly exaggerated to show the effect on its shape.

Судячи з усього, вони просто взяли реальні відхилення від сферичності і домножили їх на якийсь кінський коефіцієнт чи щось в тому роді (а може й просто робота художника) — це навіть не розрахунки в рамках якоїсь цікавої фізичної toy model :( «скучно, розходимся»

Відповісти
Підтримати
Mike Gorchak
anonymous 25.09.2018 16:48

згоден з шестикутником менше запитів буде, але обчислення будуть не оптимальні для вашого сервера

Відповісти
Підтримати
anonymous
anonymous 25.09.2018 17:03
Код просто будет более замороченный для шестиугольной сетки и всё.

ось це і називається «не оптимально»

Відповісти
Підтримати
anonymous
Alex Koshterek погромизд 25.09.2018 17:46

Если гугл отдает строго по окружности, то как не возись, будет неоптимально. Если в своей базе — то можно в запрос сунуть искомый полигон, пусть даже границы города/района/etc и все будет

Відповісти
Підтримати
anonymous
Oleg Kariakin Senior Java Developer 25.09.2018 13:27

«Тут работы на 5 минут» © Говорит любой менеджер или лид.

Відповісти
Підтримати
Dmytro Shchurov Frontend/React Developer в KAJO s.r.o. 25.09.2018 12:54

Думаю, кривизной поверхности можно пренебречь, если Вы не хотите загрузить Гугл на пол дня, просчитывая места в радиусе 10 тыс км

Відповісти
Підтримати
Andy W 25.09.2018 11:02

в якості приколу :)
— утягнути дані у postgres
— підключити postgis
— шукати, як заманеться

(досвіду з postgres/postgis нема, якщо є підводні камені — не в курсі
але на ньому крутиться openstreetmap і не кашляє)

Відповісти
Підтримати
Vitaly Panchuk Tech Lead в StrongSD 25.09.2018 01:24

Я б звичайно шукав квадратами чи прямокутниками якщо так можна (це ефективніше і зручніше).

Але якщо потрібні саме кола, я б розбивав площу пошуку на рівносторонні шестикутники утворенні перекриттям кіл рівновіддалених центрів (так як встановлюють вишки сотового зв’язку), думаю, це забезпечить мінімум запитів, проте потрібно буде уніфікувати місця які знаходяться в перекритті кіл пошуку.

Приблизна картинка того що я маю на увазі тут upload.wikimedia.org/...​ircles36arcs-enclosed.png

По естімейтам тут не так просто, якщо алгоритм мені спав на думку миттєво, то якщо це реальний проект, то я б сказав, що це б зайняло 3-4 дня розробки, інтеграції і тестування з похибкою на те, що я ніколи не користувався Google Places API і пару раз юзав різні Google APIs.

Відповісти
Підтримати
Iliya Isd Software Engineer 25.09.2018 02:29

Примерно так. Собственно, разбиение, которое использую я: ibb.co/nb2Xu9
Квадраты или прямоугольники для этого типа запроса нельзя использовать, только окружности.
Для целей данного эксперимента полагаем, что в задачу разработчика не входит общение с API (оно реализуется независимо), и функция только должна принять на вход координаты центра и выдать массив координат заполняющих окружностей. API при этом не задействуется.

Відповісти
Підтримати
Vitaly Panchuk
Євген Лесько Competency manager в ELEKS 25.09.2018 12:20

помню, на заре аутсорсанья, где-то в конце 90-х, заказчик (кстате по гражданству немец, но из литовцев, общался по русски) ставит коллеге задачу и спрашивает оценку времени. Ответ: «Да ерунда! пару дней». Проходит порядка недели, и заказчик осторожно интересуется — а гдесопснобля? Ответ: «Ну я ж говорил — пару дней !!»

Відповісти
Підтримати
Vadim Kopanev
Vadim Kopanev Architect 25.09.2018 15:20

задача написать алгоритм, я даже не знаю как его растянуть на пару недель, разве что ничего не получалось почти 2 недели, а потом бац и готово

Відповісти
Підтримати
anonymous
Vadim Kopanev Architect 25.09.2018 17:29

по большому счету задача — написать алгоритм нарезания шара на кружки, более того вопрос стоит «за сколько составишь и реализуешь алгоритм?», не включая обучение, теории, уточнения и прочее

Відповісти
Підтримати
anonymous
Iliya Isd Software Engineer 25.09.2018 17:39

Ну, какую-то часть обучения стоит тоже включить. Не знакомство с основами тригонометрии, разумеется, все мы проходили матан. Но нагуглить нужные законы и вывести из них рабочие формулы — абсолютно. Короче представьте, что вы мидл/сеньор разработчик, и вам поручили такое закодить, вы же будете тратить рабочее (а не личное) время на это. Интересует размер этого рабочего (billable) времени, вопрос чисто практический.

Відповісти
Підтримати
Vadim Kopanev
Vadim Kopanev Architect 25.09.2018 17:48

с таким раскладом я буду эстимейтить как обычно на среднегостатистического разработчика, чтобы задачу мог сделать любой в команде, предварительно разбив ее на кучу задач, в итоге получится эстимейт в месяцах :)

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

Відповісти
Підтримати
Iliya Isd
Oleg Kariakin Senior Java Developer 25.09.2018 17:50

90% времени задачи занимает сделать вменяемые требования, acceptance criteria и разные ограничения. Обычно идет отписка на 2 строчки типа «сделай заебись!», а в процессе работы уже добавляют и добавляют. Неудивительно, что задача занимает месяцы вместо пары дней.

Відповісти
Підтримати
Vadim Kopanev
Vadim Kopanev Architect 25.09.2018 17:57

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

Відповісти
Підтримати
Oleg Kariakin
Oleg Kariakin Senior Java Developer 25.09.2018 18:00

У меня таких проектов не было. Вот типичный пример как ТС пишет обтекаемые вещи, а программимст потом их реализует как сам захочет с любой погрешностью, затем добавляется новая итерация изменений и тд. Так это еще довольно подробно написано. Обычно бывает что-то типа «Integrate Sadaka» и привет )

Відповісти
Підтримати
Vadim Kopanev
Iliya Isd Software Engineer 25.09.2018 17:52

Согласен, собственно с этой целью и вопрос: сравнить свой результат в этом плане с оценочным результатом других.
Кроме того, я вот щас этот код пишу и по факту у меня два часа даже тупо закодить по формулам не получается: вылазят всякие класные приколы типа ошибок округления (децимал не спасёт, всё равно будут разности при подсчёте корней и арксинусов), вычисления границ расчётов, градусы vs радианы в формулах и т.п.
Хотя сейчас я написал вам об этом и понял, как можно сделать по-другому, чтобы их избежать)

Відповісти
Підтримати
Vadim Kopanev
Кодерок 24.09.2018 21:13

Реализация этой хрени достаточно проста. Сложнее будет написать тест, подтверждающий что требуемая точность достигнута в пределах +/- требуемой погрешности. Т.е. что разбиение 1) достаточно для заданной точности 2) не избыточно (т.е. не влечёт к ненужному удлинению времени рассчёта).

Відповісти
Підтримати
Олексій Пєніє 24.09.2018 20:37

Коментар порушує правила спільноти і видалений модераторами.

anonymous 24.09.2018 18:02
Также должна учитываться кривизна земной поверхности.

в них є можливість шукати по висоті над рівнем моря?
чи може я щось не доганяю))

Відповісти
Підтримати
Iliya Isd Software Engineer 25.09.2018 02:45

Имеется в виду, требуется учитывать, что земная поверхность не плоская, и расстояние между двумя соседними точками — это дуга, а не прямая. Тыц.

Відповісти
Підтримати
anonymous
Oleksandr Voytsekhovskyy IT Chief в Uniweb 25.09.2018 11:33

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

Відповісти
Підтримати
Iliya Isd
anonymous 25.09.2018 14:46

Зрозуміло, це не проблема, якщо будете правильно рахувати в метрах.
Ось ваша перша функція так має виглядати github.com/...​oder/calculations.rb#L210
Щоб правильно метри порахувати github.com/...​coder/calculations.rb#L84

Відповісти
Підтримати
Iliya Isd
anonymous 25.09.2018 14:54

Ось, ще намалював jmp.sh/mwW19K5
На око видно що це трохи кода, якщо є норм ліб для геокодінгу, там більш з тестом прікол(типу довше писати).

Відповісти
Підтримати
anonymous
anonymous 25.09.2018 15:41

сорі, за файл, діагональ може бути ... <= 50км * 2

Відповісти
Підтримати
anonymous
TechnoBarbarian 24.09.2018 15:14
Также должна учитываться кривизна земной поверхности.

Ты это, потише — щас набегут flat-earthers.

Відповісти
Підтримати
Andrey Bobkov 25.09.2018 14:27

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

Відповісти
Підтримати
TechnoBarbarian
Oleg Kariakin Senior Java Developer 24.09.2018 15:03
минимально возможное количество, при этом территория должна быть покрыта полностью, но с как можно меньшей погрешностью. Также должна учитываться кривизна земной поверхности.

Насколько минимальное? Как учитываться? Не хватает только кОрованов.

Відповісти
Підтримати

Підписатись на коментарі

Не підписуватись
Скористайтесь акаунтом
×
з умовами використання сайту і політикою конфіденційності.