https://github.com/abseil/abseil-cpp/commit/535f22b4a08a11166c91fabc22fe130933c745a7#diff-63e37c19fd975193f3b7ebfc5bf0a0d0b47761463d5c683df93e2823999be1faR256
Прикольно

В общем я не специалист по написанию sql/etc запросов, хоть и пишу бд.

Сейчас узнал (из issue) про забавный хак: ORDER BY RAND() LIMIT N. Собственно идея в том чтобы получить N случайных записей из таблицы (зачем нужно уже это без понятия, но прикольно).

https://youtu.be/ugw0lQoATB4
Мне тут ютуб порекомендовал любопытный доклад про различные заброшенные опенсурс субд.
Кстати про несколько систем из списка слышал, но вообще довольно грустно

В целом как-то не было особо времени/желания писать посты, на работе как то загружено, а остальное время занимался яклибом.
Между прочим я уже скоро два месяца как в Кельне, и в общем мне тут нравится.
Мои опасения по поводу отсутствия разнообразия в местной кухне не оправдались, а работать из офиса намного лучше ;)

Вы наверно знаете, что такое конечные автоматы.
Но возможно, как и я до недавнего времени, не слышали об FST.

По сути это тоже конечный автомат, где переход помимо входной метки содержит выходную (она может быть из другого алфавита), плюс можно добавить вес (которому нужно быть элементом полукольца только если вам нужны все свойства и алгоритмы).
Почему у этого есть отдельное название? Вероятно потому что для fst придумали алгоритмы минимизации, конкатенации и тд, которые сохраняли бы получившуюся структуру.
В целом теория неплохо описана в статье.

Еще эта структура данных примечательна тем, что имеет полезные применения:
- Используется для хранения словаря термов (и не только) в lucene и других поисковых движках. Кстати в качестве полукольца веса может быть и строка
- В распознавании речи в kaldi, статья довольно подробно описывает зачем, только учитывайте, что за исключением части раздела 2 и раздела 4 это по большей части повторение первой статьи.

Как я думаю следствием этого является наличие вменяемых имплементаций.
Например гугловая библиотека C++ OpenFST, ее используют kaldi и например мы в ArangoDB.

Поэтому если вам нужна библиотека обычных конечных автоматов (к сожалению я не встречал нормальных, в основном про fsm в компайл тайме для функций) можно использовать FST.
Например я недавно использовал для поиска наибольшего общего префикса.

Но зачем вообще в ArangoDB OpenFST? Мы используем ее в https://github.com/iresearch-toolkit/iresearch (аналог lucene), правда с некоторыми патчами.
Поставьте нам в iresearch звездочку кстати!

К сожалению OpenFST не без недостатков, что неудивительно учитывая что либа была написана еще в 2000-ых:
- bazel/make как система сборки, это типичный недостаток гугловых/старых либ, но это не большая проблема, можно написать свой простенький cmake для нужного вам (есть в iresearch)
2. То что это все живет не на условном github/gitlab/etc, хз принимают ли они патчи например, ну и в целом мне кажется это сказывается на активности разработки.
3. В либе много довольно странного API, который стоило бы задеприкейтить.
В целом ощущение что оно почти не развивается

Если же говорить про другие библиотеки fst, я видел несколько любопытных на rust:
- Попытка переписать openfst
- Реализация fst на rust, которая используется в tantivy
Собственно имплементация в lucene
Вроде бы еще что-то есть на java но я не интересовался

Еще постараюсь до нг написать про fault-injection немного и геометрию

Всех с наступающим/наступившим новым годом!
В общем надеюсь что новый год будет лучше чем этот для всех нас.

Кстати YACLib добавили в conan!
https://github.com/conan-io/conan-center-index/pull/14006

https://quick-lint-js.com/blog/cpp-vs-rust-build-times/
Оно конечно немного стрёмно, в духе сравнения apple clang 14 (что примерно соответствует 12-13 llvm clang) и llvm clang 15
Но любопытно и впечатляет насколько много бесполезного было сделано

Давно не писал, чем я вообще занимаюсь

Читаю книжки:
1. https://nlp.stanford.edu/IR-book/information-retrieval-book.html — про идеи и алгоритмы, которые стоят за поиском.
В целом, я многое уже знал по работе, но мне нравится, то что структурирует мои знания и в целом более теоретический взгляд.
Ещё в очередной раз убедился насколько книжки с упражнениями лучше, чем книжки без них, единственный минус, в отличии от perfbook, здесь нет ответов, чтобы проверить себя (остается, либо доказывать, либо гуглить, если не уверен).

2. https://ciir.cs.umass.edu/irbook
По сути тоже самое, но якобы более практическое (из прикольного к книжке есть жаба код учебного поискового движка http://www.search-engines-book.com), по факту мне показалась более поверхностной и менее интересной.

Вообще на работе сейчас занимаюсь ускорением geo поиска, так как он работает у нас на s2, у меня периодически горит с них жопа.
Например, сделал оптимизацию для случая, когда кверить будут только точки и заодно улучшил интерфейс, чтобы не нужно было делать аллокацию на каждый вызов, PR до сих пор висит https://github.com/google/s2geometry/pull/303, потому что гугловый чел не оценил моего расширения интерфейса. Надеюсь его не сократят, а то не знаю сколько ещё ждать ответа.

В целом мне кажется историю, которая у нас сейчас: храним термы для кверинга в инвертед индексе, а потом вычисляем точную операцию, можно делать принципиально лучше, проблема в том что s2 почти не развивается, а нужно, чтобы их индекс умел в выдачу конкретных фигур в intersects/contains не только для поиска точек, но и полилиний и полигонов, вроде как они планируют это сделать, но когда — хрен его знает :(

Вообще как бы вы решали задачу k-way merge (есть k отсортированных input, нужно получить 1 отсортированный output)?

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

Но с практической можно делать меньшее (в константу раз) число сравнений.
Вчера я вспомнил, что хотел померить это в arangosearch.

Ну и в общем в чем же идея?
Давайте сначала вспомним, что будет происходить в случае кучи:
Каждый раз доставая элемент нужно сделать sift down обновленной вершины:
Это в свою очередь спуск вниз на глубину log(k), к сожалению на каждом спуске нам ещё нужно проверять спускаться в левое или в правое под дерево, то есть в итоге мы получим не больше 2 * log(k)
(в плюсах и многих других языках из коробки ещё хуже, так как decrease key отсутствует, нужно сделать pop + push, что уже до 3 логарифмов, +1 потому что push это sift up, который требует не более логарифма сравнений)

Почему такое вообще происходит?
Потому что с точки зрения дерева минимумов оно у нас встроенное в сами данные, и поддерживать такую структуру немного сложнее.

Поэтому вместо этого можно поддержать дерево явно, по сути сделав дерево отрезков минимумов, такой подход называют tournament tree, и он даст ровно log сравнений

Cегодня я набросал код и вероятно завтра напишу микробенчмарки, потом еще посмотрю на перф в аранге:
https://github.com/iresearch-toolkit/iresearch/pull/476

В целом весьма очевидно что мы выигрываем, есть ли минусы? В сравнение с pop + push подходом нет, в сравнении с sift_down к сожалению да.

Главная проблема что в случае дерева нам нужно поднимать новое значение снизу, то есть логарифм сравнений мы делаем всегда.
В случае же с кучей мы опускаем значение среди других значений и если нам повезло и input-ы не пересекаются мы на каждый push в output будем делать только 2 сравнения (кроме тех где input закончился).

Резюмируя для [0;4-8] инпутов tournament tree однозначно лучший подход, относительно числа сравнений.

А дальше это зависит от данных. Если данные рандомные то все еще лучший. А вот если по какой-то причине у вас очень мало переключений инпутов или вообще disjoint диапазоны, то вероятно ручной sift down покажет себя оптимальнее :(

Можно ли что-то с этим сделать?
Наверно нет, только страдать, впрочем еще мне нравится подход с деревом тем, что это всегда фиксированное число сравнений, их число не зависит от того как именно output данные расположены в input-ах

Не конструктивный пост, для меня C++ лучший выбор для разработки чем Rust, да у него есть очевидные преимущества над C++, впрочем верно и обратное.

Сейчас я не буду перечислять все, а расскажу об одном из наиболее важных для меня недостатков, который декларируется как преимущество, это cargo и система пакетов.
В вакууме она безусловно лучше того, что предоставляет C++ (кривые поделия, отсутствие стандарта => большинство зависимостей собирается из сорцов).

К сожалению на практике это приводит к неприятной мне экосистеме, где даже у простейших библиотек кучи зависимостей, и к тому что код библиотеки/проекта сложнее "просмотреть".

Качество кода и глубина зависимостей становятся куда менее однородными, чем при подходе сборки из сорцов.
Есть статья которая в целом отражает мое отношение к зависимостям:
https://research.swtch.com/deps

Безусловно я не считаю что все нужно писать с нуля, буквально первое, что я делаю с идеей, это ищу код который её реализует.
К сожалению часто даже найдя такой код, использовать его не является разумным.
В случае же с пакетными менеджерами, люди редко смотрят на что-то кроме наличие нужного API и количества установок.

Впрочем в си на мой взгляд есть противоположная проблема, когда библиотеки практически не используются (кроме domain specific: сжатие, криптография, етс), а в стандартной библиотеке отсутствуют контейнеры, как следствие все реализуется по 10 раз, а дефолтная структура данных для си это список (из-за своей простоты).

Резюмируя, у каждого из подходов есть свои недостатки, но контролировать, что в твоём проекте нет лишних велосипедов, сильно легче на мой взгляд, чем контролировать что все зависимости не зависят от чего то зря (да и что делать в таком случае не очень ясно).

Прочитал интересный пост на ночь: https://eklitzke.org/efficient-file-copying-on-linux
TLDR: если читаете файл на линухе, есть вероятность что стоит делать это блоками по 128 Кб, так как readahead настроен обычно на такое число

В общем недавно появилось время и я доделал дерево вместо кучи,
померял и даже на простом компараторе получил ускорение на 15%.

Ещё недавно пофиксил оптимизировал довольно забавный кейс:
Дана сортированная по возрастанию последовательность уникальных чисел.
Затем по ней много ищут.
Есть две особенности:
1. В последовательности множество dense подотрезков, как правило с длиной больше 1.
2. Если все искомые числа выписать в одну последовательность, то это будет последовательность сортированных подотрезков, как правило с длиной больше 1.

Понятно что baseline здесь это обычный бинпоиск.
Но мы могли бы сохранить найденную позицию в массив.
Тогда при следующем поиске, нужно вычислить разницу между значением, которое было на этой позиции и искомым числом.
После прибавить эту разницу к прошлой позиции.
Затем проверить, что мы не вышли за пределы массива и это действительно искомый элемент.
В случае если между текущим искомым числом и прошлым был dense диапазон, мы нашли новое число.
А если не получилось все ещё можно использовать обычный бинпоиск.

Я не особо усердно бенчмаркал, так как это очевидно лучше, но даже на достаточно маленьких массивах (1e5) вышло в 2-4 раза быстрее.