Я придумал новую структуру данных. А дальше что?  Публичный пост

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

Отличается чуть более быстрым перформансом - в сравнении с обычными роутерами поверх Trie эффективнее на ~O(log(log(n))), ну и плюс - сам код становится оптимальнее с точки зрения количества операций. Погонял сравнение с другими решениями на JS - работает раза в два быстрее чем самые быстрые альтернативы (ценой небольших трейдоффов). Публикации про такое решение искал, не нашел - но допускаю, что плохо искал.
В опенсорс выкину через месяц где-то, наверное, упаковываю в пригодное к проду решение.

А теперь вопрос - дальше-то что с этим делать?

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

Мне греет душу сама идея того, что я что-то новое изобрел, но, кажется, стоит с этим явно что-то еще сделать, кроме "просто радоваться".

14 комментариев 👇
Egor Biriukov, Engware Softineer 29 июня 2020

Непопулярное мнение: пейперы, цитирования и прочий академ морально устрарел и не нужен. Это все power games закрытых систем, есть тысяча и один пример как там все внутри покоррапчено и ангажированно.

Я бы на твоем месте запаблишил в опенсорс на паре языков имплементацию с красивым DESIGN.md файлом и покидал ссылки на HN/Reddit.

  Развернуть 1 комментарий
Захар Кириллов, Амбассадор ЕРАМ в Клубе 29 июня 2020

Пейпер и публиковаться имеет смысл только если вы аспират/постдок/студент MSc||PhD. В остальных случаях — напрасная трата времени и сил. Порог входа для человека вне академического мира достаточно высокий, а профита нет.

Начните просто со статьей в блогах и онлайн-медиа. Как оно раскочегарится и обрастёт фидбеками, подавайтесь на интересные вам прикладные конфы. Поскольку это будет скорее всего конфа в 2021 году, то она вполне может оказаться оффлайновой и глядишь вам оплатят перелёт-жильё — хоть какая-то выгода.

Ещё можно как-то аффилировать с работодателем и получить может какой бонус, если изобретение сделано в рабочее время и решает насущные рабочие проблемы.

  Развернуть 1 комментарий

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

С работодателем - аффилировать не выйдет (только-только работу сменил), да и код я руками уже не пишу, основным рабочим инструментом аутлук стал :)

Вопрос исключительно в том, что вот есть конкретное изобретение. Да, небольшое, но все же двигающее человечество вперед, пусть и на жалкий миллиметр. Что с ним делать - ХЗ. Писать посты в блог и прочее - это, конечно, прикольно, но ощущение, что все-таки масштаб слегка не тот, надо брать выше и делать что-то "на века", на чем другие работы основываться будут.

  Развернуть 1 комментарий

@jabher, пофантазирую, что можно ещё:

а) написать авторам популярных книг (кхм-кхм, из тех кто ещё живой) или курсов на всяких курсерах и набиться к ним в соавторы — пусть расширяют свои курсы вашим изобретением и двигают его в массы;

б) пойти в юзергруппы кор разработчиков продуктов или спецификаций, референс-реализации которых основаны на префиксных деревьях. Я не большой знаток области их пректического применения, но наверняка это либо Яндекс какой с их поиском, либо ДжетБрейнз с их компиляторами, либо может какой там Эластиксёрч с индексами (пардоньте, если я ерунду сморозил относительно применения), либо что-то опенсорсное что вам небезразлично и что выиграет от прироста производительности. Поможете улучшить их продукт, возможно, заработав какие-то очки в карму и заложив ещё одтин кирпичек в простихосподи "личный бренд".

в) всё-таки имея стартовую точку на гитхабе можно дополнить статью в википедии и снова сеять полезное-доброе-вечное на весь мир.

  Развернуть 1 комментарий

Круто! Было бы интересно узнать подробности. Выкладывай куда-нибудь принцип работы и исходники, если не жалко :)

Про whitepaper - не соглашусь, что он не нужен.

Реальные пацаны, такие как Tony Hoare, Edsger W. Dijkstra не просто изобретают алгоритмы и структуры, но и доказывают почему оно работает, а также описывают при каких условиях работает, при каких вырождается, применимость и т.п.
Тот же Quicksort имеет асимптотическую сложность O(n log n) on average, а в worst case сценарии его сложность - O(n^2), что, впрочем, редко бывает на практике.

Я хочу сказать, что работа несомненно заслуживает внимания, но одних эмпирических данных недостаточно, как минимум мне :)

Я бы на твоём месте напрямую написал кому-то известному из мира компьютерных наук. Мылом или в твиттере. Да хоть тому же Роберту Седжвику или Тиму Рафгардену. Я думаю, они даже будут рады пообщаться на эту тему.

  Развернуть 1 комментарий

Не знаю как надо, но я бы пользовался доступными мне инструментами.

  1. Опубликовал репозиторий с описанием и примерами в open source.
  2. Для более любопытных составил статью, как именно и почему это работает — с картинками и описанием всего-всего. Желательно на двух языках. Можно, например, на GitHub Pages.
  3. Рассказал везде, где есть я. Тут, в Твиттере, на Reddit, друзьям «в теме».
  4. Подготовил доклад на несколько ближайших тематических конференций.
  5. Запилил проект, который использует мое решение. Так можно сравнивать его с альтернативами и говорить «Вот, моя тулза быстрее/лучше, потому что внутри применяется такое решение».
  Развернуть 1 комментарий
Arseny Smirnov, C/C++, блокчейн, базы данных 29 июня 2020

А можно немного деталей? Интересно же! Хотя бы чуть более конкретное описание задачи?

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

  Развернуть 1 комментарий

Да, конечно. На самом деле супер-тупое решение, я удивлен как до сих пор не додумались.

На примере объясню: есть ряд путей, типа
/foo/:id
/:username/bar/baz

и сейчас любой префиксный роутер тупо строит дерево из частей (foo, *, bar), и логика поиска пути типа /foo/bar/baz выглядит так:

  • ага, есть /foo, идем дальше
  • ага, еще один чанк есть, идем дальше
  • а, нет, последнего чанка нет, отходим назад
  • ага, есть wildcard :username, пошли по этому пути

а по факту можно собрать "оптимизированное" префиксное дерево из трех урлов:

  • /foo/:id
  • /foo/bar/baz
  • /:username/bar/baz

и в таком случае сложность поиска из log(n) на доступ к произвольному узлу + log(log(n)) на "отход назад" в случае miss превращаются в просто log(n), плюс пропадает кусок кода, связанный с логикой отхода, задача из хитрого tree traversal превращается в обычную задачу поиска, там даже структура для хранения данных упрощается.

В принципе можно такую логику реализовать для любого уровня навороченности, хоть полновесные lookahead-only регулярки, но пока что я сделал только для /-separated строк, как proof of concept.

  Развернуть 1 комментарий

@jabher, прикольно! А как вы к этому пришли?

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

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

Лобовой подход это с backtracking - если зашли в тупик, то возращаемся к последней "развилке" и выбираем другое ребро.

Но можно преобразовать недетерминированный автомат в
детерминированный. Пройдя из вершины по символу мы потенциально можем оказаться в нескольких разных вершинах. Набор этих вершин и будет вершиной нашего нового автомата. Т.е. переход по символу будет из одного подмножества вершин первого автомата, в другое подмножество вершин первого автомата.

Минус - размер нового автомата может оказаться слишком большим. Есть разные способы с этим бороться. Например, забить и считать, что не окажется.

https://en.wikipedia.org/wiki/Powerset_construction
1959 год, кстати)

Если применить эту конструкцию к вашему примеру, получится в точности это "оптимизированное" дерево.

Из примеров библиотек которые используеют этот подход есть:
https://github.com/google/re2
https://github.com/yandex/pire
https://github.com/hanickadot/compile-time-regular-expressions

Не знаю, применял ли кто-то на практике этот подход именно к префиксному роутеру. Возможно, можно получить какое-то ускорение по сравнению с общим подходом через регулярки.

  Развернуть 1 комментарий

@arseny30, ну, мне было скучно, и мне на глаза попалось пафосное README "самого быстрого роутера на js", захотелось осадить человека :)

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

В целом да, выглядит так, как будто я сделал превращение недетерминированного автомата в детерминированный банально.

Я честно искал реализации на JS, Java, C/C++, не нашел. Возможно, есть на других языках, но я везде вижу решения "в лоб" только. Предполагаю, что причина в том, что это "экономия на спичках" и роутер - это 0.1% от всего времени жизни запроса, но мне искренне кажется, что если по всем фронтам пройтись и насобирать таких 0.1% оптимизаций в полусотне мест - прирост выйдет значительный, поэтому доковырять точно хочется.

  Развернуть 1 комментарий

Готов сделать/помочь с реализацией на .Net c# имплементацию алгоритма.
Контакты в профиле.

  Развернуть 1 комментарий

Спасибо! Напишу, как доведу до публикации референсную реализацию на JS - там как раз уже будет интеграция с express.js, будет понятно, как в деле себя ведет.

  Развернуть 1 комментарий
Artem Kelpe, Погроммист 24 августа 2020

Автор, расскажите, как успехи? Есть ли проект уже в открытом доступе? Хотелось бы глянуть

  Развернуть 1 комментарий

могу пока про прогресс рассказать:

есть затык на интеграцию с абсолютно любым фреймворком - koa, express, hapi, даже polka.

В чем проблема:

Любой фреймворк имеет дело с контекстом.
query-параметры живут в рамках этого контекста.

И если есть 2 url-маски вида /users/:id и /:page/foo, то на запрос /users/foo отработает два трансформера - один выдаст {id: foo}, а другой - {page: users}. В целом кейс редкий, но из-за опциональных параметров может стрелять.

А при использовании контекста или объекта req - данная сущность (query) должна перезаписываться. Причем именно перезаписываться, просто заменять атрибут нельзя, иначе параллельные middleware-и (допустим, логгер) не будут работать.

Вот сейчас сравниваю перформанс двух подходов. Первый - это использование new Proxy, который обертывает оригинальный ctx, и смотрю на скорость конструктора и доступа.

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

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

Ну и третий - нашел вот такую удивительную вещь https://github.com/uNetworking/uWebSockets.js, с которой даже fastify боится сравнивать себя. Подозреваю, что она порвет и мои наработки тоже, как тузик грелку.

  Развернуть 1 комментарий

😎

Автор поста открыл его для большого интернета, но комментирование и движухи доступны только участникам Клуба

Что вообще здесь происходит?


Войти  или  Вступить в Клуб