LINUX.ORG.RU

Какие алгоритмы вы чаще всего используете?

 


3

2

Привет ЛОР!

Углубляюсь в тему алгоритмов.

Расскажите, какие алгоритмы вы чаще всего используете в вашей реальной работе (если используете)? Любые, с которыми вы сталкивались на практике, и из любого разряда: алгоритмы обработки данных, сетевые алгоритмы, поиска, алгоритмы для распределенных систем, etc.

На чем их реализуете?

Спасибо.

Ответ на: комментарий от emulek

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

однако «греческий» включает «римский» - особенно если есть отличный рубрикатор|индекс дьюи.

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

ну и те самые Начала от Евклида ага.

Кнут сам называл свой труд обзорным и сборником рецептов так что поддтроливай дальше

qulinxao ★★☆
()
Ответ на: комментарий от vertexua

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

а вообще да достаточно разбить на корзины для многократного ускорения - и не возится .

qulinxao ★★☆
()
Ответ на: комментарий от emulek

а к чему ты всё это написал?
ТС спрашивает какими алгоритмами мы пользуемся, я отвечаю
ну и как бы пых не мой

q11q11 ★★★★★
()
Ответ на: комментарий от Anon

Те алгоритмы — для приблизительной аппроксимации поверхностей по набору точек.

Внезапно - те алгоритмы для интерполяции (аппроксимации - откуда смотреть) по набору точек. Дальше с интерполируемой функцией можно делать что угодно, в т.ч. и интегрировать.

А у меня — векторное поле, и интегрировать надо очень точно.

У Вас векторное поле задано набором точек (известно в некоторых точках). Что бы его проинтегрировать, его надо сначала проинтерполировать (доопределить) между точками. Именно для это перечисленные алгоритмы и предназначены.

Строите по своему набору тетаэдическую сетку (Делоне) или сетку Вороного (ей дуальную). С тетраэдрической на самом деле работать проще. Интерполируете свое поле в ячейках как-то, и дальше интегрируете по ячейкам.

WTF вообще «интегрировать надо очень точно»? Чего, обычно трилинейной интерполяции (или ее аналогов) по ячейке не хватаить? Ну так возьмите уже бета-сплайны например. Брать что то более монструозное классики не рекомендовали, монотонность теряется и лезуть артефакты из всех щелей.

И что Вы понимаете под «интегрировать» кстати? Если просто интегрировать по объему, то скачки на границах ячейки картину почти не портят. Если под интегрированием Вы понимаете хитровыкрученный рейтрейсинг в таком поле, то все куда хуже...

Что за задача то?

AIv ★★★★★
()
Ответ на: комментарий от AIv

Под "интегрировать" я понимаю интегрировать. Интегрировать векторное поле по dxdy, чтобы из градиента получить первообразную функцию. Задача элементарная: восстановление волнового фронта по гартманнограмме.

Anon
()
Ответ на: комментарий от vertexua

вместо перебора всех пар точек в пространстве побил все на квадраты, посчитал хеши и засунул все точки в хешмапу в родной хеш и 9 соседних. После этого нашел все пары близлежащих.

Посчитал хеши чего?

9 соседних чего? Точек? А как определил соседние точки?

Результирующий алгоритм: 1 h vs 5 sec

С эффективностью понятно. Но что на счет корректности?

anonymous
()
Ответ на: комментарий от Anon

нормаль к каждому треугольнику

попытаться их все «состыковать».

Что-то у меня какие-то смутные ассоциации возникают с методом конечных элементов.

anonymous
()
Ответ на: комментарий от Anon

ну и зашибись! Тетраэдрическая сетка самое оно. Остальное решается выбором правильных базисных Функций в тетраэдрах

AIv ★★★★★
()

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

prischeyadro ★★★☆☆
()
Ответ на: комментарий от Anon

Даже и не знаю что сказать... вообще то оно на поверхности лежит. Про метод конечных элементов и какие нить RKDG/LDG (не говоря уж про сами тетраэдрические сетки) немерянные тыщщи тонн литературы понаписано.

AIv ★★★★★
()
Ответ на: комментарий от Anon

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

AIv ★★★★★
()
Ответ на: комментарий от AIv

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

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

Anon
()
Ответ на: комментарий от Anon

Построить на точках теугольную сетку, линейной интерполяцией восполнить его во всей области, --- после этого интегрировать (значения векторного поля будут определены во всех точках области). Как правильно и быстро интерировать на треугольной/тетраэрической сетке придумано в трассировке лучей (ray tracing tetrahedral mesh в гугл)

anonymous
()
Ответ на: комментарий от Anon

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

anonymous
()
Ответ на: комментарий от Anon

У Вас нет данных, чтобы сделать лучше, в принципе нет. Если как-то и получается (на рисунке) менее хреново --- то только в плане визуального восприятия, именно точность лучше не будет никогда. Только запутаетесь --- где у Вас ошиька вызвана данными, а где --- костылями для более красивой визуализации.

Городить что-то помимо линейной интерпояци имеет смысл только если у Вас есть дополнительная (качественная, не количественная) информаця о поле, которое Вы восполняете. Наприме, полиномиальная интерполяциия не сохраняет монотонность --- но можно сделать так, что монотонность будет сохранена. Ну или другие свойства.

anonymous
()
Ответ на: комментарий от anonymous

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

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

AIv ★★★★★
()

Все нужные алгоритмы очевидны, и давно уже есть в библиотеках, а ненужные алгоритмы не нужны. Программисту не надо ничего про алгоритмы знать.

anonymous
()
Ответ на: комментарий от anonymous

ненужные алгоритмы не нужны.

Чистая правда :)

Программисту не надо ничего про алгоритмы знать.

Ну, программист программисту рознь как бы

amidala
() автор топика

Я линейные люблю.

Deleted
()
Ответ на: комментарий от Anon

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

anonymous
()

Я использую алгоритм поиска в гугле в 90% случаев.

cdshines ★★★★★
()
Ответ на: комментарий от anonymous

Если данные отнесены узлам, то никаких разрывов при использовании кусочно-линейной интерполяции не будет.

anonymous
()
Ответ на: комментарий от Anon

Если этими методами не пользуются, то есть какие-то дополнительные причины --- и в этом треде Вы что-то не договариваете про постановку задачи.

В рамках Вашей постановки здеьс Вам все правильно рассказали как и что делать.

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

anonymous
()
Ответ на: комментарий от AIv

Хорошо быть молодым идеалистом.... погуглите LRnLA. Заявили громко, выигрыш коллосальный, кроме нас никто не пользуется.

Гугл выдал Ваш профиль на лоре. При небольших затратах на опробование - почему бы и нет, но с описанными год-полтора... Вот если бы гугл выдавал исходники для хотя бы одного примера реализации популярной задачи на LRnLA, чтобы можно было пощупать и убедиться, что правда (результаты должны выдаваться в таком формате, чтобы можно было сравнить с заведомо работающим решением). Увидев своими глазами преимущества, можно было бы трезво взвесить, стоит ли оно того времени для въезда.

Ещё можно оформить публикацию в другом ключе: не привычное «наш метод позволяет, ускорил,...», а взять показательный кусочек какой-нибудь реальной проблемы, над которой работают известные зарубежные институты. И показать, как быстро Вы её решили. Именно реальную проблему. Заинтересовать не столько средствами, сколько самой целью. Как только станет ясно, что Вы можете сделать именно то, над чем работают другие всемирно известные, быстрее - так они там зашевелятся. Ведь иначе, именно Ваш институт сможет заполучить следующие гранты, т.к. Вы сможете сделать больше за те же деньги.

gag ★★★★★
()
Ответ на: комментарий от gag

Все это сделано, плохо гуглите:) Посмотрите например cfmaxwell - как раз код на актуальную тему.

AIv ★★★★★
()

Вообще-то абсолютно любой код, даже самый тупой, реализует какой-то алгоритм. Даже любой рецепт из кулинарной книги это тоже алгоритм.

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.