Функционализация числового кода

Question

Играя с F#, я пытаюсь думать о коде более функционально. Большая часть моей работы носит численный характер, поэтому я думаю, имеет ли смысл это перевоспитание. Является ли написание числового кода функциональным способом, как попытка вписать квадратный колышек в круглое отверстие, или это просто вопрос крутой кривой обучения независимо от приложения?

Например, давайте возьмем фрагмент, который демонстрирует слабый закон больших чисел:

open System
open System.IO
open System.Windows.Forms
open System.Windows.Forms.DataVisualization
open FSharp.Data
open FSharp.Charting
open FSharp.Core.Operators
open MathNet.Numerics
open MathNet.Numerics.LinearAlgebra
open MathNet.Numerics.Random
open MathNet.Numerics.Distributions
open MathNet.Numerics.Statistics


let T = 1000

let arr1 = Array.init T (fun i -> float i*0.)
for i in 0 .. T-1 do
    arr1.[i] <- [|for j in 1..i do yield Exponential.Sample(0.1)|] |> Statistics.Mean

let arr2 = Array.init T (fun i -> float i*0.)
for i in 0 .. T-1 do
    arr2.[i] <- arr1.[1 .. i] |> Statistics.Mean

arr2 |> Chart.Line |> Chart.Show

Существует ли краткий функциональный способ выражения вышесказанного? Какую часть функциональной парадигмы можно включить в такую ​​работу?

Не уверен, что вопрос не по теме. Благодарю.

Answer 1

Я бы сначала не отделил звонок Array.init и установка начальных значений. Вы можете использовать форму, которую @s952163 использует в своем ответе, или основываясь на вашем коде:

let arr1 = Array.init T (fun i ->
    [|for j in 1..i do yield Exponential.Sample 0.1 |] |> Statistics.Mean
)

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

let arr1 = Array.init T (fun i ->
    Exponential.Samples 0.1 |> Seq.take (i+1) |> Seq.average
)

Теперь для второй части: Вы повторно вычисляете среднее значение элементов 1..i, что становится операцией O(n^2). Вы можете решить это в O(n), используя тот факт, что сумма элементов 1..i является суммой элементов 1..{i-1} плюс i.th элемент.

let sums, _ =
    arr1
    |> Array.mapFold (fun sumSoFar xi ->
        let s = sumSoFar + xi
        s, s
    ) 0.0
let arr2 = 
    sums
    |> Array.mapi (fun i sumi -> sumi / (float (i + 1)))

Конечно, вы все можете написать это в одной трубе.

В качестве альтернативы, используйте функцию библиотеки Array.scan вычислить кумулятивные суммы, которые в этом случае дали бы результат длины T+1, из которого вы бы тогда отбросили первый элемент:

let arr2 =
    Array.sub (Array.scan (+) 0.0 arr1) 1 T
    |> Array.mapi (fun i sumi -> sumi / (float (i + 1)))

или избегайте промежуточных массивов:

Seq.scan (+) 0.0 arr1
|> Seq.skip 1
|> Seq.mapi (fun i sumi -> sumi / (float (i + 1)))
|> Seq.toArray

Answer 2

На самом деле это два вопроса: один об улучшении данного кода и один о функциональном числовом коде в F#. Поскольку другие ответы уже сосредоточены на конкретном коде, я сосредоточусь на более общем вопросе.

Это о производительности?

По моему опыту, пригодность функционального программирования в цифрах зависит от требований к производительности. Чем важнее время выполнения, тем больше вы можете пойти на компромисс в функциональном стиле.

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

Если производительность является проблемой, вы можете пойти на компромисс в неизменяемости. Основная стоимость функционального кода в F# исходит от сборщика мусора, особенно от объектов с промежуточным временем жизни. Создание дорогостоящих объектов, изменяемых и повторное их использование, может иметь огромное значение в скорости выполнения. Если вы хотите писать такие вещи, как гидродинамика, симуляции n-тела или игры, кратким и безопасным способом, но не стремитесь к скорости выполнения педали до металла, стиль F# с несколькими парадигмами может быть хорошим способом идти.

Если производительность - это все, скорее всего, вы все равно хотите запустить GPU. Или, может быть, хорошо использовать векторные модули ЦП, многопоточность и так далее. Хотя есть попытки использовать F# на GPU, язык просто не рассчитан на скорость любой ценой. Возможно, в таких ситуациях лучше использовать язык, более близкий к аппаратному.

Когда проблема представляет собой смесь из них, часто можно смешать решения. Например, вчера мне нужно было сделать расчёт на пиксель для набора изображений, и время выполнения было важно. Поэтому я читал изображения в F# с использованием библиотеки.NET, затем загружал их в графический процессор вместе с вычислительным шейдером GLSL, который преобразовывал пиксели, а затем загружал их обратно в "землю F#". Дело в том, что управленческие операции неэффективны; код все еще копирует вещи без какой-либо реальной причины. Но это была всего лишь одна операция, которая снизила бы всю производительность, поэтому разумно использовать высокопроизводительный инструмент для этой одной операции, тогда как все остальное происходит аккуратно и безопасно в F#.

Answer 3

Я думаю, что это очень хороший вопрос. У меня сложилось впечатление, что проблема, с которой вы столкнетесь при написании функционального числового кода (думаю, Matlab vs Mathematica) не в синтаксисе, а в производительности. Но в то же время распараллелить код очень легко.

Я бы написал ваш код так:

let arr1' = [|for i in 0..1000 -> Array.init i (fun i -> Exponential.Sample(0.1)) |> Statistics.Mean |]

Обратите внимание, что а) нет изменяемого присваивания, б) нет индексации и в) я не инициализирую массив на основе 0 и не заполняю его, а вместо этого инициализирую массив с помощью функции.

Я также хотел бы выяснить, возможно ли генерировать сэмплы напрямую с помощью Exponential.Sample, а не вызывать его 1000 раз.

редактировать

Как это: Exponential.Samples(0.1) |> Seq.take 1000

И на основе комментария @ChristophRüegg ниже:

let expoMean (x:float []) =
    Exponential.Samples(x,0.1)
    x |> Statistics.Mean

Array.init 1000 (fun _ -> Array.replicate 1000 0. |> expoMean)

Я не тестировал это.