А какие требования к структуре? Планируется только доставать триты по индексу, или еще искать по значению, добавлять, удалять? Известна ли верхняя граница количества тритов? Какой желателен компромисс между скоростью и объемом (т.е. есть ли ограничения на объем)?
Ты правильно сказал, что количество 0 в LBS совпадает с количеством узлов дерева + 1. А фейковый корень добавляется для того, чтобы количество 1 точно совпадало с количеством узлов.
Поэтому select0(i + 1) — это не только индекс 0 в фрагменте LBS, относящемся узлу i — 1. Это индекс 0 перед той самой 1, которая по номеру совпадает с номером искомого первого потомка. Иными словами, select0(i + 1) + 1 — индекс единицы в LBS, номер которой — и есть номер первого потомка i.
Этот индекс нужно превратить в номер узла, и для этого используется rank1:
firstChild(i) = rank1( select0(i + 1) )
Получили еще одну формула для firstChild(i). Также известно соотношение между rank и select:
select0(x) = y
rank0(y) = x
rank1(y) = y — x
select0(i + 1) — i выводится из этого соотношения и второй формулы firstChild(i). Заранее извиняюсь, если где напутала с +-1.
P.S. Еще есть формула, определяющая зависимость rank0 и rank1 (для select чего-то похожего нет):
i = rank0(i — 1) + rank1( i — 1)
Следуя логике «2N — это O(N)», у зависимостей
f(N) = 10N,
g(N) = N + lg(N),
h(N) = N + 8
одинаковая асимптотика. Если не вылезать за рамки теоретической математики, то почему бы не огрубить до верхней границы O(N). Это верно.
Но речь идет про девайсы с ограниченной памятью, на них не удастся рассматривать эти функции как предельные с N -> inf. И f(N) = O(N), g(N) = N + o(N) и h(N) = N + O(1) уже нельзя назвать ростом одного порядка. f = O(N) — это оценка сверху, в которой N может быть помножено на любую константу, а f = N — это четкая гарантия N, без потенциального удвоения или утроения памяти.
2N возрастает строго как 2N. На константу не домножается.
O(N) возрастает линейно от N, то есть N может быть домножено на любую константу (да, в том числе на 2, но может и на 10).
У узла i есть сосед i + 1 на том же уровне дерева (иными словами, узел не является крайним справа в ряду), если выполняется условие: x = select1(i + 1) + 1
LBS[x] == 1
Есть ли у узла с i=4 (буква «е») сосед i+1?
x = select1(4 + 1) + 1 = 8
LBS[8] = 1
Да, i + 1 — сосед.
Есть ли сосед у узла с i=5 (буква «о»)?
x = select1(5 + 1) + 1 = 9
LBS[9] = 0
Нет, i + 1 не является соседом, он находится уже на следующем уровне иерархии.
P.S. Спасибо, опечатку в childrenCount(i) исправила.
С предподсчетом все не так страшно, как может показаться.
Во-первых, спасают оптимизации на аппаратном уровне: в большинстве процессоров реализован 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») — это исчезающе крошечная часть приложения, которое не стыдно назвать картой.
Поэтому select0(i + 1) — это не только индекс 0 в фрагменте LBS, относящемся узлу i — 1. Это индекс 0 перед той самой 1, которая по номеру совпадает с номером искомого первого потомка. Иными словами, select0(i + 1) + 1 — индекс единицы в LBS, номер которой — и есть номер первого потомка i.
Этот индекс нужно превратить в номер узла, и для этого используется rank1:
firstChild(i) = rank1( select0(i + 1) )
Получили еще одну формула для firstChild(i). Также известно соотношение между rank и select:
select0(x) = y
rank0(y) = x
rank1(y) = y — x
select0(i + 1) — i выводится из этого соотношения и второй формулы firstChild(i). Заранее извиняюсь, если где напутала с +-1.
P.S. Еще есть формула, определяющая зависимость rank0 и rank1 (для select чего-то похожего нет):
i = rank0(i — 1) + rank1( i — 1)
f(N) = 10N,
g(N) = N + lg(N),
h(N) = N + 8
одинаковая асимптотика. Если не вылезать за рамки теоретической математики, то почему бы не огрубить до верхней границы O(N). Это верно.
Но речь идет про девайсы с ограниченной памятью, на них не удастся рассматривать эти функции как предельные с N -> inf. И f(N) = O(N), g(N) = N + o(N) и h(N) = N + O(1) уже нельзя назвать ростом одного порядка. f = O(N) — это оценка сверху, в которой N может быть помножено на любую константу, а f = N — это четкая гарантия N, без потенциального удвоения или утроения памяти.
O(N) возрастает линейно от N, то есть N может быть домножено на любую константу (да, в том числе на 2, но может и на 10).
x = select1(i + 1) + 1
LBS[x] == 1
Есть ли у узла с i=4 (буква «е») сосед i+1?
x = select1(4 + 1) + 1 = 8
LBS[8] = 1
Да, i + 1 — сосед.
Есть ли сосед у узла с i=5 (буква «о»)?
x = select1(5 + 1) + 1 = 9
LBS[9] = 0
Нет, i + 1 не является соседом, он находится уже на следующем уровне иерархии.
P.S. Спасибо, опечатку в childrenCount(i) исправила.
Во-первых, спасают оптимизации на аппаратном уровне: в большинстве процессоров реализован 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