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

Большинство базовых алгоритмов все-таки уже реализовано для любого ЯП и руки марать нет смысла. Причем реализованы они многократно — для любого ЯП вы найдете тысячи вариаций, к примеру, 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> Могли бы привести примеры что из наиболее сложного вам пришлось делать с нуля?

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