LINUX.ORG.RU
ФорумTalks

Академические алгоритмы в современном программировании: не маразм ли?

 , , ,


3

2

У меня складывается стойкое ощущение, что использование классических супер-эффективных алгоритмов со всякими чудесными O(n) в современных реалиях, когда серверы со 128-ю процессорными ядрами стали скорее нормой, чем роскошью - в общем, это похоже на маразматическое ретроградство и заскорузлость мозга в принципиальном нежелании критически оценивать свои «бесценные» университетские знания, полученные от людей, не всегда догадывающихся о существовании многопоточности.

На мой взгляд, в современных реалиях наиболее эффективно себя показывают алгоритмы «разделяй и властвуй» наподобие QuickSort'а - т.е. те алгоритмы, которые позволяют разбить выполнение задачи на множество параллельно выполняющихся подзадач. А программистов, не задумывающихся о распараллеливании, синхронизации и склейке результатов - нужно гнать из профессии ссаными тряпками, сколько бы ни было у них гонора в связи с тем, что они всего Кнута выучили наизусть.

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

★★★★★

Последнее исправление: DRVTiny (всего исправлений: 1)

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

svr4> ...который годен только для параллельных числодробильных задач и код общего назначения выполняет хуже первопня.

И? Речь шла о том, что в распоряжении якобы нет средств выполнения кода с огромным количеством ядер.

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

dmxrand> Ну да все на словах Львы Толстые. А потом наблюдаем как создается 100 потоков каждый из которых обрабатывает 1 гиговый кусок и все дохнет. А казалось бы сохрани запросы и обработай их последовательно.

О том и речь - сначала «Ну и ладно. У меня 4 ядра. На компьютере работает Nginx, PostgreSQL, моя задача и еще ОС. И толку, что у Эрланга например все задачи сами распараллеливаются. Если считать на нем большие куски, то выхлопа 0.», а потом водружается это хозяйство на сервер, и оказывается, что решение тормознутое и вообще не годится даже для тестового показа как концепт - не то что для продакшна. Про последовательность обработки - это уже оптимизация внутри потока. Один фиг балансировать необходимо всё для эффективного использования ресурсов компьютера.

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

Sadler> Опять же, об этом должен «думать» компилятор, а не разработчик.

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

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

А его нет. Видюха по факту (с т.з. программирования, а в случае радиков 2xxx-5xxx и архитектурно) является этакой VLIW-херовиной, а не многоядерным процом.

svr4
()

А ещё не надо оптимизировать сайты - ведь у всех оптоволокно прямо до сотового телефона идет. Тоже не навязываю своего мнения :)

По сабжу - мой опыт говорит, что если не думать о скорости работы алгоритма/программы (в том числе о сложности используемого алгоритма) - получишь наверняка «тормоза». Не смотря на то, что нынешние компьютеры сильно быстрее старых - приложения часто тормозят. То есть чудесный O(n) всё-таки нужен, но и про многоядерность, конечно, нужно знать - чтобы выполнение программы легко (насколько это возможно) параллелилось. В общем, плюсую ТС.

P.S. NP полной задаче на «большом» графе глубоко пофигу ваши 128 ядер. Когда там вариантов на 15 вершинах много, но при этом про 20 лучше и не заикаться (O(n!)).

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

LTE/LTE-A в принципе по скорости сравним с ftth

Чуть зайдешь в здание и уже никакого тебе lte. Чуть отъедешь от центра города и хорошо, если EDGE есть.

grondek
()
Последнее исправление: grondek (всего исправлений: 1)
Ответ на: комментарий от svr4

У меня в некоторых торговых центрах вообще связь местами при ходьбе по коридорам пропадает (мегафон).

Ну и lte покрывает в основном города, чуток в сторону и нет его. Даже если ехать по региональной трассе.

grondek
()
Последнее исправление: grondek (всего исправлений: 1)
Ответ на: комментарий от Deleted

Подписываюсь под каждым словом. Задрали уже пихать в продакшен то, что жрет O(n^2) из-за их идиотизма.

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

Проблема параллельного программирования - только в отладке.

Взоржал

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

Так я про это и говорю - «у всех есть LTE». А то, что в Мособласти в некоторых местах (не столь отдаленных) edge - всем пофиг :)

Зато свистоперделкоплякоматериалдизайность - на высоте.

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

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

В чудесном мире поней вероятно узнают о появлении ЯП сразу как только аффтар его создал. Причем сразу начинают изучать его в университетах. Так вот Erlang широко стал известен ТОЛЬКО в 2000-х годах.

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

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

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

*пожав плечами*

То, что твой препод ничего не знал кроме делфи и крестобыдлера (той же делфи, но сбоку) - это его личные проблемы. Как и всех, выросших на турбопаскале.

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

Я написал, что «не совсем», так как под капотом там Introsort, который базируется на быстрой сортировке + переключение на другие, когда быстрая начинает проседать.

А если Вам именно чистый quicksort параллельный, то Вам хотя бы сюда: https://www.uio.no/studier/emner/matnat/ifi/INF3380/v10/undervisningsmaterial...

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

Мисье знает толк в извращениях!

Так я и говорю. Народ обчитается, что все надо распараллелить. Потом обчитается про Эрланг. И потом хочется обнять и плакать.

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

То, что твой препод ничего не знал кроме делфи и крестобыдлера

Я тебе открою страшную тайну. У моего препода фамилия была не Ванга и не Настродамус. Он и про делфи не знал :-) Ибо его небыло еще.

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

Я тебе открою страшную тайну. У моего препода фамилия была не Ванга и не Настродамус. Он и про делфи не знал :-) Ибо его небыло еще.

Тогда и OpenMP он тоже знать не мог, потому что OpenMP появился уже после Delphi.

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

Это уже вопросы к твоему опсосу, почему он не осилил низкие частоты. 800-900mhz lte в здании берет нормально.

за мкадом жизни нет, отличное алгоритмическое решение.

Rastafarra ★★★★
()

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

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

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

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

Вообще по пусть и не очень богатому опыту параллельного программирования скажу, что для того, чтобы врубиться в него требуется знакомство с куда более сложными материями, чем O(n). Требуется понимать ограничения архитектуры, что на 100+ ядрах у вас становятся неэффективными стандартные примитивы синхронизации, что «неблокирующие» алгоритмы становятся очень даже блокирующими и т.д.

Кстати, упомянутый QuickSort вполне себе академический. Энтони Хоар разработал его в 1957 году, находясь с группой студентов по обмену в Москве, в МГУ.

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

Это да. И в нормальном виде реализованный он может весить и 9Кб css + 7Кб js (muicss.com). Но так сложно и долго, поэтому некоторые http://www.material-ui.com «додумались» до того, что вместо CSS классов надо использовать стили на элементах:

Кнопка «до»:

<a href="https://github.com" class=«material-button»>GitHub</a>

Кнопка «после»:

<div style=«height: 36px; border-radius: 2px; transition: all 450ms cubic-bezier(0.23, 1, 0.32, 1) 0ms; top: 0px;»><span style=«position: relative; opacity: 1; font-size: 14px; letter-spacing: 0px; text-transform: uppercase; font-weight: 500; margin: 0px; user-select: none; padding-left: 16px; padding-right: 16px; color: rgb(255, 255, 255);»>GitHub</span></div>

Как говорится, «почуствуй разницу» %)

P.S. material-ui.com уже одумались и потихоньку рефакторят свои компоненты обратно к классам...

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

А он и не знал OpenMP. OpenMP у меня уже в университете был. А в техникуме где меня учили его небыло. Был DPD-11 с Rt11SJ. Был ЕС какой, то занюханный. Потом 286.

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

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

У меня был похожий случай. Я на работу пришел и там начальник написал софтину. Хорошая была софтина. Но когда оставалось 99% он находил в ней изъян. То библиотека новая выйдет. То алгоритм вот тут можно сделать быстрее... Вот за 10 лет пользователи так эту софтину и не увидели. Было 3-4 тестовых человека. Все очень хвалили (и она была хорошая). Я ему предлагал выпустить её в свет и потом заняться всеми доработками и оптимизациями, но ответ был одинаков «да тут на две недели работы, зато красота будет».

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

Нет. Он мне сообщил, что в школе надо Эрланг учить. Академические алгоритмы в современном программировании: не маразм ли? (комментарий)

А уже в универе я не особо учился CS. Собственно ни видел ни одного человека который там это учил. Универ кстати входил в 20-ку толи мировых толи Российских. Вот математика была зубодробительная. А делфи и сейчас преподают. 1С еще.

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

Опять же, об этом должен «думать» компилятор, а не разработчик.

Не получается пока думать. Железо весьма разнообразно в своих особенностях.

Именно.

Это и сейчас есть. +10% в среднем.

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

У меня был похожий случай.

Нет, там другое было. Не перфекционизм, а банально не работало. Типа слишком большая вибрация, потому что станина слишком лёгкая. Короче полная неюзабельность от постоянных инженерных просчётов.

atrus ★★★★★
()

У меня складывается стойкое ощущение, что использование классических супер-эффективных алгоритмов со всякими чудесными O(n) в современных реалиях, (...), это похоже на маразматическое ретроградство и заскорузлость мозга

На мой взгляд, в современных реалиях наиболее эффективно себя показывают алгоритмы «разделяй и властвуй» наподобие QuickSort

1. Устойчивость сортировки? Худший случай? Не, не слышали. А в курсе по алгоритмам рассказывают.

2. В библиотечных реализациях далеко не всегда чистый quicksort. Часто на малых размерах переключаются на другие алгоритмы. Почему? См. курсы по алгоритмам.

3. В одной из часто используемых реализаций долгое время quicksort был с «багом». Массив из равных элементов сортировался всегда за n^2. Причём так, что рандомизация не спасала. И даже в книжках до сих пор много где приведена эта «забаженная» реализация. В курсах по алгоритмам рассказывают, да.

4. И будь у тебя хоть 1000 ядер и идеально распараллеливаемый алгоритм, всё равно (лог)линейная сложность на больших размерах выстреливает у квадратичной принципиально. Увеличиваешь объём данных в 10 раз, надо ждать в 10 дольше, а не в 100. Это решает (кто сказал «big data»?). И об этом, кстати, доступно рассказывают в курсах по алгоритмам.

P.S. И это, ты серьёзно считаешь, что люди, которые профессионально занимаются алгоритмами, не в курсе про многопоточность?

nezamudich ★★
()

Уже и сюда веб-макаки добрались...

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

А можно информацию про реализацию быстрой сортировки, которая на равных элементах работает всегда за N^2? Первый раз про такое слышу и было бы очень интересно посмотреть на такую вот базовую реализацию. Потому что я не могу себе представить, что там за баг такой должен быть. Я знаю только про анти-quicksort тест, но там рандомизация спасает.

zamazan4ik ★★
()

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

Не знаю, то-ли ты тролль, то-ли совсем глуп. Асимптотическая сложность главенствовала и будет главенствовать всегда, и на 128 ядрах, и на 1024, и на миллионе, и на GPU, и на квантовых компьютерах, и гнать ссаными тряпками нужно прежде всего людей это не понимающих.

А вот многопоточный код - это тупик. Любая «синхронизация и склейка результатов» это оверхед растущий с числом потоков и ограничивающий производительность системы константой независимо от числа ядер, читай про закон Амдала. Так, для примера: если твоя синхронизация и склейка занимают всего 5%, на 128-ядерной машине прироста более чем в 17 раз ты не получишь. Т.е. 111 ядер ты просто выкинул. После чего выкидывают тебя и берут студента прочитавшего Кнута. Кроме того, современные реалии это, во-первых, GPU, где с синхронизацией как-бы не очень, во-вторых, данные не влезающие на одну машину, а на кластерах с синхронизацией ещё хуже.

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

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

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

Ладно не суть важно. Эрланг стал известен в 2000-х годах. Делая скидку на распространенность интернета и прочее это уже около 2005 года. Я вообще рад, что были преподы которые могли обучать чему, то типа C++ или Lisp (на который отвели 3 или 4 пары).

dmxrand
()

Распараллеливанием должен заниматься компилятор. Итеративное программирование - зло.

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

«Основы» могут сильно подзапутать и подзасрать мозг. Например те же мутабельные объекты при параллельном программирование дают больше вреда чем пользы. Допустим дана матрица, нужно каждый x[sub]i,j[/sub] заменить на среднее соседних ячеек. В случае иммутабельного объекта все великолепно параллелится, так как результат записывается в новый объект и число потоков может быть хоть равно числу ячеек. А вот если изменять значения прямо внутри матрицы, то распараллеливания не получится. И зачем тогда засирать мозг понятием мутабельности, если при параллельном программировании она не нужна?

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

И где такой ЯП? В rust всё равно придётся платить за синхронизацию и atomic. В Go возможны дедлоки. Всё остальное тормозит так, что толку от распараллеливания всё равно 0.

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

здесь вполне можно отправлять пользовательскому приложению части изображения

Ага. И получить артефакты на стыках блоков.

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

Ага. И получить артефакты на стыках блоков.

Тем не менее, так вполне себе делают, просто используют блоки с перекрытием. Скажем, в фильтрах фотошопа в API как раз передача результата происходит блоками.

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

Именно так. Но это необходимо, скажем, когда мы имеем ограниченный объём RAM. В таком случае обработка слишком больших блоков или всего изображения легко могла бы для некоторых фильтров уйти в swap или вообще не влезть никуда. Аналогично я делаю при генерации изображений нейросетями. Результат, конечно, чуть хуже, но иначе у меня бы просто памяти не хватило.

Sadler ★★★
()
Последнее исправление: Sadler (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.