목록의 이동 평균 계산
이번 주말에 저는 Scala와 Clojure를 시험해보기로했습니다. 저는 객체 지향 프로그래밍에 능숙해서 Scala는 언어로 쉽게 익힐 수 있었지만 함수형 프로그래밍을 시도하고 싶었습니다. 여기가 힘들어졌습니다.
함수를 작성하는 모드에 머리를 넣을 수없는 것 같습니다. 전문 기능 프로그래머로서 문제에 어떻게 접근합니까?
값 목록과 정의 된 합산 기간이 주어지면 목록의 단순 이동 평균에 대한 새 목록을 어떻게 생성합니까?
예 : 목록 values(2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0)과 period4가 주어지면 함수는 다음을 반환해야합니다. (0.0, 0.0, 0.0, 4.75, 5.0, 6.0, 7.25, 8.0, 8.25, 6.5)
하루 종일 고민 한 후 Scala에서 생각 해낼 수있는 최선의 방법은 다음과 같습니다.
def simpleMovingAverage(values: List[Double], period: Int): List[Double] = {
(for (i <- 1 to values.length)
yield
if (i < period) 0.00
else values.slice(i - period, i).reduceLeft(_ + _) / period).toList
}
나는 이것이 끔찍하게 비효율적이라는 것을 알고 있습니다.
where n < period: ma(n) = 0
where n = period: ma(n) = sum(value(1) to value(n)) / period
where n > period: man(n) = ma(n -1) - (value(n-period) / period) + (value(n) / period)
이제 그것은 명령형 스타일로 쉽게 할 수 있지만, 나는 그것을 기능적으로 표현하는 방법을 평생 동안 연구 할 수 없습니다.
흥미로운 문제입니다. 효율성의 정도가 다른 많은 솔루션을 생각할 수 있습니다. 항목을 반복해서 추가해야하는 것은 실제로 성능 문제는 아니지만 그렇다고 가정 해 봅시다. 또한 처음에있는 0은 나중에 추가 할 수 있으므로 생성에 대해 걱정하지 마십시오. 알고리즘이 자연스럽게 제공한다면 괜찮습니다. 그렇지 않은 경우 나중에 수정합니다.
Scala 2.8부터 다음은 목록의 슬라이딩 창을 가져 오는 데 n >= period사용하여 결과를 제공합니다 sliding.
def simpleMovingAverage(values: List[Double], period: Int): List[Double] =
List.fill(period - 1)(0.0) ::: (values sliding period map (_.sum) map (_ / period))
그럼에도 불구하고 이것은 다소 우아하지만 이미 계산 된 덧셈을 활용하지 않기 때문에 가능한 최고의 성능을 갖지 못합니다. 그래서, 그들에 대해 말하면 어떻게 얻을 수 있습니까?
다음과 같이 작성한다고 가정 해 보겠습니다.
values sliding 2 map sum
우리는 각 두 쌍의 합계 목록이 있습니다. 이 결과를 사용하여 4 개 요소의 이동 평균을 계산해 봅시다. 위의 공식은 다음과 같은 계산을했습니다.
from d1, d2, d3, d4, d5, d6, ...
to (d1+d2), (d2+d3), (d3+d4), (d4+d5), (d5+d6), ...
따라서 각 요소를 가져와 두 번째 다음 요소에 추가하면 4 개의 요소에 대한 이동 평균을 얻습니다.
(d1+d2)+(d3+d4), (d2+d3)+(d4+d5), (d3+d4)+(d5+d6), ...
다음과 같이 할 수 있습니다.
res zip (res drop 2) map Function.tupled(_+_)
그런 다음 8 개 요소에 대한 이동 평균을 계산할 수 있습니다. 음, 그러한 패턴을 따르는 것을 계산하는 잘 알려진 알고리즘이 있습니다. 숫자의 힘을 계산하는 데 사용되는 것으로 가장 잘 알려져 있습니다. 다음과 같이 진행됩니다.
def power(n: Int, e: Int): Int = e match {
case 0 => 1
case 1 => n
case 2 => n * n
case odd if odd % 2 == 1 => power(n, (odd - 1)) * n
case even => power(power(n, even / 2), 2)
}
여기에 적용 해 보겠습니다.
def movingSum(values: List[Double], period: Int): List[Double] = period match {
case 0 => throw new IllegalArgumentException
case 1 => values
case 2 => values sliding 2 map (_.sum)
case odd if odd % 2 == 1 =>
values zip movingSum(values drop 1, (odd - 1)) map Function.tupled(_+_)
case even =>
val half = even / 2
val partialResult = movingSum(values, half)
partialResult zip (partialResult drop half) map Function.tupled(_+_)
}
그래서 여기에 논리가 있습니다. 기간 0은 유효하지 않고 기간 1은 입력과 같고 기간 2는 크기 2의 슬라이딩 윈도우입니다. 그보다 크면 짝수 또는 홀수 일 수 있습니다.
이상한 경우 각 요소를 movingSum다음 (odd - 1)요소 의 에 추가 합니다. 예를 들어, 3 인 경우 movingSum다음 2 개 요소 의 에 각 요소를 추가 합니다.
짝수 인 경우 movingSumfor를 계산 n / 2한 n / 2다음 나중에 각 요소를 한 단계에 추가합니다 .
이 정의를 사용하면 문제로 돌아가 다음을 수행 할 수 있습니다.
def simpleMovingAverage(values: List[Double], period: Int): List[Double] =
List.fill(period - 1)(0.0) ::: (movingSum(values, period) map (_ / period))
의 사용과 관련하여 약간의 비 효율성이 :::있지만 O (values.size)가 아니라 O (기간)입니다. 꼬리 재귀 함수로 더 효율적으로 만들 수 있습니다. 그리고 물론 내가 제공 한 "슬라이딩"의 정의는 성능면에서 끔찍하지만 Scala 2.8에서는 훨씬 더 나은 정의가있을 것입니다. 에서 효율적인 sliding메서드를 만들 List수는 없지만 Iterable.
모든 것을 말했듯이, 나는 첫 번째 정의를 사용하고 중요한 경로 분석이 이것을 큰 문제로 지적한 경우에만 최적화 할 것입니다.
결론을 내리기 위해 내가 어떻게 문제를 해결했는지 생각해 봅시다. 이동 평균 문제가 있습니다. 이동 평균은 목록에서 이동하는 "창"의 합계를 해당 창의 크기로 나눈 값입니다. 그래서 먼저 슬라이딩 윈도우를 가져 와서 모든 것을 합한 다음 크기로 나눕니다.
다음 문제는 이미 계산 된 덧셈의 반복을 피하는 것이 었습니다. 이 경우 가능한 가장 작은 덧셈으로 가서 그러한 결과를 재사용하여 더 큰 합계를 계산하는 방법을 알아 내려고했습니다.
마지막으로 이전 결과에서 더하고 빼서 생각한 방식으로 문제를 해결해 보겠습니다. 첫 번째 평균을 얻는 것은 쉽습니다.
def movingAverage(values: List[Double], period: Int): List[Double] = {
val first = (values take period).sum / period
이제 우리는 두 개의 목록을 만듭니다. 먼저 뺄 요소 목록입니다. 다음으로 추가 할 요소 목록 :
val subtract = values map (_ / period)
val add = subtract drop period
을 사용하여이 두 목록을 추가 할 수 있습니다 zip. 이 방법은 더 작은 목록에있는만큼의 요소 만 생성하므로 subtract필요 이상으로 커지는 문제를 방지 할 수 있습니다 .
val addAndSubtract = add zip subtract map Function.tupled(_ - _)
결과를 폴드로 구성하여 마무리합니다.
val res = (addAndSubtract.foldLeft(first :: List.fill(period - 1)(0.0)) {
(acc, add) => (add + acc.head) :: acc
}).reverse
이것이 반환 될 답입니다. 전체 기능은 다음과 같습니다.
def movingAverage(values: List[Double], period: Int): List[Double] = {
val first = (values take period).sum / period
val subtract = values map (_ / period)
val add = subtract drop period
val addAndSubtract = add zip subtract map Function.tupled(_ - _)
val res = (addAndSubtract.foldLeft(first :: List.fill(period - 1)(0.0)) {
(acc, add) => (add + acc.head) :: acc
}).reverse
res
}
저는 Scala보다 Clojure를 더 잘 알고 있습니다. 이 글을 쓸 때 여기에 다른 Clojure 항목이 필수적입니다. 그것은 실제로 당신이 추구하는 것이 아닙니다 (관용적 인 Clojure가 아닙니다). 내 마음에 떠오르는 첫 번째 알고리즘은 시퀀스에서 요청 된 수의 요소를 반복적으로 가져와 첫 번째 요소를 삭제하고 반복하는 것입니다.
다음은 모든 종류의 시퀀스 (벡터 또는 목록, 게으른 여부)에서 작동하며 평균의 지연 시퀀스를 제공합니다. 이는 무한한 크기의 목록에서 작업하는 경우 유용 할 수 있습니다. 목록에 소비 할 요소가 충분하지 않은 경우 암시 적으로 nil을 반환하여 기본 케이스를 처리합니다.
(defn moving-average [values period]
(let [first (take period values)]
(if (= (count first) period)
(lazy-seq
(cons (/ (reduce + first) period)
(moving-average (rest values) period))))))
테스트 데이터에서 이것을 실행하면
user> (moving-average '(2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0) 4)
(4.75 5.0 6.0 7.25 8.0 8.25 6.5)
시퀀스의 처음 몇 가지 요소에 대해 "0"을 제공하지 않지만 쉽게 처리 할 수 있습니다 (다소 인위적으로).
가장 쉬운 방법은 패턴을보고 청구서에 맞는 사용 가능한 기능을 떠 올릴 수있는 것입니다. partition시퀀스의 일부에 대한 게으른보기를 제공하며이를 매핑 할 수 있습니다.
(defn moving-average [values period]
(map #(/ (reduce + %) period) (partition period 1 values))
누군가 꼬리 재귀 버전을 요청했습니다. 꼬리 재귀 대 게으름은 약간의 절충안입니다. 작업이 목록을 작성하는 경우 함수 꼬리를 재귀 적으로 만드는 것은 일반적으로 매우 간단하며 예외는 아닙니다. 목록을 하위 함수에 대한 인수로 작성하기 만하면됩니다. 목록 대신 벡터에 누적됩니다. 그렇지 않으면 목록이 거꾸로 작성되고 마지막에 반전되어야하기 때문입니다.
(defn moving-average [values period]
(loop [values values, period period, acc []]
(let [first (take period values)]
(if (= (count first) period)
(recur (rest values) period (conj acc (/ (reduce + first) period)))
acc))))
loop익명의 내부 함수를 만드는 방법입니다 (Scheme의 let이라는 이름과 같은 종류). recur마무리 호출을 제거하려면 Clojure에서 사용해야합니다. 컬렉션에 자연스러운 방식으로 추가 conj되는 일반화 된 cons, 목록의 시작과 벡터의 끝입니다.
다음은 또 다른 (기능적) Clojure 솔루션입니다.
(평균 [coll] 정의
(/ (축소 + coll)
(카운트 콜)))
(defn ma [period coll]
(맵 평균 (파티션 기간 1 coll)))
필요한 경우 시퀀스 시작 부분의 0을 추가해야합니다.
여기 Clojure의 순전히 기능적인 솔루션이 있습니다. 더 이미 제공된 것보다 복잡하지만은 게으른 하고 만 대신 처음부터 다시 계산의 각 단계에서 평균을 조정합니다 . 주기가 작은 경우 각 단계에서 새로운 평균을 계산하는 간단한 솔루션보다 실제로 느립니다. 그러나 (/ (take period ...) period)더 긴 기간 동안에는 실제로 속도 저하가 발생하지 않는 반면 수행 하는 작업 은 더 오랜 기간 동안 성능이 저하됩니다.
(defn moving-average
"Calculates the moving average of values with the given period.
Returns a lazy seq, works with infinite input sequences.
Does not include initial zeros in the output."
[period values]
(let [gen (fn gen [last-sum values-old values-new]
(if (empty? values-new)
nil
(let [num-out (first values-old)
num-in (first values-new)
new-sum (+ last-sum (- num-out) num-in)]
(lazy-seq
(cons new-sum
(gen new-sum
(next values-old)
(next values-new)))))))]
(if (< (count (take period values)) period)
nil
(map #(/ % period)
(gen (apply + (take (dec period) values))
(cons 0 values)
(drop (dec period) values))))))
다음은 부분적으로 점이없는 한 줄 Haskell 솔루션입니다.
ma p = reverse . map ((/ (fromIntegral p)) . sum . take p) . (drop p) . reverse . tails
먼저 목록에 꼬리 를 적용 하여 "꼬리"목록을 얻습니다.
Prelude List> tails [2.0, 4.0, 7.0, 6.0, 3.0]
[[2.0,4.0,7.0,6.0,3.0],[4.0,7.0,6.0,3.0],[7.0,6.0,3.0],[6.0,3.0],[3.0],[]]
되돌리고 첫 번째 'p'항목을 삭제합니다 (여기서 p를 2로 사용).
Prelude List> (drop 2 . reverse . tails) [2.0, 4.0, 7.0, 6.0, 3.0]
[[6.0,3.0],[7.0,6.0,3.0],[4.0,7.0,6.0,3.0],[2.0,4.0,7.0,6.0,3.0]]
(.) 도트 / 니플 기호에 익숙하지 않은 경우 '기능적 구성'의 연산자입니다. 즉, 한 함수의 출력을 다른 함수의 입력으로 전달하여 단일 함수로 "구성"합니다. (g. f)는 "값에 대해 f를 실행 한 다음 출력을 g에 전달"을 의미하므로 ((f. g) x)는 (g (fx))와 동일합니다. 일반적으로 그 사용법은 더 명확한 프로그래밍 스타일로 이어집니다.
그런 다음 ((/ (fromIntegral p)). sum. take p) 함수를 목록에 매핑합니다. 따라서 목록의 모든 목록에 대해 첫 번째 'p'요소를 가져 와서 합한 다음 'p'로 나눕니다. 그런 다음 "reverse"로 목록을 다시 뒤집습니다.
Prelude List> map ((/ (fromIntegral 2)) . sum . take 2) [[6.0,3.0],[7.0,6.0,3.0]
,[4.0,7.0,6.0,3.0],[2.0,4.0,7.0,6.0,3.0]]
[4.5,6.5,5.5,3.0]
이 모든 것이 실제보다 훨씬 비효율적으로 보입니다. "reverse"는 목록이 평가 될 때까지 목록의 순서를 물리적으로 바꾸지 않고 스택에 배치합니다 (좋은 ol '게으른 Haskell). "꼬리"는 또한 이러한 모든 개별 목록을 만드는 것이 아니라 원래 목록의 다른 섹션을 참조 할뿐입니다. 여전히 훌륭한 솔루션은 아니지만 한 줄 길이입니다. :)
다음은 mapAccum을 사용하여 슬라이딩 빼기와 더하기를 수행하는 약간 더 좋지만 더 긴 솔루션입니다.
ma p l = snd $ mapAccumL ma' a l'
where
(h, t) = splitAt p l
a = sum h
l' = (0, 0) : (zip l t)
ma' s (x, y) = let s' = (s - x) + y in (s', s' / (fromIntegral p))
먼저 목록을 "p"에서 두 부분으로 분할합니다.
Prelude List> splitAt 2 [2.0, 4.0, 7.0, 6.0, 3.0]
([2.0,4.0],[7.0,6.0,3.0])
첫 번째 비트를 더합니다.
Prelude List> sum [2.0, 4.0]
6.0
두 번째 비트를 원래 목록으로 압축합니다 (이는 두 목록에서 순서대로 항목을 쌍으로 묶음). 원래 목록은 분명히 더 길지만이 추가 비트를 잃습니다.
Prelude List> zip [2.0, 4.0, 7.0, 6.0, 3.0] [7.0,6.0,3.0]
[(2.0,7.0),(4.0,6.0),(7.0,3.0)]
이제 mapAccum (ulator)에 대한 함수를 정의합니다. mapAccumL 는 "맵"과 동일하지만 추가 실행 상태 / 누적 기 매개 변수가 있습니다.이 매개 변수는 맵이 목록을 통해 실행될 때 이전 "매핑"에서 다음 "매핑"으로 전달됩니다. 누산기를 이동 평균으로 사용하고 목록이 슬라이딩 창을 방금 떠난 요소와 방금 입력 한 요소 (방금 압축 한 목록)로 구성되므로 슬라이딩 함수는 첫 번째 숫자 'x'를 사용합니다. 평균에서 벗어나 두 번째 숫자 'y'를 더합니다. 그런 다음 새로운 's'를 전달하고 's'를 'p'로 나눈 값을 반환합니다. "snd"(두 번째)는 mapAccumL의 두 번째 반환 값을 가져 오는 데 사용되는 쌍 (튜플)의 두 번째 구성원 만 가져옵니다.
$ 기호에 익숙하지 않은 사용자에게는 "응용 프로그램 연산자"입니다. 실제로는 아무것도하지 않지만 "낮은 오른쪽 연관 바인딩 우선 순위"가 있으므로 대괄호를 생략 할 수 있습니다 (LISPers에주의). 즉 (fx)는 f $ x와 동일합니다.
실행 (ma 4 [2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0])은 두 솔루션 모두에 대해 [4.75, 5.0, 6.0, 7.25, 8.0, 8.25, 6.5]를 산출합니다.
아 그리고 두 솔루션을 모두 컴파일하려면 "List"모듈을 가져와야합니다.
Scala 2.8.0에서 이동 평균을 수행하는 두 가지 방법이 더 있습니다 (하나는 엄격하고 하나는 게으름). 둘 다 vs 에 적어도 p Doubles 가 있다고 가정 합니다.
// strict moving average
def sma(vs: List[Double], p: Int): List[Double] =
((vs.take(p).sum / p :: List.fill(p - 1)(0.0), vs) /: vs.drop(p)) {(a, v) =>
((a._1.head - a._2.head / p + v / p) :: a._1, a._2.tail)
}._1.reverse
// lazy moving average
def lma(vs: Stream[Double], p: Int): Stream[Double] = {
def _lma(a: => Double, vs1: Stream[Double], vs2: Stream[Double]): Stream[Double] = {
val _a = a // caches value of a
_a #:: _lma(_a - vs2.head / p + vs1.head / p, vs1.tail, vs2.tail)
}
Stream.fill(p - 1)(0.0) #::: _lma(vs.take(p).sum / p, vs.drop(p), vs)
}
scala> sma(List(2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0), 4)
res29: List[Double] = List(0.0, 0.0, 0.0, 4.75, 5.0, 6.0, 7.25, 8.0, 8.25, 6.5)
scala> lma(Stream(2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0), 4).take(10).force
res30: scala.collection.immutable.Stream[Double] = Stream(0.0, 0.0, 0.0, 4.75, 5.0, 6.0, 7.25, 8.0, 8.25, 6.5)
J 프로그래밍 언어는 이동 평균과 같은 프로그램을 용이하게합니다. 실제로 (+/ % #)\'이동 평균'이라는 레이블보다 문자가 적습니다 .
이 질문에 지정된 값 ( 'values'이름 포함)에 대해 다음을 코딩하는 간단한 방법이 있습니다.
values=: 2 4 7 6 3 8 12 9 4 1
4 (+/ % #)\ values
4.75 5 6 7.25 8 8.25 6.5
구성 요소에 대한 레이블을 사용하여이를 설명 할 수 있습니다.
periods=: 4
average=: +/ % #
moving=: \
periods average moving values
4.75 5 6 7.25 8 8.25 6.5
두 예제 모두 정확히 동일한 프로그램을 사용합니다. 유일한 차이점은 두 번째 형식에 더 많은 이름을 사용한다는 것입니다. 이러한 이름은 J 프라이 머리를 모르는 독자에게 도움이 될 수 있습니다.
서브 프로그램에서 무슨 일이 일어나고 있는지 좀 더 살펴 보겠습니다 average. +/합산 (Σ)을 %나타내고 나누기를 나타냅니다 (예 : 고전 기호 ÷). 항목의 집계 (수) 계산은에서 수행합니다 #. 그러면 전체 프로그램은 값의 합계를 값의 합계로 나눈 값입니다.+/ % #
여기에 작성된 이동 평균 계산 결과에는 원래 질문에서 예상했던 선행 0이 포함되지 않습니다. 이러한 0은 의도 된 계산의 일부가 아닙니다.
여기에 사용 된 기술을 암묵적 프로그래밍이라고합니다. 이것은 함수형 프로그래밍의 포인트없는 스타일과 거의 동일합니다.
다음은 더 기능적인 언어 인 척하는 Clojure입니다. 이것은 완전히 꼬리 재귀 적이며 btw이며 선행 0을 포함합니다.
(defn moving-average [period values]
(loop [[x & xs] values
window []
ys []]
(if (and (nil? x) (nil? xs))
;; base case
ys
;; inductive case
(if (< (count window) (dec period))
(recur xs (conj window x) (conj ys 0.0))
(recur xs
(conj (vec (rest window)) x)
(conj ys (/ (reduce + x window) period)))))))
(deftest test-moving-average
(is (= [0.0 0.0 0.0 4.75 5.0 6.0 7.25 8.0 8.25 6.5]
(moving-average 4 [2.0 4.0 7.0 6.0 3.0 8.0 12.0 9.0 4.0 1.0]))))
일반적으로 함수를 커리하기 쉽게하기 위해 collection 또는 list 매개 변수를 마지막에 넣습니다. 하지만 Clojure에서는 ...
(partial moving-average 4)
... 너무 번거롭고, 보통 이렇게하게됩니다 ...
#(moving-average 4 %)
... 어떤 경우에는 매개 변수가 어떤 순서로 가는지는 실제로 중요하지 않습니다.
다음은 클로저 버전입니다.
lazy-seq로 인해 완벽하게 일반적이며 스택을 날리지 않습니다.
(defn partialsums [start lst]
(lazy-seq
(if-let [lst (seq lst)]
(cons start (partialsums (+ start (first lst)) (rest lst)))
(list start))))
(defn sliding-window-moving-average [window lst]
(map #(/ % window)
(let [start (apply + (take window lst))
diffseq (map - (drop window lst) lst)]
(partialsums start diffseq))))
;; 수행중인 작업을 확인하려면 :
(sliding-window-moving-average 5 '(1 2 3 4 5 6 7 8 9 10 11))
start = (+ 1 2 3 4 5) = 15
diffseq = - (6 7 8 9 10 11)
(1 2 3 4 5 6 7 8 9 10 11)
= (5 5 5 5 5 5)
(partialsums 15 '(5 5 5 5 5 5) ) = (15 20 25 30 35 40 45)
(map #(/ % 5) (20 25 30 35 40 45)) = (3 4 5 6 7 8 9)
;; 예
(take 20 (sliding-window-moving-average 5 (iterate inc 0)))
이 예제는 상태를 사용합니다.이 경우에는 실용적인 솔루션이고 창 평균화 함수를 만드는 클로저입니다.
(defn make-averager [#^Integer period]
(let [buff (atom (vec (repeat period nil)))
pos (atom 0)]
(fn [nextval]
(reset! buff (assoc @buff @pos nextval))
(reset! pos (mod (+ 1 @pos) period))
(if (some nil? @buff)
0
(/ (reduce + @buff)
(count @buff))))))
(map (make-averager 4)
[2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0])
;; yields =>
(0 0 0 4.75 5.0 6.0 7.25 8.0 8.25 6.5)
부작용이없는 것은 아니지만 일류 함수를 사용한다는 의미에서 여전히 기능적입니다. 언급 한 두 언어는 모두 JVM 위에서 실행되므로 필요한 경우 상태 관리를 허용합니다.
이 솔루션은 저에게 더 친숙한 Haskell에 있습니다.
slidingSums :: Num t => Int -> [t] -> [t]
slidingSums n list = case (splitAt (n - 1) list) of
(window, []) -> [] -- list contains less than n elements
(window, rest) -> slidingSums' list rest (sum window)
where
slidingSums' _ [] _ = []
slidingSums' (hl : tl) (hr : tr) sumLastNm1 = sumLastN : slidingSums' tl tr (sumLastN - hl)
where sumLastN = sumLastNm1 + hr
movingAverage :: Fractional t => Int -> [t] -> [t]
movingAverage n list = map (/ (fromIntegral n)) (slidingSums n list)
paddedMovingAverage :: Fractional t => Int -> [t] -> [t]
paddedMovingAverage n list = replicate (n - 1) 0 ++ movingAverage n list
스칼라 번역 :
def slidingSums1(list: List[Double], rest: List[Double], n: Int, sumLastNm1: Double): List[Double] = rest match {
case Nil => Nil
case hr :: tr => {
val sumLastN = sumLastNm1 + hr
sumLastN :: slidingSums1(list.tail, tr, n, sumLastN - list.head)
}
}
def slidingSums(list: List[Double], n: Int): List[Double] = list.splitAt(n - 1) match {
case (_, Nil) => Nil
case (firstNm1, rest) => slidingSums1(list, rest, n, firstNm1.reduceLeft(_ + _))
}
def movingAverage(list: List[Double], n: Int): List[Double] = slidingSums(list, n).map(_ / n)
def paddedMovingAverage(list: List[Double], n: Int): List[Double] = List.make(n - 1, 0.0) ++ movingAverage(list, n)
기간에 관계없이 O (목록 길이)라는 장점이있는 짧은 Clojure 버전 :
(defn moving-average [list period]
(let [accums (let [acc (atom 0)] (map #(do (reset! acc (+ @acc %1 ))) (cons 0 list)))
zeros (repeat (dec period) 0)]
(concat zeros (map #(/ (- %1 %2) period) (drop period accums) accums))))
이는 시퀀스의 누적 합계 (예 : [1 2 3 4 5]-> [0 1 3 6 10 15])를 만든 다음 두 숫자를 빼서 숫자 범위의 합계를 계산할 수 있다는 사실을 이용합니다. 귀하의 기간과 동일한 오프셋.
나는 파이썬에서 어떻게 할 것인지 알고 있습니다 (참고 : 0.0 값을 가진 처음 3 개의 요소는 실제로 이동 평균을 나타내는 적절한 방법이 아니기 때문에 반환되지 않습니다). Scala에서도 비슷한 기술이 가능할 것이라고 생각합니다. 여기에 여러 가지 방법이 있습니다.
data = (2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0)
terms = 4
expected = (4.75, 5.0, 6.0, 7.25, 8.0, 8.25, 6.5)
# Method 1 : Simple. Uses slices
assert expected == \
tuple((sum(data[i:i+terms])/terms for i in range(len(data)-terms+1)))
# Method 2 : Tracks slots each of terms elements
# Note: slot, and block mean the same thing.
# Block is the internal tracking deque, slot is the final output
from collections import deque
def slots(data, terms):
block = deque()
for datum in data :
block.append(datum)
if len(block) > terms : block.popleft()
if len(block) == terms :
yield block
assert expected == \
tuple(sum(slot)/terms for slot in slots(data, terms))
# Method 3 : Reads value one at a time, computes the sums and throws away read values
def moving_average((avgs, sums),val):
sums = tuple((sum + val) for sum in sums)
return (avgs + ((sums[0] / terms),), sums[1:] + (val,))
assert expected == reduce(
moving_average,
tuple(data[terms-1:]),
((),tuple(sum(data[i:terms-1]) for i in range(terms-1))))[0]
# Method 4 : Semantically same as method 3, intentionally obfuscates just to fit in a lambda
assert expected == \
reduce(
lambda (avgs, sums),val: tuple((avgs + ((nsum[0] / terms),), nsum[1:] + (val,)) \
for nsum in (tuple((sum + val) for sum in sums),))[0], \
tuple(data[terms-1:]),
((),tuple(sum(data[i:terms-1]) for i in range(terms-1))))[0]
재귀 솔루션을 찾고있는 것 같습니다. 이 경우 문제를 약간 변경하고 해결책으로 (4.75, 5.0, 6.0, 7.25, 8.0, 8.25, 6.5, 0.0, 0.0, 0.0)을 목표로 삼을 것을 제안합니다.
이 경우 Scala에서 아래의 우아한 재귀 솔루션을 작성할 수 있습니다.
def mavg(values: List[Double], period: Int): List[Double] = {
if (values.size < period) List.fill(values.size)(0.0) else
if (values.size == period) (values.sum / values.size) :: List.fill(period - 1)(0.0) else {
val rest: List[Double] = mavg(values.tail, period)
(rest.head + ((values.head - values(period))/period)):: rest
}
}
파티에 늦고 함수형 프로그래밍도 처음 접했기 때문에 내부 함수로이 솔루션을 찾았습니다.
def slidingAvg (ixs: List [Double], len: Int) = {
val dxs = ixs.map (_ / len)
val start = (0.0 /: dxs.take (len)) (_ + _)
val head = List.make (len - 1, 0.0)
def addAndSub (sofar: Double, from: Int, to: Int) : List [Double] =
if (to >= dxs.length) Nil else {
val current = sofar - dxs (from) + dxs (to)
current :: addAndSub (current, from + 1, to + 1)
}
head ::: start :: addAndSub (start, 0, len)
}
val xs = List(2, 4, 7, 6, 3, 8, 12, 9, 4, 1)
slidingAvg (xs.map (1.0 * _), 4)
나는 전체 목록을 마침표 (len)로 미리 나누는 아이디어를 채택했습니다. 그런 다음 len-first-elements에 대해 시작할 합계를 생성합니다. 그리고 첫 번째 잘못된 요소 (0.0, 0.0, ...)를 생성합니다.
그런 다음 재귀 적으로 첫 번째 값을 빼고 마지막 값을 더합니다. 결국 나는 모든 것을 나열합니다.
Haskell 의사 코드에서 :
group4 (a:b:c:d:xs) = [a,b,c,d] : group4 (b:c:d:xs)
group4 _ = []
avg4 xs = sum xs / 4
running4avg nums = (map avg4 (group4 nums))
또는 무점
runnig4avg = map avg4 . group4
(이제 4 개를 추상화해야합니다 ...)
Haskell 사용 :
movingAverage :: Int -> [Double] -> [Double]
movingAverage n xs = catMaybes . (fmap avg . take n) . tails $ xs
where avg list = case (length list == n) -> Just . (/ (fromIntegral n)) . (foldl (+) 0) $ list
_ -> Nothing
핵심은 결과의 n 번째 요소에 첫 번째 n-1 요소가 누락 된 속성을 사용하여 목록을 원래 목록의 복사본 목록에 매핑하는 tails 함수입니다.
그래서
[1,2,3,4,5] -> [[1,2,3,4,5], [2,3,4,5], [3,4,5], [4,5], [5], []]
We apply fmap (avg . take n) to the result, which means we take the n-length prefix from the sublist, and compute its avg. If the length of the list we are avg'ing is not n, then we do not compute the average (since it is undefined). In that case, we return Nothing. If it is, we do, and wrap it in "Just". Finally, we run "catMaybes" on the result of fmap (avg . take n), to get rid of the Maybe type.
I was (surprised and) disappointed by the performance of what seemed to me the most idiomatic Clojure solutions, @JamesCunningham 's lazy-seq solutions.
(def integers (iterate inc 0))
(def coll (take 10000 integers))
(def n 1000)
(time (doall (moving-average-james-1 coll n)))
# "Elapsed time: 3022.862 msecs"
(time (doall (moving-average-james-2 coll n)))
# "Elapsed time: 3433.988 msecs"
So here's a combination of James' solution with @DanielC.Sobral 's idea of adapting fast-exponentiation to moving sums :
(defn moving-average
[coll n]
(letfn [(moving-sum [coll n]
(lazy-seq
(cond
(= n 1) coll
(= n 2) (map + coll (rest coll))
(odd? n) (map + coll (moving-sum (rest coll) (dec n)))
:else (let [half (quot n 2)
hcol (moving-sum coll half)]
(map + hcol (drop half hcol))))))]
(cond
(< n 1) nil
(= n 1) coll
:else (map #(/ % n) (moving-sum coll n)))))
(time (doall (moving-average coll n)))
# "Elapsed time: 42.034 msecs"
Edit: this one -based on @mikera 's solution- is even faster.
(defn moving-average
[coll n]
(cond
(< n 1) nil
(= n 1) coll
:else (let [sums (reductions + 0 coll)]
(map #(/ (- %1 %2) n) (drop n sums) sums))))
(time (doall (moving-average coll n)))
# "Elapsed time: 9.184 msecs"
ReferenceURL : https://stackoverflow.com/questions/1319891/calculating-the-moving-average-of-a-list
'developer tip' 카테고리의 다른 글
| .NET-반영된 PropertyInfo의 기본값 가져 오기 (0) | 2020.12.27 |
|---|---|
| C #에서 쿼리 문자열을 사전으로 변환하는 가장 좋은 방법 (0) | 2020.12.27 |
| Android : SlidingDrawer의 높이를 wrap_content로 설정할 수 있습니까? (0) | 2020.12.27 |
| Linux에서 MongoDB를 가져와 원격 연결 수신 (0) | 2020.12.27 |
| .NET의 문자열 끝에서 문자열 자르기-이것이 누락 된 이유는 무엇입니까? (0) | 2020.12.27 |