Среднее значение с использованием складки

Как мне вычислить среднее значение списка чисел с помощью карты и сокращения.

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

Скелетная попытка LISP:

(defun average (list)
  (reduce ... list))

Скелетная попытка JS:

function average (array) {
  return array.reduce(function() {
    ..
  }, 0);
}

Если вы опубликуете ответ с реальным кодом на каком-либо языке, объясните это так, как будто я новичок в этом языке (что, вероятно, так и будет).

Я хочу избежать банального ответа

function average (array) {
   return sum(array) / array.length;
}

Это использует деление в конце, а не оператор сокращения. Считаю это «обманом».

[[Изменить]]

Решил свою проблему. Если у кого-то есть элегантное решение с использованием синтаксического сахара из LISP или Haskell, мне было бы интересно.


average functional-programming language-agnostic
person Raynos    schedule 12.05.2011    source источник
comment
Возможно, лучше подходит для CodeGolf.SE?   -  person ircmaxell    schedule 13.05.2011
comment
Простой reduce он же fold не mapreduce (как в фреймворке Google). Даже если вы map вводите заранее.   -  person    schedule 13.05.2011
comment
@delnan, извини, я запуталась в терминологии.   -  person Raynos    schedule 13.05.2011
comment
Первым шагом должна стать математическая обработка решения. Можете ли вы придумать итеративный алгоритм, который даст вам то, что вы хотите? Превратить это в fold не должно быть слишком сложно.   -  person abesto    schedule 13.05.2011
comment
@abesto теперь решение кажется таким простым. Я не думал "спасибо".   -  person Raynos    schedule 13.05.2011

Ответы (5)


arrow_upward
1
arrow_downward

Вот общая версия lisp:

(defun running-avg (r v)
  (let* ((avg (car r))
         (weight (cdr r))
         (new-weight (1+ weight)))
    (cons (/ (+ (* avg weight) v) new-weight) new-weight)))

(car (reduce 'running-avg '(3 6 5 7 9) :initial-value '(0 . 0)))
;; evaluates to 6

Он отслеживает текущее среднее значение и вес и вычисляет новое среднее значение как ((previous average * weight) + new value).

person ataylor    schedule 12.05.2011
comment
не могли бы вы объяснить 1+ и weight. Я ничего не знаю о LISP. Также * (car r) (cdr r) Является ли r кортеж? - person Raynos; 13.05.2011
comment
1+ - это функция, которая добавляет 1 к аргументу. weight - это просто имя локальной переменной. Да, r - кортеж; Я немного очистил его, придумав несколько значимых имен. - person ataylor; 13.05.2011
comment
Разумно очевидно, что :initial-value делает, но не могли бы вы объяснить семантику этого синтаксиса? - person Raynos; 13.05.2011
comment
Это необязательный аргумент ключевого слова для reduce. Функции Common Lisp могут принимать именованные аргументы, где имя является символом Lisp. Двоеточие в начале - это просто синтаксис Lisp для символов. При начальном значении при первом вызове функции используется (initial-value, element0) вместо (element0, element1). - person ataylor; 13.05.2011
comment
Теперь, когда я понял код, я предпочитаю исходную версию, потому что в ней есть классическая лаконичность LISP :) - person Raynos; 13.05.2011

arrow_upward
3
arrow_downward

Как упоминал @abesto, для этого требуется итеративный алгоритм.

Let counter be 0 
For each [value, index] in list   
  let sum be (counter * index) + value   
  let counter be sum / (index + 1)

return counter

Реализация javascript будет

var average = function(list) { 
    // returns counter
    return list.reduce(function(memo, val, key) {
         // memo is counter
         // memo * key + val is sum. sum / index is counter, counter is returned
         return ((memo * key) + val) / (key + 1)
    // let counter be 0
    }, 0);  
}
person Raynos    schedule 12.05.2011

arrow_upward
2
arrow_downward

вычислить среднее значение списка чисел с помощью карты и уменьшить

Не требуется map. Просто разверните, чтобы сгенерировать список, и сверните, чтобы уменьшить его до среднего значения:

mean n m = uncurry (/) . foldr g (0, 0) . unfoldr f $ n
      where 
        f b | b > m     = Nothing
            | otherwise = Just (b, b+1)

        g x (s,n) = (s+x, n+1)

Эффективная реализация

Эта структура (fold . unfold) позволяет выполнять оптимизацию слияния. Особенно эффективная реализация объединит разворачивание (создание списка) со сворачиванием (сокращение списка). Здесь, в Haskell, GHC объединяет две фазы (разворачивание == enumFromN) и сворачивание посредством слияния потоков:

import Data.Vector.Unboxed 

data Pair = Pair !Int !Double

mean :: Vector Double -> Double
mean xs = s / fromIntegral n
  where
    Pair n s       = foldl' k (Pair 0 0) xs
    k (Pair n s) x = Pair (n+1) (s+x)

main = print (mean $ enumFromN 1 (10^7))

Что компилятор преобразует из композиции двух функций в рекурсивный цикл:

main_loop a d e n =
    case ># a 0 of 
      False -> (# I# n, D# e #);
      True -> main_loop (-# a 1) (+## d 1.0) (+## e d) (+# n 1)

что сводится к этому goto в сборке (бэкэнд C для компилятора):

Main_mainzuzdszdwfoldlMzqzuloop_info:
        leaq    32(%r12), %rax
        cmpq    %rax, 144(%r13)
        movq    %r12, %rdx
        movq    %rax, %r12
        jb      .L198
        testq   %r14, %r14
        jle     .L202
.L199:
        movapd  %xmm5, %xmm0
        leaq    -1(%r14), %r14
        movsd   .LC0(%rip), %xmm5
        addq    $1, %rsi
        addsd   %xmm0, %xmm6
        movq    %rdx, %r12
        addsd   %xmm0, %xmm5
        jmp     Main_mainzuzdszdwfoldlMzqzuloop_info

LLVM дает более эффективные, но более запутанные реализации (примерно в 2 раза быстрее).

Ссылки: Вычисление среднего значения список эффективно на Haskell

person Don Stewart    schedule 12.05.2011

arrow_upward
0
arrow_downward

Описание аппорача в Haskell, который позволяет использовать композиционный подход к сверткам: http://conal.net/blog/posts/another-lovely-example-of-type-class-morphisms/

person sclv    schedule 12.05.2011
comment
Эта статья что-то значила бы, если бы я пошел на курс Haskell для начинающих. - person Raynos; 13.05.2011
comment
Связанный красивый складной столб несколько более доступен. - person sclv; 13.05.2011

arrow_upward
0
arrow_downward

В системе Mathematica

mean[l_List]:=
    Fold[{First@#1+1,(#2 +#1[[2]](First@#1-1))/First@#1}&,{1,1},l][[2]]  

In[23]:= mean[{a,b,c}]
Out[23]= 1/3 (a+b+c)
person Dr. belisarius    schedule 13.05.2011