С предподсчетом все не так страшно, как может показаться.
Во-первых, спасают оптимизации на аппаратном уровне: в большинстве процессоров реализован popcnt, который быстро считает количество установленных битов в слове. Интел довольно давно разработал набор команд SSE4 с POPCNT для регистров 16, 32, 64 бита. AMD — аналогично. А также есть вариации с ускорением посредством SIMD.
Если забыть про аппаратное ускорение, то конечно есть техники для предподсчета rank таким образом, чтобы не раздувать занимаемое пространство. Многие из них основываются на списках с пропусками для блоков битовой строки. Но это очень большая тема, тянет на отдельную статью с красивыми графиками сравнения производительности и занимаемых ресурсов.
Значения rank для битового массива — это неубывающая последовательность, в которой могут встречаться равные соседние элементы.
rank1(2) = 1, но также и rank1(0) = 1, rank1(1) = 1. select1(1) = 0 соответствует первому инкременту: rank1(0) = 1.
Сам MapProxy можно развернуть как тайловый кэш или WMS-сервер. А утилита mapproxy-seed генерит тайлы по различным сценариям, в том числе для полностью оффлайн-решений.
«Сделать мобильную карту за пару дней» — заголовок немного нечестный, не находите?
Со звездочкой и сноской мелким шрифтом «без учета времени на разработку сидинга тайлов, их обновления в приложеньках пользователей, переключения языков для слоев названий и других первоочередных штук». А как быть с оптимизацией наполнения/размера тайлов, чтобы они не сожрали все место и весть трафик?
Вскользь упоминается, как лекго прикрутить FTS на SQLite. Но сделать юзабельный поиск на данных OSM — крайне нетривиальная задача. Даже Nominatim часто лажает с российскими адресами и ранжированием результатов.
А как быть с предобработкой осмерских фантазий — тысячеэтажных домов, дворцов культуры с amenity=«brothel», кашей из тэгов?
Вменяемые офлайн-карты можно пересчитать по пальцам (и да, 2ГИС определенно хорош). Это наталкивает на мысль, что андроид-активити, заполненный из getMapFile(«cyprus.map») — это исчезающе крошечная часть приложения, которое не стыдно назвать картой.
Во-первых, спасают оптимизации на аппаратном уровне: в большинстве процессоров реализован popcnt, который быстро считает количество установленных битов в слове. Интел довольно давно разработал набор команд SSE4 с POPCNT для регистров 16, 32, 64 бита. AMD — аналогично. А также есть вариации с ускорением посредством SIMD.
Если забыть про аппаратное ускорение, то конечно есть техники для предподсчета rank таким образом, чтобы не раздувать занимаемое пространство. Многие из них основываются на списках с пропусками для блоков битовой строки. Но это очень большая тема, тянет на отдельную статью с красивыми графиками сравнения производительности и занимаемых ресурсов.
rank1(2) = 1, но также и rank1(0) = 1, rank1(1) = 1. select1(1) = 0 соответствует первому инкременту: rank1(0) = 1.
Было бы интересно почитать про этажи.
По поводу сидинга — еще есть mapproxy-seed, тоже удобная штука для генерации тайлов из osm или из собственного источника.
Со звездочкой и сноской мелким шрифтом «без учета времени на разработку сидинга тайлов, их обновления в приложеньках пользователей, переключения языков для слоев названий и других первоочередных штук». А как быть с оптимизацией наполнения/размера тайлов, чтобы они не сожрали все место и весть трафик?
Вскользь упоминается, как лекго прикрутить FTS на SQLite. Но сделать юзабельный поиск на данных OSM — крайне нетривиальная задача. Даже Nominatim часто лажает с российскими адресами и ранжированием результатов.
А как быть с предобработкой осмерских фантазий — тысячеэтажных домов, дворцов культуры с amenity=«brothel», кашей из тэгов?
Вменяемые офлайн-карты можно пересчитать по пальцам (и да, 2ГИС определенно хорош). Это наталкивает на мысль, что андроид-активити, заполненный из getMapFile(«cyprus.map») — это исчезающе крошечная часть приложения, которое не стыдно назвать картой.
Ссылка на игру в Google Play