Мария Рубаненко (Fintech AI, Team lead DS) Повышаем производительность программ: мой путь к succ[ess | inct]

По мере увеличения объёма данных, структуры данных, занимающие много дополнительного места, становятся всё менее производительны и возникает вопрос: как оптимально сжать структуру данных по памяти, чтобы не потерять производительность основных операций на структуре. В докладе разберёмся со сжатыми структурами данных, их практической реализацией, а также посмотрим для каких задач их целесообразно применять.

Видео: https://moscowpython.ru/meetup/101/increase-soft-perfomance/

Moscow Python: http://moscowpython.ru
Курсы Learn Python: http://learn.python.ru
Moscow Python Podcast: http://podcast.python.ru
Заявки на доклады: https://bit.ly/mp-speaker

Transcript

1. Повышаем производительность программ: мой путь к succ[ess | inct] Рубаненко Мария МФТИ / Fintech AI / ШАД(Яндекс) 2025
2. Содержание 2 • 1. Терминология сжатия • 2. Суперсжатые структуры данных ❏ 2.1. Операции access / rank / select ❏ 2.2. Как сжать битовый массив ❏ 2.3. Суперсжатый битовый массив ❏ 2.4. Вейвлет-дерево ❏ 2.5. Как суперсжимать дерево • 3. Область применения суперсжатых структур данных • 4. Как реализовать суперсжатую структуру данных ❏ 4.1 Pysdsl ❏ 4.2 Sux ❏ 4.3 Facebook’s folly • 5. Выводы
3. 1. Терминология сжатия 3 Compressed data structure = Сжатая структура данных • без потерь • с потерями Implicit data structure = Эффективная структура данных X + O(1) bit of Space, где X - нижняя граница теории информации Succinct data structure = Суперсжатая структура данных X + o(X) bit of Space, где X - нижняя граница теории информации Compact data structure = Компактная структура данных O(X) bit of Space, где X - нижняя граница теории информации
4. 2. Суперсжатые структуры данных 4 • 1. Терминология сжатия • 2. Суперсжатые структуры данных ❏ 2.1. Операции access / rank / select ❏ 2.2. Как сжать битовый массив ❏ 2.3. Суперсжатый битовый массив ❏ 2.4. Вейвлет-дерево ❏ 2.5. Как суперсжимать дерево • 3. Область применения суперсжатых структур данных • 4. Как реализовать суперсжатую структуру данных ❏ 4.1 Pysdsl ❏ 4.2 Sux ❏ 4.3 Facebook’s folly • 5. Выводы
5. 2.1. Операции access / rank / select 5
6. 2.1. Операции access / rank / select 6
7. 2.1. Операции access / rank / select 7
8. 2.1. Операции access / rank / select 8
9. 2.1. Операции access / rank / select 9
10. 2.1. Операции access / rank / select 10
11. 2.2. Как сжать битовый массив 11
12. 2.2. Как сжать битовый массив 12
13. 2.3. Суперсжатый битовый массив 13
14. 2.3. Суперсжатый битовый массив 14
15. 2.3. Суперсжатый битовый массив 15
16. 2.3. Суперсжатый битовый массив 16
17. 2.3. Суперсжатый битовый массив 17
18. 2.4. Вейвлет-дерево 18
19. 2.4. Вейвлет-дерево 19
20. 2.4. Вейвлет-дерево 20
21. 2.4. Вейвлет-дерево 21
22. 2.4. Вейвлет-дерево 22
23. 2.4. Вейвлет-дерево 23
24. 2.4. Вейвлет-дерево 24
25. 2.4. Вейвлет-дерево 25
26. 2.4. Вейвлет-дерево 26
27. 2.4. Вейвлет-дерево 27
28. 2.4. Вейвлет-дерево 28
29. 2.4. Вейвлет-дерево 29
30. 2.4. Вейвлет-дерево 30
31. 2.4. Вейвлет-дерево 31
32. 2.4. Вейвлет-дерево 32
33. 2.4. Вейвлет-дерево 33
34. 2.5. Как суперсжимать дерево 34
35. 2.5. Как суперсжимать дерево 35
36. 2.5. Как суперсжимать дерево 36
37. 2.5. Как суперсжимать дерево 37
38. 2.5. Как суперсжимать дерево 38
39. 2.5. Как суперсжимать дерево 39
40. 3. Область применения суперсжатых структур данных 40 • 1. Терминология сжатия • 2. Суперсжатые структуры данных ❏ 2.1. Операции access / rank / select ❏ 2.2. Как сжать битовый массив ❏ 2.3. Суперсжатый битовый массив ❏ 2.4. Вейвлет-дерево ❏ 2.5. Как суперсжимать дерево • 3. Область применения суперсжатых структур данных • 4. Как реализовать суперсжатую структуру данных ❏ 4.1 Pysdsl ❏ 4.2 Sux ❏ 4.3 Facebook’s folly • 5. Выводы
41. 3. Область применения суперсжатых структур данных 41 ▪ Поиск информации • поиск документов • поисков шаблонов в документе • автодополнение поискового запроса • индексы поиска ▪ ML • эмбеддинги языковой модели • ранжирование документов • генерация синтетической речи • распознавание речи на определенную тему ▪ Криптография • Неинтерактивные протоколы доказательства с нулевым разглашением • Гомоморфное шифрование
42. 3. Область применения суперсжатых структур данных 42 ▪ Мобильные приложения ▪ Медицинские данные (ДНК) ▪ Потоковая обработка данных
43. 4. Как реализовать суперсжатую структуру данных 43 • 1. Терминология сжатия • 2. Суперсжатые структуры данных ❏ 2.1. Операции access / rank / select ❏ 2.2. Как сжать битовый массив ❏ 2.3. Суперсжатый битовый массив ❏ 2.4. Вейвлет-дерево ❏ 2.5. Как суперсжимать дерево • 3. Область применения суперсжатых структур данных • 4. Как реализовать суперсжатую структуру данных ❏ 4.1 Pysdsl ❏ 4.2 Sux ❏ 4.3 Facebook’s folly • 5. Выводы
44. 4.1. Pysdsl 44 https://github.com/QratorLabs/pysdsl
45. 4.1. Pysdsl 45
46. 4.1. Pysdsl 46
47. 4.1. Pysdsl 47
48. 4.1. Pysdsl 48
49. 4.1. Pysdsl 49
50. 4.1. Pysdsl 50
51. 4.1. Pysdsl 51
52. 4.1. Pysdsl 52
53. 4.1. Pysdsl 53
54. 4.1. Pysdsl 54
55. 4.1. Pysdsl 55
56. 4.2. Sux 56 https://github.com/vigna/sux
57. 4.2. Sux 57
58. 4.3. Facebook’s folly 58 https://github.com/facebook/folly
59. 5. Выводы 59 • 1. Терминология сжатия • 2. Суперсжатые структуры данных ❏ 2.1. Операции access / rank / select ❏ 2.2. Как сжать битовый массив ❏ 2.3. Суперсжатый битовый массив ❏ 2.4. Вейвлет-дерево ❏ 2.5. Как суперсжимать дерево • 3. Область применения суперсжатых структур данных • 4. Как реализовать суперсжатую структуру данных ❏ 4.1 Pysdsl ❏ 4.2 Sux ❏ 4.3 Facebook’s folly • 5. Выводы
60. 5. Выводы 60 Ограничения суперсжатых структур данных: • В большинстве случаев работают только со статическим набором данных • Шаблон доступа к памяти часто не локален • Реализация с нуля сложна • Известные алгоритмы необходимо адаптировать для быстрой работы с суперсжатыми структурами данных Преимущества суперсжатых структур данных: • Позволяют индексировать большие наборы данных (примерно в 10-100 раз больше по сравнению с классическими индексами). • Адаптируются к данным: например, фиксируют повторы • Реализация с нуля сложна • Предоставляют дополнительную функциональность • Не ограничиваются только индексацией текста
61. Спасибо за внимание!
62. • Материалы к докладу: 1. https://github.com/mariyana-rubanenko/MoscowPython_101 2. https://vkvideo.ru/@club230164570 3. https://www.youtube.com/@so_besy 62 • Контактная информация: telegram - https://t.me/maryrubik GitHub VK YouTube