Полчаса — это если в 12 потоков) И код по хардкору на C++. Руками ничего не обрабатываю, потому что лень( Из-за этого всякие несуразности все-равно остаются.
2. Это как-то неправильно. Задача обратного геокодинга сложная сама по себе, а если еще и память нельзя кушать, то совсем печально получается.
Забавно. Я сейчас тихо-мирно тоже потихоньку пилю свой обратный геокодер (как библиотеку), который умеет возвращать то же, что и ваш (в смысле ID). Он переваривает все данные OSM примерно за полчаса и генерит бинарную базу примерно на 5Гб (могу еще сжать до 4Гб, но придется всякие битовые оптимизации мутить). После чего используя эту бинарную базу умеет порядка 100 000 локальных вызовов в библиотеку с временами ответов почти всех запросов в районе 1 микросекунды, если подтянуть все данные в память перед запросами. Честного тестирования производительности не делал, поэтому цифры примерные, но правильного порядка. Планирую в течении ближайших пары месяцев допилить и написать статью о библиотеке, алгоритмах и структурах данных в ней.
Откуда вы взяли лишнее log(n) при m? Стандартная сложность этого алгоритма при использовании кучи — O(m + n* log(n)).
Если использовать фибоначчиеву кучу, то да. При использовании обычной кучи, асимптотика именно такая, как я показал.
А вот и нет, интуитивно понятно, но неверно. Точнее, верно только в том случае, если вы соблюдаете ограничение применимости этого алгоритма, про которое в посте ни слова.
Согласен, это верно только при не отрицательных весах ребер, сейчас допишу об этом в посте.
P.S. Лучше брать flatbuffers для этой цели.
2. Это как-то неправильно. Задача обратного геокодинга сложная сама по себе, а если еще и память нельзя кушать, то совсем печально получается.
P.S. Сори (коменты не читай — сразу отвечай)
Не согласен. Кучу писать совсем не сложно.
Если использовать фибоначчиеву кучу, то да. При использовании обычной кучи, асимптотика именно такая, как я показал.
Согласен, это верно только при не отрицательных весах ребер, сейчас допишу об этом в посте.