|
|
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
mikhail_n wrote: > Аж дух захватывает... Вот мне интересно, а зачем мне иметь возможность > "В ЛЮБОЕ ВРЕМЯ ВЫПОЛНЕНИЯ ГАРАНТИРОВАННО БЕЗОПАСНО распараллелить" какую > - либо функцию, которая реализует глубоко сермяжно последовательный > алгоритм? Чтобы параллелить алгоритм в любой момент. Например, у тебя есть алгоритм (на ф.я.), который обрабатывает список и что-то считает. Список о 200 элементах. у тебя 10 процессоров. Ты берёшь алгоритм, разбиваешь на 10 частей, и запускаешь на 10 процессорах, потом сливаешь результаты. Получается примерно в 10 раз быстрее. Если единственное преимущество ф.я. с точки зрения > распаралеливания вычислений состоит в том что они заставляют кодить > потокобезопасные проги, то это несомненно круто, но вот заявлять что на > этом основании это им даёт какой-то там билет в будущее - имхо перебор. Ну, как бы я это не сам придумал. > Главные проблемы в этом направлении - минимизация последовательной части > алгоритмов и количество промахов по кэшу. Так что если затрагивать Главные проблемы в этом направлении -- иметь возможность параллелить алгоритмы. Далее уже можно думать о всём остальном. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 00:41:58 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
Диез wrote: > Одерский ) языки типа Scala и Nemerle, где можно писать вполне себе > императивные программы. А можно применить принципы ФП и забыть про > проблемы синхронизации потоков, mutable state, NullPointerException... > А заодно выкинуть из головы половину паттернов ООП, ибо более оные не > требуются :) Вот кстати да. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 00:43:11 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
Ggg_old wrote: > Диез, вы уже говорите коанами ;) SCALA - это lisp-подобный язык или я > ошибаюсь? Да ничуть. Лисп-подобный -- это Clojure. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 00:43:52 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
mayton wrote: > Мастер я рискну предположить, что на практике не так всё просто > и распараллеливание всего и вся еще не гарантирует быстрого > получения результата. Мне например не понятно, КТО и КАК будет > диспетчеризировать функции-процессы? На основании каких правил? Компилятор. Или интерпретатор. > Нужно учитывать накладные расходы на ту-же мультизадачность. Нужно-то нужно, но императивные языки вообще нифига не параллелятся автоматом. Их надо параллелить. Я на самом деле не большой знаток чистой функциональщины, наверное есть там куча своих проблем, но там принципиально хотя бы задача решается. Вообще, параллелизм очень хорошо возникает сам там, где есть абстракции высокого уровня и декларативные операции. Например, операции с матрицами и массивами в фортране, или запросы на SQL, или ещё что-то в этом роде. Там, где есть операнды, правила их обработки, и спецификация на результат, а процесс недетерменирован. В этом случае в условии наличия разных ресурсов можно реализовывать операции так или иначе. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 00:51:57 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
Чтобы параллелить алгоритм в любой момент. Например, у тебя есть алгоритм (на ф.я.), который обрабатывает список и что-то считает. Список о 200 элементах. у тебя 10 процессоров. Ты берёшь алгоритм, разбиваешь на 10 частей, и запускаешь на 10 процессорах, потом сливаешь результаты. Получается примерно в 10 раз быстрее. Погоди, погоди... Какой-то пример больно примитивный и удобный для тебя. Я спрашивал про тот случай, когда мне надо что-то сделать и известный мне алгоритм который это что-то делает глубоко последовательный. При работе с императивным языком единственным способом добиться ускорения за счёт распараллеливания - это выбросить известный мне последовательный алгоритм и придумать другой, который будет или полностью (в идеале) или хотя бы частично параллельным. Всё, других вариантов НЕТ. А с ф.я. у тебя что, есть альтернативы??? Главные проблемы в этом направлении -- иметь возможность параллелить алгоритмы. Далее уже можно думать о всём остальном. Опять же, причём здесь ф.я. против и.я? Возможность или невозможность параллелить АЛГОРИТМ зависит от количества и качества мозга в голове, а не от языка или модели программирования. Вообще, параллелизм очень хорошо возникает сам там, где есть абстракции высокого уровня и декларативные операции. Например, операции с матрицами и массивами в фортране, Такие вещи часто пишут в учебниках по программированию люди которые просто не представляют себе всех тонкостей численной реализации методов линейной алгебры. Все абстракции высокого уровня там заканчиваются в тот самый момент когда люди мало-мальски начинают задумываться о точности того, что их высоко абстрактные проги считают. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 01:34:24 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
mikhail_nПогоди, погоди... Какой-то пример больно примитивный и удобный для тебя. Я спрашивал про тот случай, когда мне надо что-то сделать и известный мне алгоритм который это что-то делает глубоко последовательный. При работе с императивным языком единственным способом добиться ускорения за счёт распараллеливания - это выбросить известный мне последовательный алгоритм и придумать другой, который будет или полностью (в идеале) или хотя бы частично параллельным. Всё, других вариантов НЕТ. А с ф.я. у тебя что, есть альтернативы???Пример кстати очень подходящий, но не объясненный до конца :) 1) Есть массив из многих элементов типа А. 2) Есть функция (последовательная) по превращению значения типа А в тип Б. 3) Надо в первом массиве обработать все ячейки и получить массив с данными типа Б. В императивном языке, ты делаешь цикл - обработать первую ячейку, обработать вторую ячейку и так далее. Либо вручную же разбиваешь оригинальный массив на несколько частей (по числу процессоров) и отдаешь каждую часть отдельному процессору. А на ФЯ ты даешь команду обработать такой-то массив такой-то функцией. Транслятор или виртуальная машина решает что если обработка одной ячейки массива не влияет на обработку другой (ничего не пишется обратно в исходные данные или в глобальные переменные) то обработку двух ячеек можно распараллелить, и соотвественно нагружает два процессора. Каждый из них будет заниматься своей ячейкой массива и вот эта обработка будет по прежнему последовательной. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 02:08:32 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
Хорошо, тогда скажи, чем вот это: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. отличается от того что ты описал? Кондовая императивная конструкция, вот просто слово в слово... Пока всё что я вижу из твоего объяснения (сам я ни одного ф.я. не знаю, но в отличии от Пастернака не осуждаю, просто хочу понять чем они так хороши для параллельных вычислений). Пока всё что я понял - цикла не надо. Ну вот я тоже цикл в фукцию спрячу и притворюсь что его там нет. А в остальном OMP озаботится тем чтоб всё было как ты написал... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 02:29:28 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
Ggg_oldВ приведенном коде на F# не видно ничего функционального. Обычный императивный код, только записанный необычным синтаксисом другого языка: "Для каждого элемента списка вызвать функцию такую-то, которая выполняет строгую последовательно операция". что делает async и чем use отличается от use! а так же что такое |> ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 06:20:43 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
Если немного переделать пример Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 1. Здесь нет гарантии, что someFunction не имеет какого-то побочного эффекта и не изменит свой результат в зависимости от порядка выполнения. В чисто функциональных языках такая гарантия была бы. 2. В функциональных языках это все записалось бы проще - так как развиты сроедства комбинирования функций. Типа Код: plaintext 1. Ну вот я тоже цикл в фукцию спрячу и притворюсь что его там нет В принципе, поверх С++ некоторые пишут функциональные языки - что-то такое в Boost входит. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 06:35:00 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
Ggg_oldВ приведенном коде на F# не видно ничего функционального. В принципе, кстати, да - F# не чисто функциональный - там можно писать с побочными эффектами. Но нельзя сказать, что приведенный фрагмент чисто императивный. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 06:38:52 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
Ggg_oldНарод, уже долгое время пытаюсь понять в чем суть и фишка направления под названием "функциональное программирование". В общем просьба объяснить простым языком, в чем соль, ради чего это все надо и где зарыт профит. Элементы функциональных языков. Евгений Кирпичёв Новые слова, ответы зачем? и почему? По тексту. Лямбда-исчисление. Зачем? В каком-то классе школы (я в третьем) мы изучали уравнения и было такое правило "иксы в левую часть уравнения, остальное в правую". С помощью такого нехитрого способа можно решать псевдологичекие задачки типа "Ваня старше Маши в 2 раза а Егор младше Вани на 15 лет". Беря такю аналогию, можно сказать лямбда-исчисление позволяет представить алгоритм в виде уравнения, которое с помощью алгебры можно упрощать, анализировать и преобразовывать. Карринг. Взмем функцию сложения двух чисел (+ x y) Но выдадим ей один аргумент (funcall #'+ 5) Если ЯП поддерживает карринг то мы получим частично примененую функцию (+5 y) которая будет складывать y и 5. Циклы. Циклы примерно равно "хвостовая рекурсия". Не циклы потому, что если избавились от переменных то зачем нам переменные цикла? Хотя сам процесс итерирования может иметь место. Сама фраза "преимущество решения задач в ФП-стиле перед императивным способом" в отрыве от контекста несколько бессмыслена. Вот императивный бэйсик [code] a = 2 b = 3 c = a + b [code] вот [+ a b] Просто мир императивной парадигмы сейчас включают в себя наряду с переменными, классы, объекты, паттерны, модели и ddd. А из функционального вводные статьи дают только лямбда-термы и рекурси. Почитай приведенную статью это несколько расширит рамки разговора. Или про Лисп, но серьезно. Связь ФЯ с декларативностью. Прямой связи нет, но "комбинаторы и бесточечный стиль". Вобще все зависит от точки зрения, я когда sql смотрю вижу функции select, update и create , замыкающие БД, и попробуй доказать что это не так. P. S. А вобще на этом форуме тема почти бессмысленая. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 08:23:26 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
Ggg_oldТ.е. что-бы быть на острие прогресса надо владеть ФП+С. Я конечно далек от того, чтобы видеть индустрию на порядок лучше тебя :), но подозреваю, что знание ФП не единственный способ быть на "острие прогресса" во первых и не достаточное условие для такого пребывания там, во вторых. Но то что оно не помешает, это факт ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 09:19:33 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
belugin Код: plaintext 1. 2. 3. 4. 5. 6. Оооо да !!! это оооочень полезно. Распараллеливать вычисление чисел Фиббоначи. Еще набивший всем оскомину пример с QuickSort-ом на Haskell-е мне нравится, всем QuickSort-ам QuickSort. А то что сортирует список, а не массив, так это не беда. Ну перестроит он его раз с десяток, так кому от этого плохо ??? А то что средний элемент всегда берет из головы списка, так нам повезет !!! Действительно, кому надо сортировать уже отсортированное ??? Зато алгоритм стал такой понятный понятный (не беда что другой). При знакомстве с трудами некоторых апологетов ФП полезно включать мозг. Некоторые примеры "крутости" ФП граничат с маразмом (Кстати за Кнутом или Виртом я такого не замечал ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 09:40:16 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
MasterZiv Например, у тебя есть алгоритм (на ф.я.), который обрабатывает список и что-то считает. Список о 200 элементах. у тебя 10 процессоров. Ты берёшь алгоритм, разбиваешь на 10 частей, и запускаешь на 10 процессорах, потом сливаешь результаты. Получается примерно в 10 раз быстрее. А на кой здесь ляд ФП ??? Такую замечтательную задачу можно запросто распараллелить даже на фортране ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 09:47:20 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
White Owl wrote: > исходные данные или в глобальные переменные) то обработку двух ячеек > можно распараллелить, и соотвественно нагружает два процессора. Каждый > из них будет заниматься своей ячейкой массива и вот эта обработка будет > по прежнему последовательной. Главное, что если процессоров 100, то точно так же можно загрузить 100 процессоров. А если 500 -- то 500. И при этом это от программиста не зависит. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 09:54:28 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
MasterZiv White Owl wrote: > исходные данные или в глобальные переменные) то обработку двух ячеек > можно распараллелить, и соотвественно нагружает два процессора. Каждый > из них будет заниматься своей ячейкой массива и вот эта обработка будет > по прежнему последовательной. Главное, что если процессоров 100, то точно так же можно загрузить 100 процессоров. А если 500 -- то 500. И при этом это от программиста не зависит. выше давался пример с omp ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 09:55:30 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
mikhail_n wrote: > #include <omp.h> > ..... > > double a[*100*]; > double b[*100*]; > > int N = *100*; > > void function imp_omp_parallel(int N, double a[], double b[]) > { > int i; > > #pragma omp parallel private(i) shared(a,b,N) > #pragma omp for > for(i = *0*; i < N; i++) > a[i] = i * b[i]; > } > > > отличается от того что ты описал? Кондовая императивная конструкция, вот > просто слово в слово... Компилятор С/С++ не имеет право параллелить твой код. И не знает, где это можно сделать. А в функциональных языках -- наоборот, и знает, и имеет право. > хочу понять чем они так хороши для параллельных вычислений). Пока всё > что я понял - цикла не надо. Ну вот я тоже цикл в фукцию спрячу и > притворюсь что его там нет. А в остальном OMP озаботится тем чтоб всё > было как ты написал... Главное не это , а то, что в ФЯ (чистых) нет побочных эффектов, и результат вызывова твоей фунции предсказуем из кода. И изза этого компилятор ЗНАЕТ где можно параллелить и как. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 09:58:09 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
MasterZiv Главное не это , а то, что в ФЯ (чистых) нет побочных эффектов, и результат вызывова твоей фунции предсказуем из кода. И изза этого компилятор ЗНАЕТ где можно параллелить и как. Лепота то какая, Лепота !!! (с) И много они автоматически распараллелили ??? Возможно OCaml автоматически распараллеливает вычисление чисел Фибоначчи ? нет ??? странно Ах да, накладные расходы съедят все бенефиты. QuickSort автоматически параллелить тоже как-то не очень получается :( Очевидно параллельные алгоритмы должны писаться специально, с учетом того, что они параллельные? А если так, то обеспечение функциональной чистоты того что параллелим всего лишь одна из маленьких задачек, решаемых разработчиком алгоритма. А если автоматического параллелизма нет и не будет, то какая разница на чем писать на Haskell-е или на Fortran-е ??? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 10:34:19 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
mikhail_nВозможность или невозможность параллелить АЛГОРИТМ зависит от количества и качества мозга в голове, а не от языка или модели программирования. Вообще, параллелизм очень хорошо возникает сам там, где есть абстракции высокого уровня и декларативные операции. Код: plaintext 1. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 11:47:16 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
Ggg_oldФишка номер 2, нет циклов, вообще нет циклов. Все надо определять через рекурсивные функции. Дейкстра показал, что применение рекурсии всегда просто не удобно. Поэтому и ввел операторы if-fi и do-od. Собсно вопрос схоластический - то ли ФЯ расширять до императивных, то ли наоборот (имхо так лучше). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 11:55:09 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
Gluk (Kazan)Оооо да !!! это оооочень полезно. Распараллеливать вычисление чисел Фиббоначи. Еще набивший всем оскомину пример с QuickSort-ом на Haskell-е мне нравится, всем QuickSort-ам QuickSort. А то что сортирует список, а не массив, так это не беда. Ну перестроит он его раз с десяток, так кому от этого плохо ??? Добавлю по поводу перформанса. Душкин в своей книге приводит пример метода вычисления списка простых чисел до заданного N. Но здесь-же признаётся, что Haskell-решение реализованное в лоб в характерной функционально манере работает чрезвычайно медленно и явно проигрывает С++-шному. Решение-же оптимальное по скорости на Haskell теряет некую красоту и выразительность. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 12:25:39 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
Gluk (Kazan) wrote: > выше давался пример с omp Всё понятно, как раз и прикол в том, что OMP для ФЯ не нужно. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 12:36:07 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
MasterZiv....Компилятор. Или интерпретатор. Я не о том. Приведу отвлечённый пример для императивного языка. Мне даны две матрицы A, B, 1000х1000 элементов. Надо их перемножить по правилам математики. Тривиальное решение - итеративный процесс, который обходит все элементы двух матриц и записывает результат в третью матрице. Он работает но не очень быстро. Далее - маргинальное решение, я стартую 1000 процессов(потоков) которые для каждой строки A(i) и столбца B(i) выполняют соотв. скалярное произведение векторов и сохраняют результата в матрицу С(i,j) и т.д по внешнему циклу j. Данное решение распараллелено по критерию который я придумал. Однако оно, очевидно не самое оптимальное. Я теряю время на квантах переключения между процессами (потоками), и теряю время на старт-стопе процессов(потоков), которое несколько выше чем callback функции. Очевидно, что надо увеличивать количество вычислительных потоков, но не сильно. Неплохой вариант - разбить матрицу на две 1000х500 и перемножить в два threads (исходя из предположения что бортовое железо Athlon X2 содержит два ядра и грузятся на 70-80% на момент вычислений). Или, если копнуть еще глубже, и узнать о перезагрузках кешей L1, L2 гарантировать что-бы в кешах лежали только перемножаемые данные, и сделать четыре thread для суб-матриц 1000x250. (Всё вышесказанное - чистая теория. На практике я это не проверял, и возможно где-то ошибаюсь но в общем моя мысль идёт в этом направлении). Так вот. К чему я это. В императивном языке я вручную управлял параллелизмом выбирая ту степень, которая наиболее оптимальня для отклика. Функциональный язык, очевидно будет руководствоваться какими-то другими критериями которых я не знаю. И если он выбырет ТРИВИАЛЬНЫЙ или МАРГИНАЛЬНЫЫЙ критерий количества потоков/процессов на функцию то мы вместо роста performance получим просадку. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 12:54:46 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 12:55:34 |
|
||
|
Функциональное программирование
|
|||
|---|---|---|---|
|
#18+
MasterZiv Gluk (Kazan) wrote: > выше давался пример с omp Всё понятно, как раз и прикол в том, что OMP для ФЯ не нужно. Гмм, повторю вопрос снова. Какая из реализаций ФЯ обеспечивает автоматическое распараллеливание ??? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2010, 13:27:14 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=36431121&tid=1343707]: |
0ms |
get settings: |
7ms |
get forum list: |
9ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
171ms |
get topic data: |
6ms |
get forum data: |
2ms |
get page messages: |
44ms |
get tp. blocked users: |
1ms |
| others: | 185ms |
| total: | 429ms |

| 0 / 0 |
