всем привет.
есть задача: хранить в памяти несколько десятков миллионов строк произвольной длины (плюс, условно, уникальный идшник им соответствующий) и проверять поток входящих ивентов (15к епс) на предмет присутствия в них этих строк.

я сейчас взял для этого дела indexmap (https://docs.rs/indexmap/1.3.2/indexmap/), но возник вопрос: может умные люди что-то более подходящее подскажут для этого дела?

набор строк может меняться динамически, так что время на создание этой структуры имеет значение
скорее даже в первую очередь имеет значение время построения/изменения, во вторую - потребление памяти, в третью - скорость поиска по ней (но полный перебор не подойдет)

https://docs.rs/aho-corasick/0.7.10/aho_corasick/ ?

я, может, заблуждаюсь, но разве ахо корасик это не наоборот оверхед на добавление/удаление строк?
там же дерево надо строить

Да, там оффлайн построение, но поиск оптимален. Просто не очень понятно из описания, насколько все динамично - может раз в какое-то время можно автомат перестраивать. Построение в AC простое за линейное время.

ну я выше писал, что приоритет на добавление/удаление строк и на объем, так что перестраивать каждый раз, пожалуй, не вариант.

Ну тогда просто trie без suffix links, подходит под описание по идее. Правда не уверен, что есть в виде готового крейта.

Я не очень понял. Надо для каждого события понять, входит ли оно в набор? Или что какая-то его подстрока входит в набор?

стрикт матч

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

Тогда да, строй бор (aka trie).

окей, сейчас почитаю, спасибо за советы )

Некий enum без PartialEq, чтобы в тестах вместо assert_eq!(a, MyVariant(b)) писать assert!(matches!(a, MyVariant(B))). Например.

Ещё bloom filter может помочь. Но это не точно.

Либо bloom filter поставить перед trie для скорости.

Из блум фильтра удалять не очень)

Подскажите над реализацией. Есть веб-сервис, к нему приходит запрос с каким-то параметром.
Есть какая-то логика в другом потоке, которая относительно долго отрабатывает (пару секунд).
Когда на сервис приходит запрос, нужно отправить новую задачу этой логике и ждать результата.
Как правильно должна быть устроена логика, как она должна принимать задачи и оповещать об окончении и готовности результатов для “подписчиков”

А из trie? 😉

А из trie O(n) от длины строки. Быстрее ты даже хэш не посчитаешь.

А смысл удалять?