Такой вопрос.

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

Далее. Даже то, что не реализовано — описано по шагам в спец. литературе. Т.е. реализация состоит в том, чтобы повторить эти шаги. А еще проще — взять уже готовое на другом ЯП и просто перевести.

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

Здравствуйте, Shmj, Вы писали:

S>Так вот, в чем вопрос. Все-же встречаются некие уникальные алгоритмы, которые не описаны и не реализованы. Часто ли встречается в вашей практике? Могли бы привести примеры что из наиболее сложного вам пришлось делать с нуля?

Тут даже не алгоритмы, а подход. Упаковка дерева классов из БД со связями объектов многие ко многим с возможной циклической связью таким образом, чтобы всё хранилось одним куском в памяти (не требовало сериализации/десериализации при передаче по сети).

Здравствуйте, Shmj, Вы писали:

S>Так вот, в чем вопрос. Все-же встречаются некие уникальные алгоритмы, которые не описаны и не реализованы. Часто ли встречается в вашей практике? Могли бы привести примеры что из наиболее сложного вам пришлось делать с нуля?

Занимался 10 лет назад сжатием изображений. Идея была в том, что в отличие от звука, преобразовние Фурье/вейвлетов для графики не подходит.
Придумал два алгоритма: один очень простой и быстрый, без Фурье, по эффективности как jpeg.
Другой посложнее, по эффективности получился как jpeg2000, без Фурье, но медленный. Потом узнал, что идея известна и называется context-adaptive image coding, но в стандартах не прижилась.
Потом работал еще какое-то время с сжатием видео в Samsung. Но к теме интереса больше нет, и с тех не занимался этим.

Здравствуйте, lpd, Вы писали:

lpd>Идея была в том, что в отличие от звука, преобразовние Фурье/вейвлетов для графики не подходит.
lpd>...

В каком смысле не подходит. DCT это тот же Фурье только вид сбоку, а вейвлет в jpeg2000 используется. Можешь раскрыть мысль ?

Здравствуйте, Videoman, Вы писали:

V>Здравствуйте, lpd, Вы писали:

lpd>>Идея была в том, что в отличие от звука, преобразовние Фурье/вейвлетов для графики не подходит.

V>В каком смысле не подходит. DCT это тот же Фурье только вид сбоку, а вейвлет в jpeg2000 используется. Можешь раскрыть мысль ?

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

Здравствуйте, Shmj, Вы писали:

S>Могли бы привести примеры что из наиболее сложного вам пришлось делать с нуля?

1. Система для аукционов. Одновременно запускается множество аукционов, в которых участвуют люди. Аукционы бывают на повышение/понижение, ну в общем там определённая бизнес-логика прописана. При этом это не какая-то игра была, а реальные торги на лоты по миллионам рублей. Всё должно работать быстро, и, конечно, корректно. В случае чего и засудить могут. Ядро этой системы, где вся логика была, пожалуй была самым аккуратным, протестированным и продуманным кодом в моей жизни, тестировал я её вдоль и поперёк, даже ботов писал для тестирования.

2. http://rsdn.org/forum/java/7043726.flat#7043726

Автор: C0s
Дата: 04.02.18

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

Здравствуйте, Shmj, Вы писали:

S>Большинство базовых алгоритмов все-таки уже реализовано для любого ЯП и руки марать нет смысла. Причем реализованы они многократно — для любого ЯП вы найдете тысячи вариаций, к примеру, B-Tree, хотя большинство реализаций с ошибками. Это как про много веселых ребят, которые делают велосипед (чисто по приколу или просто потому что могут).

S>Далее. Даже то, что не реализовано — описано по шагам в спец. литературе. Т.е. реализация состоит в том, чтобы повторить эти шаги. А еще проще — взять уже готовое на другом ЯП и просто перевести.

S>Так вот, в чем вопрос. Все-же встречаются некие уникальные алгоритмы, которые не описаны и не реализованы. Часто ли встречается в вашей практике? Могли бы привести примеры что из наиболее сложного вам пришлось делать с нуля?

У меня было несколько случаев, когда я сначала реализовывал сложные алгоритмы, а потом их сильно упрощал.
В 90-х делал физический движок, который в рилтайме должен был считать гравитационные и магнитные взаимодействия. Много сил убил на реализацию двухмерного движка. А потом осенило — оси же ортогональны, и можно реализовать все алгоритмы в виде единого простого алгоритма для одной единственной оси в одномерном пространстве. А в целевом игровом мире просто сделать нужное кол-во ортогональных осей в виде объектов, и формировать финальный вектор обычным суммированием рассчитанных этим простым алгоритмом компонентов вектора. Демка показала, что концепция работает правильно. Ну и еще по ходу реализаци движка пришлось переизобрести хэш-таблицы.
В другой программе, тоже из начала 2000-х, переизобрел хэш-таблицы с бакетами, сохраняемыми на диск, для того, т.к. объемы данных не влезали в ОЗУ.
А про сами хэштаблицы как один из способов оптимизации узнал лет через 5. Но когда стал заниматься программированием профессионально, наоборот, стараюсь избегать сложности и самопальных алгоритмов, стараюсь все делать стандартными средствами и подходами и максимально просто.

Здравствуйте, Shmj, Вы писали:

S>Так вот, в чем вопрос. Все-же встречаются некие уникальные алгоритмы, которые не описаны и не реализованы. Часто ли встречается в вашей практике? Могли бы привести примеры что из наиболее сложного вам пришлось делать с нуля?

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

У меня из интересного было восстановление электрической схемы из геометрических данных (Gerber, ODB++), построение сечений (cross-sections) линий передач (transmission lines) на печатной плате.
Построение линий передач на плате довелось реализовывать аж трижды в двух разных компаниях
Построение прямоугольной адаптивной сетки (adaptive cartesian mesh) для 3D solver'а.
И прочего по мелочи.

Здравствуйте, Shmj, Вы писали:

Оптимальное сшивание 3D поверхностей на основе набора граничных условий на базе генетического алгоритма. Ну, понятно, что генетический алгоритм не я придумал, но использовать его в конкретной задаче не так тривиально. Самое прикольное было наблюдать за "эволюцией" в рантайме — как поверхности ползли друг к другу пристыковывались, смещали вершины, жили и умирали чтоб выжил только самый подходящий вариант.

Здравствуйте, Homunculus, Вы писали:

H>Оптимальное сшивание 3D поверхностей на основе набора граничных условий на базе генетического алгоритма. Ну, понятно, что генетический алгоритм не я придумал, но использовать его в конкретной задаче не так тривиально. Самое прикольное было наблюдать за "эволюцией" в рантайме — как поверхности ползли друг к другу пристыковывались, смещали вершины, жили и умирали чтоб выжил только самый подходящий вариант.

А почему именно генетический алгоритм? Если есть критерии выбора оптимального варианта, то почему сразу не делать "как надо"?

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>А почему именно генетический алгоритм? Если есть критерии выбора оптимального варианта, то почему сразу не делать "как надо"?

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

Здравствуйте, Shmj, Вы писали:

S>Так вот, в чем вопрос. Все-же встречаются некие уникальные алгоритмы, которые не описаны и не реализованы. Часто ли встречается в вашей практике? Могли бы привести примеры что из наиболее сложного вам пришлось делать с нуля?

Не совсем с нуля, но...
Балансировка цепей синхронизации для микросхемы.

Здравствуйте, lpd, Вы писали:

lpd>Мысль в том, что звук состоит и воспринимается органами слуха как волны, поэтому dct с квантованием коэффициентов и используется.
lpd>А вот для изображения разложение на волны не должно подходить, т.к. глаз его так не воспринимает.
lpd>Но по факту для сжатия типичных изображений с градиентами dct/фурье таки канает, хотя и не необоходимо.

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

SVZ>А почему именно генетический алгоритм? Если есть критерии выбора оптимального варианта, то почему сразу не делать "как надо"?
А как надо?
Генетический, муравьиный, отжига, вариации монтекарлы и подобные применяются для поиска глобального минимума, когда предполагается наличие многих локальных у функции.
Если у функции только один минимум и глобальный, то градиентные обычно.
Иногда еще используются те, которые не требуют вычисления градиента.

Здравствуйте, Vzhyk2, Вы писали:

SVZ>>А почему именно генетический алгоритм? Если есть критерии выбора оптимального варианта, то почему сразу не делать "как надо"?
V>А как надо?
V>Генетический, муравьиный, отжига, вариации монтекарлы и подобные применяются для поиска глобального минимума, когда предполагается наличие многих локальных у функции.
V>Если у функции только один минимум и глобальный, то градиентные обычно.
V>Иногда еще используются те, которые не требуют вычисления градиента.

Ну я ожидал какой-нить метод отжига. Либо эвристику. Потому что просто случайный поиск (ака генетический) это как-то совсем не быстро.

Здравствуйте, Maniacal, Вы писали:

M>Тут даже не алгоритмы, а подход. Упаковка дерева классов из БД со связями объектов многие ко многим с возможной циклической связью таким образом, чтобы всё хранилось одним куском в памяти (не требовало сериализации/десериализации при передаче по сети).

Делал примерно то же, но не для передачи по сети, а для поиска в этом двоичном дереве. Использовал memory-mapped files. Дерево хранил как есть, с указателями (смещения от базы в файле)

Здравствуйте, Shmj, Вы писали:

S>Такой вопрос.
S>Большинство базовых алгоритмов все-таки уже реализовано ... Могли бы привести примеры что из наиболее сложного вам пришлось делать с нуля?


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


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


А теперь я уже в совершенно другой области что-то пытаюсь придумать...

Здравствуйте, lpd, Вы писали:

lpd>Занимался 10 лет назад сжатием изображений

Расскажи пожалуйста. А вот в методах сжатия видео, есть ли какой теоретический предел. Порог, что не позволяет сжимать видео лучше него?

-- арифметическое сжатие — определяется если поток данных уменьшается не 16 бит а во что-то меньшее или снизу или сверху — переупаковывается в меньшее количество байт

-- сжатие плиток в карте и также алгоритм сжатия временных данных концентраций многокомпонентных газов в трехмерном пространстве

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

Здравствуйте, Shmj, Вы писали:

S> Могли бы привести примеры что из наиболее сложного вам пришлось делать с нуля?

пузырьковая сортировка

Здравствуйте, Shmj, Вы писали:

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

— Эффективный способ реализации межпоточной очереди через 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 и сверх-легковесное. Аналогичного кач-ва решения, насколько я знаю, в природе не существует. Известные сложные асинхронные системы достаточно долго стартуют и долго откатываются к начальному состоянию в случае ошибок в дочерних подсистемах (часто вовсе по банальному таймауту). Выглядит так, что программы пишут исключительно для успешной ветки, а неуспешные ветки обыгрываются по остаточному принципу и лишь потребляют терпение клиентов, когда "что-то пошло не так..." (С)

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