Я, отработав в компании МойОфис 9 лет и покинув её в январе, добавил бы важнейший, на мой взгляд, раздел в статью.
Мотивация - хорошо, однако прежде всего не должно быть мощных демотиваторов. В частности, высокопоставленный дурак или воинствующая некомпетентность, наделённая реальной властью - наверное, самый мощный демотиватор после прямого обмана сотрудников.
К чести компании замечу, что она не только не была за 9 лет замечена в "кидалове", но даже несколько шокировала меня выплатой заметного размера премии через несколько месяцев после моего ухода!
(здесь было много текста с упоминанием имён наиболее сильных демотиваторов, но решил не публиковать)
Искренне надеюсь, что автор статьи - достойный руководитель проекта. Хочется верить, что "всё было не зря".
В 1986 Полторак стал нам физико-химические основы неорганической химии, и в разделе "Термометрия" сказал дословно следующее:
Измерение температуры построено на двух предположениях, первое из которых произвольно, а второе заведомо ошибочно. Первое - выбор реперных точек. Второе - утверждение, что шкала между ними линейна.
В реальности размер ключа не фиксированный, но, казалось бы, для хэш-таблицы это влияет только на её физический размер, и ограничений там быть не должно.
Типичный размер словаря ключей немного поработавшей перимущественно русскояычной полнотекстовой машины - за миллион (~60,000 русской общей лексики из активного запаса, два по столько орфографических ошибок, формально годящихся в русские слова, остальное - числа и иероглифы вроде rs232).
Тут под соседей заметкой меня практически спросили, зачем нужен другой полнотекстовый поиск, если есть Apache Lucene. Не дословно, конечно, но это подразумевалось.
Да, вы совершенно правы: если нужна оценка размера некоторой массивной и кучерявой структуры данных, то GetBufLen проделывает весь путь Serialize, а время на её исполнение пропорционально времени Serialize с коэффициентом, равным отношению времени операции суммирования ко времени операции записи в конкретный коллектор.
С другой стороны, такая оценка нужна ровно в двух случаях: либо если вы собираетесь сделать дамп в памяти и хотите понять, сколько её надо резервировать, либо если вам надо строить внутренние таблицы релокации внутри такого дампа.
Эта была сделана в своё время для построения дампов словарных данных, по которым можно эффективно искать, не десериализуя.Где активно и используется (libmorph).
Так всё-таки к разработке каких известных полнотекстовых поисковых движков вы имели отношение? Или хотя бы к эксплуатации?
---
Пардон, заглянул - там Apache Lucerne, разработка двадцатилетней давности, довольно громоздкая и с низким качеством поиска (отношение правильно найденных к общему количеству найденных), на сегодня - прошлый век.
Видимо, проделана большая работа над тем, чтобы оно таки шевелилось.
1 и 2 справедливы для обоих подходов - и для упомянутой вами хэш-таблицы,и для сериализованного базисного дерева.
Однако у хэш-таблиц есть очевидный недостаток: построить по ней итератор, перебирающий ключи в порядке возрастания (убывания) сложно и дорого. А в прикладных задачах полнотекстового поиска этот итератор важен и нужен.
Хэш-таблица, демонстрирующая o(1), будет к тому же, вероятно, очень разреженной, а значит, "жирной" по размеру.
А про скорость поговорим в следующей заметке, добавим хэш-таблицу в сравнение производительности.
Нет. Это не так. Если передать по ссылке, то, например, для сериализации в память надо будет писать специальную обёртку, а не использовать простой char* - указатель, а вместо возврата nullptr в случае ошибки придётся бросаться exception'ами.
Для записи числа, которое можно представить 2 байтами (0 - 65535) нужен 1 байт, если число меньше 128, 2 байта, если число меньше 16384 и три байта в остальных случаях. В моих задачах это даёт экономию размера примерно 7%, а для uint32_t и того больше. Впрочем, писать таким способом или иным - вопрос выбора.
Сравнивать же с flatbuffers или с protobuf некорректно - это совсем разный функционал. Этот код, конечно же, быстрее, чем flatbuffers/protobuf, компактнее, если не использовать компрессию (zlib) и не имеет и половины того функционала, что есть в названных библиотеках.
Повторюсь, это инструмент сериализации данных в виде, позволяющем работать с ними без явной десериализации, то есть гарантировать, например, отсутствие операций резервирования памяти при эксплуатации такого словаря.
В следующей статье я покажу работу сериализованного базисного дерева, небольшое (~10%) замедление при работе по сравнению с его развёрнутой формой при снижении требований к памяти более чем на порядок.
Видимо, таки давно: пят лет назад либерда торчала от инфы, что у 70% нет заграна.
На картинке некий усталый скуф.
Индеец (Олег, прости, но тебя так многие зовут за глаза) не такой - он бегает, по горам ходит, и подтянутый.
Вообще говоря, до сих пор не была случая отвала "нужного куска Интернет".
Хотя сама сеть, да, иногда падает.
Ну, как бы, уж насколько ранжирование слабое у Elastic, но здесь даже обратная частота термина (его избирательность) не будет учитываться!
Я, отработав в компании МойОфис 9 лет и покинув её в январе, добавил бы важнейший, на мой взгляд, раздел в статью.
Мотивация - хорошо, однако прежде всего не должно быть мощных демотиваторов. В частности, высокопоставленный дурак или воинствующая некомпетентность, наделённая реальной властью - наверное, самый мощный демотиватор после прямого обмана сотрудников.
К чести компании замечу, что она не только не была за 9 лет замечена в "кидалове", но даже несколько шокировала меня выплатой заметного размера премии через несколько месяцев после моего ухода!
(здесь было много текста с упоминанием имён наиболее сильных демотиваторов, но решил не публиковать)
Искренне надеюсь, что автор статьи - достойный руководитель проекта. Хочется верить, что "всё было не зря".
В 1986 Полторак стал нам физико-химические основы неорганической химии, и в разделе "Термометрия" сказал дословно следующее:
Измерение температуры построено на двух предположениях, первое из которых произвольно, а второе заведомо ошибочно. Первое - выбор реперных точек. Второе - утверждение, что шкала между ними линейна.
Да, разумно.
В реальности размер ключа не фиксированный, но, казалось бы, для хэш-таблицы это влияет только на её физический размер, и ограничений там быть не должно.
Типичный размер словаря ключей немного поработавшей перимущественно русскояычной полнотекстовой машины - за миллион (~60,000 русской общей лексики из активного запаса, два по столько орфографических ошибок, формально годящихся в русские слова, остальное - числа и иероглифы вроде rs232).
Да ладно...
Тут под соседей заметкой меня практически спросили, зачем нужен другой полнотекстовый поиск, если есть Apache Lucene. Не дословно, конечно, но это подразумевалось.
Да, вы совершенно правы: если нужна оценка размера некоторой массивной и кучерявой структуры данных, то GetBufLen проделывает весь путь Serialize, а время на её исполнение пропорционально времени Serialize с коэффициентом, равным отношению времени операции суммирования ко времени операции записи в конкретный коллектор.
С другой стороны, такая оценка нужна ровно в двух случаях: либо если вы собираетесь сделать дамп в памяти и хотите понять, сколько её надо резервировать, либо если вам надо строить внутренние таблицы релокации внутри такого дампа.
Размер ключа у полнотекстовой поисковой машины невелик: от 3-4 до 20-25 байт. В зависимости от того, словарная это лексема или неизвестная.
А как вы хотите на hash-таблице сделать итератор по ключам? Например, для реализации поиска с усечением - сло*?
Выложил для того, чтобы было на что ссылаться при выкладке библиотеки полнотекстового поиска.
Эта была сделана в своё время для построения дампов словарных данных, по которым можно эффективно искать, не десериализуя.Где активно и используется (libmorph).
Непременно прочту.
Так всё-таки к разработке каких известных полнотекстовых поисковых движков вы имели отношение? Или хотя бы к эксплуатации?
---
Пардон, заглянул - там Apache Lucerne, разработка двадцатилетней давности, довольно громоздкая и с низким качеством поиска (отношение правильно найденных к общему количеству найденных), на сегодня - прошлый век.
Видимо, проделана большая работа над тем, чтобы оно таки шевелилось.
Терешке, думаю, тяжело пришлось обосновывать TCO.
Ну так какой из больших или хотя бы малых полнотекстовых движков вы сделали? Или хотя бы поучаствовали, хотя бы в качестве сеньора?
Из больших - Апорт!, Рамблер от 2000 года и дальше, украинскую Мету.
Эти три спроектировал, в значительной мере написал, последние два потом развивал и эксплуатировал.
И несколько поменьше.
А вы?
"Любимые БД" сильно просаживает производительность поисковых движков.
Требуют много памяти и медленно работают.
А я веду именно туда.
1 и 2 справедливы для обоих подходов - и для упомянутой вами хэш-таблицы,и для сериализованного базисного дерева.
Однако у хэш-таблиц есть очевидный недостаток: построить по ней итератор, перебирающий ключи в порядке возрастания (убывания) сложно и дорого. А в прикладных задачах полнотекстового поиска этот итератор важен и нужен.
Хэш-таблица, демонстрирующая o(1), будет к тому же, вероятно, очень разреженной, а значит, "жирной" по размеру.
А про скорость поговорим в следующей заметке, добавим хэш-таблицу в сравнение производительности.
Нет. Это не так. Если передать по ссылке, то, например, для сериализации в память надо будет писать специальную обёртку, а не использовать простой char* - указатель, а вместо возврата nullptr в случае ошибки придётся бросаться exception'ами.
В данном случае замечание про владение очень не к месту.
Требовать здесь unique_ или shared_ptr - это примерно как возвращать из vector<>::data() или string::c_str() вместо указателя - std::*_ptr(), право!
::Serialize никоим образом и ни в один момент времени не является владельцем объекта по указателю.
А что не так с "сырыми" указателями?
Для записи числа, которое можно представить 2 байтами (0 - 65535) нужен 1 байт, если число меньше 128, 2 байта, если число меньше 16384 и три байта в остальных случаях. В моих задачах это даёт экономию размера примерно 7%, а для uint32_t и того больше. Впрочем, писать таким способом или иным - вопрос выбора.
Изначально это делалось для словарей, так что данные, созданные на одной платформе, должны верно читаться и на обратном порядке следования байт (см. словари libmorph). Порции для записи берутся арифметическими операциями (см. код https://github.com/big-keva/mtc/blob/557336ee9bfe935c4a7afe31a2a06ee8fa9ab189/serialize.h#L227).
Сравнивать же с flatbuffers или с protobuf некорректно - это совсем разный функционал. Этот код, конечно же, быстрее, чем flatbuffers/protobuf, компактнее, если не использовать компрессию (zlib) и не имеет и половины того функционала, что есть в названных библиотеках.
Повторюсь, это инструмент сериализации данных в виде, позволяющем работать с ними без явной десериализации, то есть гарантировать, например, отсутствие операций резервирования памяти при эксплуатации такого словаря.
В следующей статье я покажу работу сериализованного базисного дерева, небольшое (~10%) замедление при работе по сравнению с его развёрнутой формой при снижении требований к памяти более чем на порядок.