Префиксное дерево на миллионы правил, Олег Кошовец: Lua in Moscow 2019 Meetup

Рет қаралды 709

4 жыл бұрын

В рамках разработки очередной фичи для S3 Object Storage возникла задача сопоставления имени объекта с различными префиксами и постфиксами. Задача сопоставления строки с префиксным правилом не выглядит сложной, но все становится интереснее, если таких правил миллион. Конкретно эту задачу мы решали с помощью префиксных деревьев, на примере построения и работы с этими деревьями я расскажу, какие проблемы могут возникнуть при работе с "хитрыми" структруами данных в Lua, и как эти проблемы решали.

Пікірлер: 6

@user-ne4bd3ry1n 22 күн бұрын

Сишка в проекте - это всегда страшно ... )

@ilyarozhok9167 4 жыл бұрын

Олег, крутое выступление! Люблю твой подход к изложению информации, лукас

@VADemon 4 жыл бұрын

Так как все строки в Lua дедуплицируются по умолчанию, самим языком (string interning/string pooling), то разбивать строку на префиксы по 1-2-3 символа противоречит самой задаче. Правильно было бы разбивать по логическим элементам (допустим путь к файлу разбивается на папки по-элементно, а названия файлов (т.к. они будут похожи, но не одинаковы) - так, как Олег описывает - префиксово-посимвольно) Хотя позже они в постановке задачи решили, что все префиксы правил будут уникальными - это противоречит идее string interning, пришлось бы с этого момента по-другому думать.

@VADemon 4 жыл бұрын

Так и не нашел ни его, ни ссылок на Гитхаб, ничего :/

@Tarantool 4 жыл бұрын

Держите ссылку :) github.com/okoshovetc/prefix_trees

@VADemon 4 жыл бұрын

@@Tarantool Ого, спасибо всем!