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