Комментарии 16
«Сжатые» — это compressed, а вы переводите из «succint».
Чтобы не смущать читателей, лучше взять другое слово (краткий/компактный/лаконичный), к тому же в статье они противопоставляются сжатым (на самом деле) структурам.
Спасибо, исправили.
Операция rank для указанного индекса считает количество битов, установленных в массиве до него:
То есть rank(0) равен 0, потому что в этой позиции ещё не установлено ни одного бита, rank(1) равен 1
В русском языке "до" означает "не включая". Обед не происходит "до обеда".
Лучше написать "вплоть до", "до и включая" или ещё как-нибудь.
Операция rank для указанного индекса считает количество установленных битов на отрезке от начала массива и до указанного индекса включительно.
Сейчас в тексте получается, что rank(0) всегда равен 0 для любого вектора, потому что считает только "отрицательные" биты, которых не существует.
Вот блин спрашивается, зачем писать такие статьи ! Тема интересная, но хоть объяснили бы что-нибудь ! Хотя бы на пальцах. Как например за константное время выполнять rank/select если для этого потребуется просмотреть весь массив, и время явно будет линейным ??? Или речь о каких-то разреженных массивах ??? Там тоже не понятно как будет с константным временем, а пожалуй и с логарифмическим. Полез код vers смотреть, но там без поллитры не разобраться, тем более на rust я не пишу. Хорошо хоть комментирует автор довольно подробно. Но все-таки хоть каких-то объяснений ждал здесь. Без этого такие статьи не имеют смысла.
Сам очень часто использую просто биты упакованные в int64_t для задания признаков какому-то набору объектов. Там всего три операции - set(size_t index), clear(size_t index) и check(size_t index). Там всё действительно мгновенно. И именно за константное время. Но понять как делаются ЗА КОНСТАНТНОЕ ВРЕМЯ rank/select, у меня просто не хватает воображения. Может кто-нибудь из читателей объяснит...
Вероятно чем то подобным
Для rank(3)
Кладем изначальный вектор в регистр [0101000]
Кладем маску [110000]
Получаем [01000000] ну или 2 в эквиваленте
Знаем, что у двойки всегда только один бит выставлен в 1 и, следовательно, вернем 1
Для rank(4) тогда маска бы совпала и дала число 10 -> 2
Select скорее всего подобным образом работает
Возможно, имелся в виду случай, когда данные укладываются в одно значение uint64. Там и теоретически время константное, так как данные дальше не растут, да и на практике используются интринсики, считающие количество единичек за одну инструкцию. В русте куча всяких таких битовых фокусов типа count_zeros или trailing_ones встроена сразу в целочисленные типы. Это удобно.
Согласен, насчёт константости - скорее всего враньё. А насчёт скорости: если посмотреть документацию на vers-vecs , то там написано
This crate uses compiler intrinsics for bit manipulation. The intrinsics are supported by all modern x86_64 CPUs, but not by other architectures. There are fallback implementations if the intrinsics are not available, but they are significantly slower. Using this library on x86 CPUs without enabling BMI2 and popcnt target features is not recommended.
The intrinsics in question are popcnt (supported since SSE4.2 resp. SSE4a on AMD, 2007-2008), pdep (supported with BMI2 since Intel Haswell resp. AMD Excavator, in hardware since AMD Zen 3, 2011-2013), and tzcnt (supported with BMI1 since Intel Haswell resp. AMD Jaguar, ca. 2013).
Ну Ч.Т.Д., одна команда работает с одним integer-регистром, или эквивалентной ячейке памяти.
Хотя мне кажется, нет смысла измерять количество команд, данные в регистре не берутся сами по себе обидно, поэтому следующий уровень - это кэш L1, точнее размер линии кэша. Скорее всего, не важно сколько инструкций выполнится, но пока они "вмещаются" в одну линию - время всё ещё постоянное, процессоры суперскалярные.
А вот ширина (внешней) линии данных процессора (например, 64 биты у 32-битного Пентиума), скорее всего не важен, потому что он меньше, чем ширина кэша. То есть должно получиться константное время до ширины кэша, а дальше резкий скачок и линейное.
С третьей стороны, по логике статьи, она делается для больших, многомегабайтных наборов данных. Выпендриваться так для пары килобайт просто незачем, скорость на маленьких размерах просто никому не интересна, наверное.
По поводу константного времени. Подразумевается, что у вас есть какая-то статическая структура, которую вы долго (ну или не очень, но уж точго не за константу, а хотя бы за один проход) инициализируете, а потом к ней применяете какие-то запросы (в данном случае rank-select). Инициализация долгая, но запросы быстрые. Вот простой пример как сделать rank-select за константу, но не succint:
Изначально у нас есть последовательность битов v_1, v_2, ... v_n.
Вычисляем за линейный проход частичные суммы s_i=s_{i-1}+v_i и кладем в массив. rank(i) -- это просто s_i
Вычисляем за линейный проход чем-то вроде `for(i = 0; i < v.size(); ++i) { if (v[i] ) p.push_back(i); }` в итоге в массиве p у нас позиции единичных битов, select(i) -- это просто p[i].
Собственно ценность succint структур в том, чтобы не хранить два отдельных вектора с числами, а делать это как-то хитро, чтобы занимало меньше памяти.
P. S. Я сам очень увлекаюсь такими структурами и если на хабре есть такой запрос, то с удовольствием сделаю подробный обзор по ним. Для самостоятельного изучаения рекомендую вот эту репу
Мне кажется, что это будет отличный технический материал.
Хорошо, готовлю
FYI на хабре уже есть добротная статья
Спасибо за ссылку :-)
Действительно, статья гораздо лучше. Даже первая фраза статей
Несколько месяцев назад в поисках идей по ускорению кода
или
Как быть, если дерево поиска разрослось на всю оперативку
Учитывая, что алгоритмы в статья очевидно замедляют доступ, а не ускоряют, то в этой статье сразу начинается "разрыв шаблона"
Ещё вроде бы в шахматных программах такие же структуры должны использоваться, потому что там тоже все в размер и скорость памяти упирается.
Нет там, конечно, константного. По ссылке Матвеева есть текст и графики. В тексте есть ДВЕ узко-специальных структуры для специальных запросов. И только про эти два частных случая говорится о константе:
An Elias-Fano encoding of monotone sequences supporting constant-time predecessor/successor queries.
Two Range Minimum Query vector structures for constant-time range minimum queries.
Кроме того явно сказано
An increase in all runtimes can be observed for input sizes exceeding the L2 cache size (16 MB).
А вот графики "rank, randomized input" любопытные: там действительно почти постоянная производительность до 100 миллионов битов. А для основной реализации вообще сначала работа очень медленная, но по мере роста от 1 до 1000 битов всё быстрее и быстрее.
Какая конкретно работа тут подразумевается - не знаю. 1 создание и заполнение на 1 запрос, или 1 раз создали и потом миллион запросов...
Ничего не понятно, но очень интересно
Компактные структуры данных