2.3 KiB
2.3 KiB
Другой дизайн
Roaring map
- описание здесь
хранить сразу расшифрованный set
- WIP здесь
- огромная часть ресурсов уходит не на просмотр включения множеств, а на декодирование set-строк
- при возможности хранить больше данных за более дешёвое сравнение - прекрасно
- тупо условный формат:
<bpp> <последовательно упакованные bpp-битные хеши>
- Shannon–Fano–Elias coding как одна из идей, но надо глубже копать
Группировать, а не хэшировать
- если была бы возможность точно делать соответствия между label и id, то provides стал бы в большинстве последовательным, а required было бы легко искать в P.
Доработки на текущий дизайн
битовый prefilter
- Позволяет отбросить заведомо ложные варианты
- но так ли часто это будет срабатывать, но вызывает доп расходы при высчитывании
- фильтр Блума как пример
- В теории хэш можно заменить на него
- необходимо знать, насколько больше будет ложноположительных срабатываний
- В теории хэш можно заменить на него
улучшить проход по массивам
- Можно provides хранить не в виде массива, а сразу как хэш-структурку
- если provides строка кэшируется не так часто, смысла не будет
Прочие улучшения
улучшение работы с хэшем
- если условно "отсортировать" массив provides/requires, можно получить лучшую работу с кэшом
- (надеюсь, что под капотом оно уже и так это делает, но проверить стоит)