— Алгоритм поиска одной из базовых станций в случае, когда несколько базовых станций работают на одном радио-канале и потенциально мешают друг другу. Достаточно было подобрать вид распределения плотности вероятности провоцируемых столкновений во временной области.
— Эффективный способ реализации межпоточной очереди через lock-free, с гарантией отсутствия проблемы ABBA. Спустя несколько лет увидел идентичную реализацию во внутренностях новой на тот момент MS PPL. В двух словах — любые альтернативные виденные варианты lock-free очередей в разы менее эффективны. Например, джавовский LMAX Disruptor — вовсе детсад.
— Способ повышения эффективности межпоточной сигнализации при увеличении нагрузки вплоть до полного исключения дёргания примитивов сигализации уровня ОС, т.е. исключение достаточно дорогих операций. Пропускная способность в режиме пиковых нагрузок возросла примерно в 20 раз от классических вариантов, сведя стресс-режимы работы системы к штатным.
— Пул объектов, умеющий быстро наращивать свою ёмкость и постепенно отдающий память системе при снижении нагрузки.
— Деджиттер для UDP-пакетов с двумя контурами АУ. Собсно, многоконтурное управление — классика из мира электроники (двухконтурное так вовсе применяется "практически везде", это выделение постоянной составляющей с большим Тау, и целевая работа с небольшим Тау в частотной области целевого сигнала уже за вычетом постоянной составляющей), оно хорошо легло на относительную стабильность среднего пинга в установленном и "разогретом" соединении хоть на другой конец шарика при более "быстром" плавании этого пинга вокруг среднего. Однако, такая примитивщина явилась откровением для мира VoIP. Виденные до этого одноконтурные деджиттеры с наколенными нелинейными эвристиками выдавали лишь невладение авторами азами АСУ. ))
— Дешевый способ дешифратора тонального сигнала телефонов (при наборе номера или расшифровке сигналов АОН, еще в проводную эпоху), алгоритм использует только сложение-вычитание входных отчётов сигнала, идеально подходит для микроконтролеров без умножителей. Является переработанным/вырожденным вариантом БПФ по заданной сетке частот, вместо регулярной. Объяснял суть способа adontz когда-то давно, у него с полутыка всё получилось с точностью распознавания и отношением сигнал-шум на порядки лучше требуемых. Алгоритм использует эффект сужения окна в частотной области при растягивании во временной. Так же позволяет намеренно расширить окно в частотной области для задания требуемых погрешностей (т.к. кварцы имеют погрешность, особенно на дешевой аппаратуре).
— Алгоритмы проектирования и реализации цифровых фильтров без промежуточного построения модели прототипа и последующего z-преобразования. Подходит для динамических "крутилок" фильтров, где сама крутилка, например, управляется некоей огибающей, получаемой прямо из сигнала. Всё работает в реалтайм, т.е. вычисление коэфициентов фильтра по классическому алгоритму выходит в разы дороже целевой фильтрации. Существуют альтернативные способы сохранения предвычесленных коэф. фильтров в таблице и затем вычисление их через квадратичную интерполяцию. Требует внушительных таблиц и всё еще заметных вычислений. И совсем не подходит при динамичесокм управлении в том числе характеристиками фильтра, например, добротностью, т.к. получается таблица в таблице. Реализованная идея сводит вспомогательные вычисления практически к 0-лю за счёт небольшой погрешности огибающей фильтра в частотной области. В целевой области применения такая погрешность была допустимой.
— Методы нелинейного преобразования спектра сигналов на основе вычисления степеней с показателем степени менее единицы от модуля амплитуды или логарифмов тоже от модуля, без вычисления логарифмов и дробных степеней. Реализовано через приближенные рекурсивные алгоритмы, где предыдущий отчет даёт первое приближение, в итоге рекурсивные алгоритмы сходятся быстро. Алгоритм растёт идеей от придуманного мною же алгоритма рисования окружности когда-то без вычислений корней квадратных на персоналках. Суть таких алгоритмов в том, что sqrt(2)*sqrt(2)==2, при задании достаточно хорошего приближения алгоритм сходится быстро, например, при рисовании круга он сходился за один шаг при точности в один пиксел, если брать исходным приближением координаты предыдущего вычисленного пиксела, т.е. итоговый алгоритм не содержал вложенного цикла. Плюс обходился цеочисленными вычислениями (через масштабирование на разрешение экрана). В итоге, программа на Бейсике рисовала окружности в несколько раз быстрее встроенной процедуры рисования окружности (которая была не на Бейсике, а на асме). И что забавно — рисовала окружности точнее. Похоже, внутренний алгоритм вычисления корня по ряду Тейлора или рекурсиный сходящийся были ограничены в кол-ве шагов, т.е. были недостаточно точны. Плюс, представление плавающего числа само по себе крадёт точность у мантиссы (от полной ширины бит представления, т.к. требуется хранить еще знак и экспоненту).
Оба предыдущих способа использовали передискретизацию сигнала вчетверо, упростив суммарные вычисления примерно на порядок, даже с учётом передискретизации. В системе происходила Фильтрация на требуемый диапазон, затем передискретизация, это гарантировало "плавность" изменения отсчётов, что требовалось для эффективной работы упомянутых решений.
— линия задержки с плавным регулированием задержки (т.е. с дробной задержкой относительно отсчётов). Решила проблему "роботизации" звука классических цифровых алгоритмов фленжеров/фейзеров/хорусов/реверберации, которая (проблема) проявляется при большом уровне обратной связи, и чего не происходит в реализациях на аналоговых регулируемых линиях задержки (например, в конструкциях на магнитных лентах). "Теплый ламповый звук" в цифре возможен! ))
— Способ склейки совпадающих участков цепочек нетерминалов у одновременно протягиваемых альтернативных состояний GLR-парсера, в итоге резко улучшает как требования к памяти, так и общую эффективность, особенно для "глубоких" по иерархии грамматики входных цепочек. Спустя несколько лет увидел аналогичные решения у других GLR парсеров, хотя не видел у более ранних их версий. Видать, идея была на поверхности — достаточно было развернуть направление связанного списка на обратное, чтобы шарить общие "хвосты". Похоже, первые реализации GLR-парсеров писались теми, кто Лиспа в руках не держал. ))
В сочетании с пулом объектов, куда попадают отвалившиеся в процессе разбора неудачные ветки, и откуда берутся узлы для протягиваемых всё еще успешных на данном шаге вариантов AST, на реальных данных получилась эффективность, практически не уступающая вылизанным RL(k) парсерам, при том что полный набор данных невозможно было разобрать LR(k) парсерами.
— Аналогичный трюк до этого использовал в автоматическом генераторе лексеров для расширенных регулярных выражений (это которые из иерархии Холмского, а не которые перловые), в итоге требуемая при работе память растёт примерно линейно от размера грамматики, в отличие от квадратичного роста потребляемой памяти в классических алгоритмах перевода НКА сразу в минимизированный ДКА.
— Сверху идея подборки оптимального перекодирования терминалов в таблице переходов исходя из частотной статистики реальных данных для парсера. Идея проста как 3 копейки — самые частовстречающиеся терминалы должны идти первыми строками таблицы переходов. Плюс перекодирование почти всегда кратно сжимает таблицу переходов. Плюс таблицу переходов стало возможно хранить не прямоугольной, а как набор столбцов разной высоты (в большинстве случае малой высоты), что еще снизило требования к памяти. Скорость работы лексера выросла примерно втрое.
— Lock-free реализация promise/future, аналогичных оным из стандартной библиотеки С++. Сверху реализованы предложения к АПИ, так и не вошедшие в стандарт (три вида continuations). В нагрузочном тестировании работают примерно в 20 раз эффективнее стандартных (стандартные защищают своё состояние мьютексом и условной переменной). Хотя, задача изначально встала не из-за эффективности, а из-за дедлока, который эти же реализации из Буста (еще до вхождения в стандарт) вызывали в сценариях, где подписка на события future происходила одновременно с проигрыванием уже имеющихся подписок. В итоге, та реализация из Буста, таки, пошла в стандарт, но подписку на события убрали.
— Идея и реализация динамически формируемых графов future. Исходный вид подписки в Бусте предполагал статическое формирование графов распространения сигналов в системе future-s, в то время как "в реальной жизни" (С) чаще требовалось динамическое формирование графов. Была выделенная общая особенность таких сценариев и достаточно простым движением руки реализована. Заодно было достигнуто абстрагирование сущности "задача" от сущности "группа задач". Например, все виденные фреймворки явно выделяли одиночную задачу от группы задач, что вносит заметные неудобства при использовании таких фреймворков. Дотнетный мега-абстрактный Task решает эту проблематику, а сценарий, в котором реализация от Буста впадает в дедлок, обыгрывает через копирование в куче очередей подписок continuations, плюс в этом месте многократно дёргаются примитивы синхронизации, в итоге дотнетный Task получился слишком неэффективным, "тяжеловесным" в работе. Куча флагов, куча ветвлений, куча синхронизаций на мьютексте. Стоимость обслуживания объекта Task часто превышает стоимость целевой работы, т.е. инфраструктура порой больше пашет на саму себя, чем на полезный выхлоп. Сверху пресловутое абстрагирование от execution или synchronization context, т.е. постелили соломки для "низкой планки входа", но в итоге сделали реализацию еще более неэффективной. Моё решение было перенесено из плюсов в дотнет со всей поддержкой async/await, благо такую поддержку можно накручивать поверх своих асинхронных примитивов.
— Проведены исследования и выполнена реализация простой, казалось бы, вещи — надёжного "транзакционного" запуска иерархически составных асинхронных систем и их надёжной остановки. Стоило копнуть и всё оказалось сложнее, чем звучит на словах. Были выделены сценарии, составляющие базис, этим базисом описываются произвольные сценарии, возможные в реальной жизни, т.е. произвольные сценарии получаются иерархической (в любую глубину) комбинацией базисов. Как обычно, всё на основе lock-free и сверх-легковесное. Аналогичного кач-ва решения, насколько я знаю, в природе не существует. Известные сложные асинхронные системы достаточно долго стартуют и долго откатываются к начальному состоянию в случае ошибок в дочерних подсистемах (часто вовсе по банальному таймауту). Выглядит так, что программы пишут исключительно для успешной ветки, а неуспешные ветки обыгрываются по остаточному принципу и лишь потребляют терпение клиентов, когда "что-то пошло не так..." (С)
Суть решения крылась в проанализированных и найденных обязательных маршрутах распространения сигналов успешности/неуспешности запуска компонент в произвольных по структуре подобных системах. Сверху найдены ограничения на моменты распространения сигналов, т.е. иногда сигналы задерживаются до достижения нужных условий. Все тонкости обыграны "под капотом", не требуют от прикладного программиста знаний о них.
