за реализаию я был бы премного благодарен - нужно кучу всего бенчить для approximate searching

Сейчас попробую найти. Там был marathon match на topcoder, там куча реализаций.

Потому что давно всё написано.

А что не так-то?

А что не так-то?

то, что позиция "алгоритмы нужны только для собеседований и все давно написано" - очень наивная

то, что позиция "алгоритмы нужны только для собеседований и все давно написано" - очень наивная

Результатов: примерно 345 000

Результатов: примерно 345 000

Кого забанить?

Кого забанить?

#supapro

давай рулеткой выберем?

Approximate regexp?

agrep это ты имел ввиду?

ну я так понял строки?

Я не знаю либы

Ну как там это делается, алгоритм т9, посмотри

У Сэджвика

Ну тебе нужно как-то переопределить оператор<() м)

Что для тебя означает приблизительный поиск? Формализуй эти требования и ты их легко закодируешь

Что для тебя означает приблизительный поиск? Формализуй эти требования и ты их легко закодируешь

Наверное быстрые алгоритмы не публикуют. Может можно узнать как там у duckduckgo

Ладно, я не знаю что тебе нужно)

мне нужны в идеале (в порядке убывания идеальности): 1) Либа с такими алгоритмами, которые я могу просто дёргать 2) Проект, откуда я могу эти алгоритмы спокойно утащить и где они номроально написаны 3) Ссылки на бумаги, которые описывают действительно эффективные алгоритмы 4) Просто полезные ссылки на бумаги Также всякие бенчамрки будут просто бесценны

https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=10390&rd=13800&cr=15805598&subnum=5 https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=10390&rd=13801&cr=9987185&subnum=2 Можешь из этих двух решений попробовать вытащить реализации.

Но о портируемости и production ready коде там речи нету, конечно.

Но о портируемости и production ready коде там речи нету, конечно.

но реализации, конечно, зашкварны. И судя по всему, парни выжимали, что могли

Опишу еще раз всю ситуацию TLDR Откуда брать mpsc queue, которую можно ждать в epoll или почему таких нигде нету? Есть несколько потоков, в каждом из них крутится epoll. Потокам нужно слать друг другу сообщения. Когда потоку приходит сообщение он должен пробуждаться из epoll-а. Разбудить поток можно разными способами: eventfd, pthread_signal, pipe наконец. Пробуждаться каждые x миллисекунд и проверять очередь так себе вариант. Как именно будить имхо не очень важно, системный вызов и пробуждение потока это уже относительно долго. Но допустим используется eventfd, как будто созданный именно для этого. Для отправки сообщений хочется использовать mpsc queue. При этом ее нужно как-то скрестить с eventfd, чтобы fast path в eventfd не писал вообще. То есть хочется хочет делать write в eventfd только когда consumer действительно спит в epoll. Это можно сделать обернув очередь в семафор внутри которого не futex, а eventfd. Но нигде не видел реализации такого семафора. Более того интуитивно кажется что оборачивать очередь в семафор не оптимально, оптимальней встроить eventfd в саму очередь. Но таких очередей тоже что-то не видно.

А почему не очередь с conditional_variable у каждого потока? Чем вызвана необходимость использовать epoll?

Тем что каждый поток может работать с сетью.

я думаю он бенчмаркает бустовский fuzzy_search

А что у тебя за задача-то?

А! Так вы делаете многопоточный actor? Прикольно, неожиданно. У вас особые требования к latency? Реализаций мало, так как обычно используют proactor, а там один epoll + очередь задач из которой многие потоки тянут себе "работу". Всё сетевое идёт через единственный epoll, готовое сетевое событие ставится в очередь задачь, свободный поток его забирает.

в бусте его ещё нет ?

там есть левенштейн

да, автомат меньше где встречается

никак не могу найти плюсовую реализацию. Наверное придётся портировать с шарпа какого-нибудь

Не проще свою навелосипедить?

Айфонная клава предлагает исправить "навелосипедить" на "на велосипед тьмы", но все же

а есть какая-нибудь общепринятая либа для работы с конечными автоматами?

можно взять libgfsm, алгебраически levenshtein automaton легко строится (если я правильно понял, что это)