У меня тоже очень быстрый самописный парсер OSM есть. Проблема в том, что надо еще распарсивать XML entity.
x10kHz: попробуй запустить на PyPy, он раза в 2-3 быстрее, чем стандартный Питон.
if self.curr_node:
self.curr_node.tags[attrs['k']] = attrs['v']
elif self.curr_way:
self.curr_way.tags[attrs['k']] = attrs['v']
elif self.curr_relation:
self.curr_relation.tags[attrs['k']] = attrs['v']
Это сжимается до
if self.curr_elt:
self.curr_elt.tags[attrs['k']] = attrs['v']
если в других частях кода curr_node/way/etc заменить на curr_elt.
Насколько я помню, уровней вложенности в файле osm всего 1. Если больше, надо просто сделать стек из элементов, вроде такого:
#!/usr/bin/python
stack = []
def put(item):
stack.append(item)
def pop():
return stack.pop()
def set_property(data):
for k, v in data.items():
stack[-1].tags[k] = v
def get_id():
return stack[-1].id
Напомню, что если питоновский скрипт оформить фнкцией (да хоть main()), а в начале (до функции) дописать вызов psyco, то все числодробильные штуки начнут исполняться со скоростью, близкой к асмовой. Жаль, что только на 32-битных системах.
import psyco
psyco.full()
Да и плодить объекты не надо лишний раз, если критично именно время исполнения.
Чистый C/C++ будет быстрее работать, но его сложнее писать 
Ещё можно SteelBank Common Lisp, он работает так же быстро, как C. Только к нему доки и такие либы под XML фиг найдёшь
А поглядеть на этот код можно? Уж очень фантастически цифры выглядят. На Python с учетом всех оптимизаций больше 3500 объектов в секунду выжать не удалось.
Kaylee, прошу прощения за столь большую задержку!
Исходники выложил “как есть”… пока там сплошной мусор, ненужные закомменченые дебажные куски кода и прочее, но основную идею понять можно т.к. объем кода довольно маленький и даже должно работать!)) Но я сейчас не проверял… надеюсь в будущем дойдут руки привести все в порядок!
http://github.com/chertov/OpenStreetMap-MongoDB
Простите за этот позор, надеюсь хоть кому-нибудь пригодится 
если кому интересно то в базе
mongo -uosm -posm wildman.bn.by/osm
лежит дамп беларуси. в ближайшее время сделаю ежедневное обновление. пока что за 7-е число.
Совершенно обычная скорость.
Парсер моего конвертера обрабатывает planet.osm примерно 2 ч 40 м на обычном двухъядернике 2.6 ГГц 2006 г. без всяких RAID’ов.
Скорость обработки узлов составляет 139962.8 узлов/сек.
Собственно, такое указание скорости не совсем корректно. Лучше посчитать по-другому:
исходный файл - 204 Гб + результирующие файлы суммарным объемом около 49 Гбайт, то скорость обмена с диском составляет 26.3 Мб/сек.
Другими словами, скорость обработки определяется не столько производительностью процессора, сколько скоростью работы жесткого диска.
PS. Собственно, парсер работает хоть и на двухъядернике, но в 1 поток. Учитывая, что узким местом является производительность диска, я не стал заботиться о распараллеливании обработки на 2 ядра.
В том и прелесть компилируемых языков, что, если не делать откровенных глупостей, любой алгоритм обработки данных сложности O(n) упирается именно в производительность жесткого диска, а не процессора.
Кто заливал osm в mongo, какие объёмы базы получаются? У меня файл Новосибирской области (12 мегов bz2, или 120 распакованный) занял 1.1G. 
У меня получился скрипт, обрабатывающий 2.2К точек в секунду.
Что интересно, парсер .osm.bz2 > .json.bz2 на pypy работает медленнее, чем на стандартном питоне 2.6.
Поскольку для js есть xml-парсеры, попробую переписать питоновский скрипт на js, чтобы работал прямо в mongodb, получится компактнее и быстрее.
Как скомпилировать и запустить файл .cpp? Интересно попробовать, насколько будет быстро работать. Ещё вопрос, можно ли ему направить через stdin поток из распаковщика bz2?
Индексы пробовал, работают нормально, ускоряют очень хорошо. Можно сделать индекс по любому тегу:
(через pymongo)
db.way.create_index('tags.building:levels')
(если теги находятся в отдельном объекте: way = {_id: …, {tags: {building: ‘yes’, building:levels: 9}}})
Индекс работает ещё быстрее, если у каких-то объектов этого поля нет. То есть если хотите ставить разные флаги, лучше чтобы у большинства объектов флага не было, тогда по нему ищется быстрее. То же самое с сортировкой.
Запросы лучше делать пореже и доставать данные сразу одним. Например, если нужно по одиночке обработать точки из линии, лучше запросить их сразу все:
db.node.find({‘id’: {‘$in’: [id1, id2, …]}})
чем по одной.
Запрос update поддерживает только либо установку конкретного значения, либо увеличение или уменьшение на число, поэтому если нужно записать сложные вычисления, запросы придётся делать по одному.
Если lon и lat (именно в таком порядке) собрать в массив или в объект, можно сделать по ним пространственный индекс. Но единственная команда, которая доступна - поиск точек в определённых границах либо по расстоянию до них. Для подсчёта расстояний между парами точек и длин путей такая команда слишком медленная.
После замеров скорости работы скриптов на питоновском профайлере cProfile оказалось, что самая затратная операция - count(). Вызвать .count у запроса - в 4 раза дороже, чем .next().
Оказалось, что вызовы count занимают в моём скрипте больше половины времени, 160 секунд из 290.
Переделал скрипт. Было:
for node in db.nodes.find(...):
bad_neighbors = db.nodes.find({'_id': {'$in': node['neighbors']}})
while bad_neighbors.count() > 0:
for neighbor in bad_neighbors:
...
bad_neighbors.rewind()
Заменил на счётчик в виде переменной, который запускается в цикле.
for node in db.nodes.find(...):
bad_neighbors = db.nodes.find({'_id': {'$in': node['neighbors']}})
bad_neighbors_count = 0
while True:
for neighbor in bad_neighbors:
bad_neighbors_count += 1
...
if bad_neighbors_count == 0:
break
bad_neighbors.rewind()
Суммарное время сократилось до 134 секунд, из них 107 - на cursor.next, в которых один и тот же объект достаётся минимум дважды. Есть куда оптимизировать.
siberiano, стесняюсь спросить, с монгой никогда не работал - а while bad_neighbors: не работает, или не подходит по контексту?
Я написал плагин к Osmosis. После некоторого размышления я изменил структуру базы, убрав оттуда обратные ссылки (node → way, way → relation, relation → relation). Слишком большой оверхед при импорте получался.
Пока получается такая статистика:
Импорт Новосибирской области (с gis-lab.info) занимает 84 секунды из которых 10 уходит на создание нужных индексов. Машина – одноядерный Athlon 3200.
> db.stats()
{
"db" : "osm",
"collections" : 6,
"objects" : 967076,
"avgObjSize" : 62.81341693930984,
"dataSize" : 60745348,
"storageSize" : 109661952,
"numExtents" : 21,
"indexes" : 6,
"indexSize" : 67698688,
"fileSize" : 469762048,
"ok" : 1
}
Места действительно жрет как слон веники. Как это можно оптимизировать, не представляю.
Я пошагово удаляю соседей, которые не на перекрёстках и на ходу меняю список соседей. Поэтому когда ближайших обработал, надо запросить ещё раз, и так пока по всем направлениям не дойду до перекрёстков.
А my_cursor всегда переводится в True, даже если в нём пусто:
In [21]: x = db.routes.find({‘_id’: -1})
In [22]: 1 if x else 0
Out[22]: 1
Он оставляет место под расширения документов, чтобы если начнёшь писать в них новые свойства, не пришлось раскидывать кластерами по файлу.
Если ты что-то удалил из базы, чтобы сжать, нужно $ mongod --repair --dbpath=…
А какие индексы делаешь? Я для того чтобы сделать дорожный граф, создал единственный индекс - tags.highway.
Сейчас после небольшой работы с монго я пришёл к такой схеме:
-
исходную базу делать с минимумом информации, и в объекты ничего лишнего не писать, а лучше даже удалять лишнее сразу при импорте.
-
никаких рабочих вычислений на этой базе делать нельзя. Для предметной области нужно делать отдельную БД, и туда экспортировать объекты уже в том виде, в котором нужно.
-
Лучше держать немного больших документов, чем много мелких. Будет оптимальнее использоваться диск (больше реальных данных, меньше доля “заделов”). То есть нужно всё денормализовывать, чтобы не делать "join"ов. Чем меньше раз запрашиваешь курсор, тем лучше. Напротив, атомарная запись или запись одного документа в mongo очень быстрая, ею можно пользоваться часто.
-
потоковая конвертация с mongo - тормозная. Если есть возможность, лучше всё сразу считать в память, потом формировать объекты, какие нужно, и записывать. У меня размер коллекции в базе - 87 МБ, в памяти Питона те же объекты занимают 9 МБ.
Примерно к тем же выводам я и пришел. У меня две базы. Одна под минутную репликацию, вторая под геометрию. В основной базе три коллекции примерно такой структуры:
Nodes:
{
"_id" : NumberLong(32521222),
"lat" : 54.7724042,
"lon" : 83.1009863,
"tags": {"amenity": "parking"}
}
Ways:
{
"_id" : NumberLong(17237995),
"nodes" : [NumberLong(178727045), NumberLong(269537100)],
"tags" : { "highway" : "primary"},
}
Relations:
{
"_id" : NumberLong(129298),
"members" : [{
"ref" : NumberLong(23363997),
"type" : "way",
"role" : "to"
}, {
"ref" : NumberLong(35133693),
"type" : "way",
"role" : "from"
}, {
"ref" : NumberLong(248503088),
"type" : "node",
"role" : "via"
}],
"tags" : { "restriction" : "no_left_turn", "type" : "restriction" }
}
Индексы на полях ways.nodes и (relations.members.type, relations.members.ref). Без индексов не получится отслеживать изменения геометрии при изменении объекта. Что отсюда можно выкинуть, не представляю.
Основная проблема у меня в том, что для того чтобы построить геометрию, скажем, для вея, нужны координаты его точек, а это довольно тяжелая выборка. Выгрузить все ноды в память тоже не вариант. Для РФ они занимают 1Гб только в бинарном виде.
Кстати, а ты можешь расшарить в битторренте базу России? (mongodubp => bz2) Именно эти три коллекции.
Вот пример документа у меня в базе. При работе с ними никаких дополнительных запросов не нужно. Теги путей я уберу скоро, они не нужны. Из файла области таких документов получается ~36 000.
{
"_id" : 130763674,
"changeset" : 6422529,
"id" : 130763674,
"lat" : 55.0410469,
"lon" : 82.3909092,
"timestamp" : "2010-11-21T13:30:55Z",
"uid" : 183878,
"user" : "whalerich",
"version" : "9",
"routes" : [
{
"way" : [
{
"ref" : "M-51",
"highway" : "trunk"
},
{
"ref" : "M-51",
"highway" : "trunk"
},
{
"ref" : "M-51",
"highway" : "trunk"
}
],
"via" : [
130763195,
659857287
],
"id" : 210244290,
"len" : 721.3430402945971
},
{
"way" : [
{
"ref" : "M-51",
"highway" : "trunk",
"oneway" : "yes"
},
{
"ref" : "M-51",
"highway" : "trunk",
"oneway" : "yes"
},
{
"ref" : "M-51",
"highway" : "trunk",
"oneway" : "yes"
},
{
"ref" : "M-51",
"highway" : "trunk",
"oneway" : "yes"
},
{
"ref" : "M-51",
"highway" : "trunk",
"oneway" : "yes"
},
{
"ref" : "M-51",
"highway" : "trunk",
"oneway" : "yes"
},
{
"ref" : "M-51",
"highway" : "trunk",
"oneway" : "yes"
},
{
"ref" : "M-51",
"highway" : "trunk",
"oneway" : "yes"
}
],
"via" : [
997755222,
130763193,
997754917,
130763192,
997754958,
410845442,
410845443
],
"id" : 210244284,
"len" : 913.9816212646475
},
{
"way" : [
{
"name" : "Северный обход Новосибирска",
"highway" : "trunk"
},
{
"name" : "Северный обход Новосибирска",
"highway" : "trunk"
}
],
"via" : [
707377151
],
"id" : 389013040,
"len" : 335.20540758147973
}
],
"neighbors" : [
210244290,
210244284,
389013040
]
}
Дело мое движется время от времени…
Хочу описать некоторый алгоритм, чтобы стало себе понятнее)
Для быстрого отображения или редактирования карты хотелось бы иметь возможность быстро определить какие веи и “свободные” ноды входят целиком, “задевают” этот тайл или накрывают его.
(Если тайл лежит целиком внутри вея, то этот вей задает его цвет полностью и этот признак тоже хотелось бы иметь в базе.)
Алгоритм, который собирает эту инфу я и накодил. Наверняка есть баги какие-нибудь и пока нет поддержки дырок, но ее ввести достаточно легко вроде бы.
Работает эта штука следующим образом.
Алгоритм пробегает по всем веям в базе и делает с ними следующее:
Сперва находится тайл максимального уровня, который содержит в себе целиком данный вей.
Для этого берем любую точку вея и смотрю в каком тайле максимального уровня (например 15 или 17) она лежит. Смотрим лежат ли все остальные точки вея (ну или bbox вея) в этом же тайле. Если нет, то берем предка этого тайла и делаем аналогичную проверку для него. Когда мы получили тайл в котором лежат все точки вея, то этот тай будет для нас скажем “корневым”… тайлом с которого мы запустим итерационный процесс.
После этого составляется список тайлов для проверки. Пока в него добавляется только корневой тайл.
Проверка заключается в том что ищется пересечение тайла с веем… и тайлу ставится признак того полностью внутри ли он, полностью снаружи или на него попадает граница вея.
Если тайл полностью снаружи, то мы благополучно о нем забываем и выкидываем из списка.
Если тайл полностью внутри вея, то мы добавляем в базе этому тайлу признак того что вей такой-то накрывает тайл полностью, после чего тоже удаляем из списка.
Если тайл попал на границу вея, то мы оставляем его в списке, а в базу ничего не добавляем. (Хотя возможно и нужно добавить инфу о том что в базе будут его потомки. Чтобы потом было удобнее по всему дереву пробегать.)
После проверки всех тайлов и добавления информации в базу мы делим все оставшиеся в списке тайлы на 4 новых, уровень которых выше соответственно на единицу. Список конечно чистим от старых тайлов прошлого уровня. После чего запускаем тест снова. И так продолжается до какого-то максимального уровня…
Когда дошли до этого уровня, то сохраняем в базу инфу для каждого тайла. О том что он содержит вей такой-то…
Проиллюстрирую работу алгоритма на простом примере:
Но есть пример интереснее:
Думаю наверняка где-то это уже реализовано, но пока свой велосипед удобнее)
Думаю если держать такую информацию о тайлах в каком-то, ориентированном на быстрое чтение, виде, то можно сделать быстрый поиск необходимых веев и нодов для рендера карты.
Статистику не собирал, но много тайлов максимального уровня будет там где есть мелкие веи, населенные пункты и т.д. для лесов, морей, рек такой информации должно быть мало…
Рендер может определить цвет каких тайлов ему нужен исходя из то куда направлена камера.
Затем посмотреть есть ли эти тайлы в базе, вычислить их цвет исходя из информации о их предках, если их нет… или найти потомков и составить “представление” для данного тайла.
Получив id всех необходимых объектов для отрисовки выкидываем дубликаты и подгружаем того что нет в кэше… рисуем. На мой взгляд вроде бы идея имеет право на жизнь)
Правда тут у меня возникают некоторые вопросы, которые я еще не продумал) Например как лучше добавить разную геометрию для разных уровней… или отрезать вообще часть “глобальных” уровней сделав пререндер и т.д. Как удобнее и оптимальнее бегать по дереву тайлов и быстро использовать имеющуюся инфу, но надеюсь я на правильном пути.
Описывал по памяти… возможно где-то как-то алгоритм неправильно воспроизвел, но основная идея думаю понятна.
Если есть какие-то идеи по поводу оптимизации этого алгоритма или может что-нибудь в принципе другое для шустрого поиска того что нужно рисовать здесь и сейчас, заметите какие-то косяки, не стыковки и прочее - буду рад услышать!
Интересно. Кстати, попробовал на pypy 1.7, экспорт из .osm.bz2 в .json.bz2 получился чуть-чуть быстрее.