Succinct data structures for PythonЯзык Python, его эволюция и использование

Доклад отклонён
Константин Игнатов
Qrator Labs CZ s.r.o.

Выпускник МГТУ им. Баумана и Высшей Школы Экономики.
Инженер-разработчик в отделе исследований Qrator Labs.

@podshumok
Тезисы

Когда мы говорим о минимально возможном размере целочисленного массива в байтах, то обычно нас интересует только, сколько элементов будет всего, и насколько большое значение будет храниться в этом массиве. Никакая другая информация о хранимых данных нам не поможет: если максимальное хранимое значение - это '2**64 - 1', и всего элементов 1073741824, то будет съедено порядка 8 гигабайт плюс оверхед. Даже если мы знаем, что остальные элементы не намного меньше, или если они почти все одинаковые, или есть какой-то повторяющийся паттерн в массиве, всё равно это будет восемь гигов, а найти все вхождения некоторой подпоследовательности в таком массиве - это операция, сложность которой также не зависит от того, какие данные там хранятся.

Но в теории это всё не так. Существуют структуры данных, которые помогают использовать информацию о распределении данных для более эффективного использования как памяти, так и вычислительных ресурсов.

Succinct или лаконичные структуры данных дают именно это - близкое к теоретически минимальному потребление памяти и вычислительных ресурсов.

Обычно подобные структуры данных можно встретить только, скажем, в реализации индексов баз данных. Но теперь они есть в распоряжении любого пайтониста - при помощи библиотеки, которую я собираюсь представить.

Другие доклады секции Язык Python, его эволюция и использование