Moving average clojure

Este fim de semana eu decidi tentar minha mão em alguns Scala e Clojure. Eu proficiente com a programação orientada a objetos, e assim Scala foi fácil de escolher como uma linguagem, mas queria experimentar a programação funcional. Foi aí que ficou difícil. Eu simplesmente não consigo entender minha cabeça em um modo de funções de escrita. Como um programador funcional especialista, como você aborda um problema. Dada uma lista de valores e um período de soma definido, como você geraria uma nova lista da média móvel simples da lista. Por exemplo: Dado os valores da lista (2.0, 4.0 , 7.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0) e o período 4, a função deve retornar: (0.0, 0.0, 0.0, 4.75, 5.0, 6.0, 7.25, 8.0, 8.25, 6.5) Depois Passando um dia refletindo, o melhor que poderia surgir em Scala era o seguinte: eu sei que isso é horrivelmente ineficiente. Eu prefiro fazer algo como: Agora, isso seria facilmente feito em um estilo imperativo, mas eu não posso para a vida De mim, descobrir como expressar isso funcionalmente. Problema interessante. Posso pensar em muitas soluções, com vários graus de eficiência. Ter que adicionar coisas repetidamente não é realmente um problema de desempenho, mas vamos assumir que é. Além disso, os zeros no início podem ser antecipados mais tarde, então não nos preocupemos em produzi-los. Se o algoritmo fornece-los naturalmente, bem se não, corrigimos isso mais tarde. Começando com Scala 2.8, o seguinte daria o resultado para o período n gt usando o deslizamento para obter uma janela deslizante da Lista: No entanto, embora isso seja bastante elegante, ele não possui o melhor desempenho possível, porque não aproveita já Adições calculadas. Então, falando sobre eles, como podemos fazê-lo. Digamos que escrevemos isso: Temos uma lista da soma de cada dois pares. Vamos tentar usar esse resultado para calcular a média móvel de 4 elementos. A fórmula acima fez a seguinte computação: Então, se tomarmos cada elemento e adicioná-lo ao segundo próximo elemento, obtemos a média móvel para 4 elementos: podemos fazê-lo assim: podemos calcular a média móvel para 8 elementos, e assim por diante. Bem, existe um algoritmo bem conhecido para calcular coisas que seguem esse padrão. É mais conhecido por seu uso na computação do poder de um número. Isso é assim: então, apliquemos aqui: então, a lógica é verdadeira. O período 0 é inválido, o período 1 é igual à entrada, o período 2 é uma janela deslizante de tamanho 2. Se for maior que isso, pode ser igual ou impar. Se for estranho, adicionamos cada elemento ao movimentoSum dos próximos elementos (ímpares - 1). Por exemplo, se 3, adicionamos cada elemento ao MoveSum dos próximos 2 elementos. Se mesmo, calculamos o MoveSum para n 2. depois adicione cada elemento ao n 2 passos depois. Com essa definição, podemos voltar ao problema e fazer isso: há uma ligeira ineficiência em relação ao uso de. Mas é O (período), não O (valores. size). Pode ser mais eficiente com uma função recursiva da cauda. E, é claro, a definição de deslizamento que forneci é horrível desempenho-sábio, mas haverá uma definição muito melhor sobre isso na Scala 2.8. Observe que não podemos fazer um método de deslizamento eficiente em uma Lista. Mas podemos fazê-lo em um Iterable. Dito tudo isso, Id vai com a primeira definição e otimize apenas se uma análise de caminho crítico identificou isso como um grande negócio. Para concluir, considere como eu enfrentei o problema. Temos um problema médio móvel. Uma média móvel é a soma de uma janela em movimento em uma lista, dividida pelo tamanho dessa janela. Então, primeiro, tento obter uma janela deslizante, somar tudo sobre isso, e depois dividir pelo tamanho. O próximo problema foi evitar a repetição de adições já computadas. Nesse caso, eu fui a menor adição possível e tentei descobrir como calcular somas maiores reutilizando tais resultados. Finalmente, vamos tentar resolver o problema do jeito que você achou, adicionando e subtraindo o resultado anterior. Obter a primeira média é fácil: agora fazemos duas listas. Primeiro, a lista de elementos a serem subtraídos. Em seguida, a lista de elementos a serem adicionados: podemos adicionar essas duas listas usando zip. Este método só produzirá tantos elementos quanto a menor lista, o que evita o problema de subtrair sendo maior do que o necessário: terminamos compondo o resultado com uma dobra: qual é a resposta a ser retornada. Toda a função parece assim: eu conheço Clojure melhor do que Scala, então aqui vai. Ao escrever isso, a outra entrada de Clojure aqui é imperativa, não é realmente o que você está procurando (e não é Clojuure idiomático). O primeiro algoritmo que vem à minha mente é tomar repetidamente o número de elementos solicitados da seqüência, descartando o primeiro elemento e recorrente. O seguinte funciona em qualquer tipo de sequência (vetor ou lista, preguiçoso ou não) e dá uma sequência preguiçosa de médias --- o que pode ser útil se você estiver trabalhando em uma lista de tamanho indefinido. Observe que ele cuida do caso base, retornando nulo implícitamente se não houver elementos suficientes na lista para consumir. Executando isso em seus rendimentos de dados de teste. Não dá 0 para os primeiros elementos na seqüência, embora isso poderia ser facilmente manipulado (um pouco artificialmente). A coisa mais fácil de tudo é ver o padrão e ser capaz de lembrar uma função disponível que corresponda à conta. A partição dá uma visão preguiçosa de porções de uma seqüência, que podemos então mapear: Alguém perguntou por uma versão recursiva da cauda, ​​a recursão da cauda versus a preguiça é um pouco de compensação. Quando seu trabalho está construindo uma lista, então, tornar a sua função cauda recursiva geralmente é bastante simples, e isso não é exceção - basta criar a lista como um argumento para uma subfunção. Bem, acumule-se em um vetor em vez de uma lista porque, de outra forma, a lista será construída para trás e precisará ser revertida no final. O loop é uma maneira de criar uma função interna anônima (tipo de Esquemas, nomeado como chamado), deve ser usado em Clojure para eliminar chamadas de cauda. Conj é um fato generalizado. Acrescentando da maneira natural para a coleta --- o início das listas eo final dos vetores. Respondeu 24 de agosto às 2:58 I39ve decidiu adicionar a este antigo Q, porque o tópico surgiu novamente (stackoverflowquestions2359821hellip) e acho preferível apontar para esta linda coleção de possíveis soluções ao adicionar minha própria tomada (o que é diferente de Versões anteriores em Clojure, como explicado na A). Talvez possamos construir o repositório mais completo das implementações mov-avg funcionais da Web39 -) ndash Micha Marczyk 2 de março 10 às 0:20 Heres uma solução Haskell de uma linha parcialmente sem pontos: primeiro aplica as colas à lista para obter as listas das caudas , Então: Inverte e cai as primeiras entradas p (tomando p como 2 aqui): Caso você não esteja familiarizado com o símbolo (.) Dotnipple, é o operador para composição funcional, o que significa que passa a saída de uma função como a Entrada de outro, compondo-os em uma única função. (G. F) significa executar f em um valor, em seguida, passar a saída para g, então ((f. G) x) é o mesmo que (g (f x)). Geralmente, seu uso leva a um estilo de programação mais claro. Em seguida, mapeia a função (((deIntegral p)). Soma. Pegue p) na lista. Então, para cada lista na lista, são necessários os primeiros elementos p, somá-los e, em seguida, divide-os por p. Então, basta virar a lista novamente com o reverso. Tudo isso parece muito mais ineficiente do que o inverso não reverte fisicamente a ordem de uma lista até que a lista seja avaliada, ela apenas a coloca na pilha (boa e voraz Haskell). As caudas também não criam todas essas listas separadas, ele apenas faz referência a diferentes seções da lista original. Ainda não é uma ótima solução, mas é uma linha longa :) Essa é uma solução ligeiramente mais agradável, mas mais longa, que usa mapAccum para fazer uma subtração deslizante e adição: Primeiro dividimos a lista em duas partes em p, então: Soma o primeiro bit: Codifique o segundo bit com a lista original (isso apenas faz o par de itens a partir das duas listas). A lista original é, obviamente, mais longa, mas perdemos esse bit extra: agora definimos uma função para o nosso mapAccum (ulator). MapAccumL é o mesmo que o mapa, mas com um parâmetro de acumulação de estado de execução extra, que é passado do mapeamento anterior para o próximo como o mapa é executado através da lista. Usamos o acumulador como nossa média móvel, e como nossa lista é formada pelo elemento que acabou de sair da janela deslizante e do elemento que acabou de entrar (a lista que acabamos de fechar), nossa função deslizante tira o primeiro número x de A média e adiciona o segundo número y. Em seguida, passamos o novo s ao longo e retornamos s divididos por p. Snd (segundo) apenas leva o segundo membro de um par (tupla), que é usado para obter o segundo valor de retorno do mapAccumL, pois mapAccumL retornará o acumulador, bem como a lista mapeada. Para aqueles que não conhecem o símbolo. É o operador da aplicação. Ele realmente não faz nada além de ter uma prioridade de ligação baixa e associativa direita, então significa que você pode deixar de lado os colchetes (pegue nota LISPers), ou seja, (fx) é o mesmo que fx Running (ma 4 2.0, 4.0, 7,0, 6,0, 3,0, 8,0, 12,0, 9,0, 4,0, 1,0) produz 4,75, 5,0, 6,0, 7,25, 8,0, 8,25, 6,5 para qualquer das soluções. Ah, e você precisará importar o módulo List para compilar qualquer uma das soluções. Daniel Obrigado Escrever o código é muito mais fácil do que explicá-lo -) Você descreveu a essência disso. Duas ListasStreams são mantidas em ambas as funções e pega seu quotheadsquot retirado durante cada iteração. One ListStream serve como a coleção principal para iterar, enquanto o outro ListStream, que é a mesma coleção, exceto que quotperiodquot, menos duplas retirados, é usado no cálculo da nova média móvel. Ndash Walter Chang 24 de agosto 09 às 17:19 A linguagem de programação J facilita programas como a média móvel. Na verdade, há menos caracteres em () do que em seu rótulo, média móvel. Para os valores especificados nesta questão (incluindo os valores do nome), aqui é uma maneira direta de codificar isso: podemos descrever isso usando rótulos para componentes. Ambos os exemplos usam exatamente o mesmo programa. A única diferença é o uso de mais nomes na segunda forma. Esses nomes podem ajudar os leitores que não conhecem as primárias J. Vamos olhar um pouco mais para o que está acontecendo no subprograma, a média. Denota soma () e denota divisão (como o sinal clássico). O cálculo de uma contagem (contagem) de itens é feito por. O programa geral, então, é a soma dos valores divididos pelo valor dos valores: o resultado do cálculo da média móvel aqui escrito não inclui os zeros iniciais esperados na pergunta original. Esses zeros são indiscutivelmente não fazem parte do cálculo pretendido. A técnica usada aqui é chamada de programação tácita. É praticamente o mesmo que o estilo sem pontos de programação funcional. Respondeu 26 de agosto 10 às 16:15 Aqui está Clojure fingindo ser uma linguagem mais funcional. Isso é totalmente recursivo, btw, e inclui zeros de liderança. Geralmente eu coloco a coleção ou o último parâmetro da lista para tornar a função mais fácil de curry. Mas em Clojure. É tão complicado, geralmente acabo fazendo isso. Nesse caso, realmente não importa qual é a ordem dos parâmetros. Respondeu 24 de agosto 09 às 4:56 Oi Jonathan, eu sou muito novo para esta programação funcional, você poderia explicar-me como isso é recursivo de cauda Obrigado ndash James P 24 de agosto 09 às 14:38 A recursão ocorre na declaração if, Onde qualquer opção é baseada em recorrer. Isso irá calcular todos os parâmetros primeiro, e apenas depois recurse. A resposta será o resultado de recorrer. Como o resultado é o mesmo resultado retornado pela recursão, sem outros cálculos, isso é recursivo da cauda. Ndash Daniel C. Sobral 24 de agosto 09 às 15:20 Este exemplo faz uso do estado, uma vez que para mim é uma solução pragmática neste caso e um fechamento para criar a função de média de janelas: ainda é funcional no sentido de fazer uso De funções de primeira classe, embora não seja livre de efeitos colaterais. Os dois idiomas que você mencionou ambos são executados em cima da JVM e, portanto, ambos permitem gerenciamento de estado quando necessário. Respondeu 24 de agosto 09 às 1:55 Esta solução está em Haskell, que é mais familiar para mim: respondeu 24 de agosto de 09 às 10:23 Eu gosto do uso da declaração da partida. Tentei fazer algo parecido, mas não consegui muito fazer isso até lá. Ndash James P 24 de agosto de 09 às 14:39 Uma breve versão Clojure que tem a vantagem de ser O (comprimento da lista), independentemente do seu período: isso explora o fato de que você pode calcular a soma de uma variedade de números criando uma soma cumulativa Da sequência (por exemplo, 1 2 3 4 5 - 0 1 3 6 10 15) e depois subtrair os dois números com um deslocamento igual ao seu período. Estando atrasado na festa e a programação nova para a funcionalidade também, cheguei a esta solução com uma função interna: adotei a ideia, para dividir toda a lista pelo período (len) antecipadamente. Então eu gerar a soma para começar com o len-first-elements. E ganho os primeiros elementos inválidos (0.0, 0.0.). Então, recursivamente, resumo o primeiro e adicione o último valor. No final, sinto-me lisonjeado. Respondeu 29 de abril 10 às 19:28 No pseudocódigo de Haskell: (Agora um realmente deve abstrair o 4 para fora.) Respondeu Jul 23 13 às 13:45 A chave é a função da cauda, ​​que mapeia uma lista para uma lista de cópias do original Lista, com a propriedade de que o n-ésimo elemento do resultado está faltando os primeiros elementos n-1. Nós aplicamos fmap (avg. Take n) ao resultado, o que significa que nós levamos o prefixo n-length da sublista e calculamos seu valor médio. Se o comprimento da lista que somos avging não é n, então não calculamos a média (uma vez que é indefinido). Nesse caso, devolvemos nada. Se for, nós fazemos, e embrulhe-o em Just. Finalmente, corremos o CatMaybes no resultado do fmap (avg. Take n), para livrar-se do tipo Maybe. Respondeu 21 de outubro 13 às 1:29 Fiquei (surpreso e) desapontado com o desempenho do que me pareceu as soluções de Clojure mais idiomáticas, as soluções de preguiça-seq de JamesCunningham. Então, ela é uma combinação de solução de James com a idéia de DanielC. Sobral de adaptar rápida-exponenciação a somas em movimento: Editar: esta baseada na solução do mikera é ainda mais rápida. Respondeu 22 de julho 13 às 19:21 Sua resposta 2017 Stack Exchange, IncClojure A média móvel de Java para Clojure Clojure tem um clojure. lang. PersistentQueue para trabalhar com filas. Não sei por que não tem uma macro de leitor, mas funciona bem e retorna uma coleção de Clojure que você pode lidar com os contras e as vistas. Você pode começar com uma fila vazia com clojure. lang. PersistentQueueEMPTY ou insira seus itens no construtor. Eu escrevi algum material sobre isso em português se você tiver algum interesse. Em 20072014, às 08:48, Cecil Westerhof escreveu: Eu estava pensando: qual é a melhor maneira de traduzir isso para Clojure No momento Clojure não tem uma fila. Eu deveria usar as chamadas Java, ou há uma maneira melhor - Cecil Westerhof - Você recebeu esta mensagem porque você está inscrito no grupo Google QuotClojurequot. Para enviar a este grupo, envie um email para clojuregooglegroups. Observe que as postagens dos novos membros são moderadas - seja paciente com sua primeira postagem. Para cancelar a inscrição deste grupo, envie um email para clojure unsubscribegooglegroups. Para mais opções, visite este grupo em groups. googlegroupclojurehlen --- Você recebeu esta mensagem porque está inscrito no Grupo Google quotClojurequot. Para cancelar a inscrição deste grupo e parar de receber e-mails dele, envie um email para clojureunsubscribegooglegroups. Para mais opções, visite groups. googledoptout. - Você recebeu esta mensagem porque está inscrito no grupo Grupos do Google QuotClojurequot. Para enviar a este grupo, envie um email para clojuregooglegroups. Observe que as postagens dos novos membros são moderadas - seja paciente com sua primeira postagem. Para cancelar a inscrição deste grupo, envie um email para clojure unsubscribegooglegroups. Para mais opções, visite este grupo em groups. googlegroupclojurehlen --- Você recebeu esta mensagem porque está inscrito no Grupo Google quotClojurequot. Para cancelar a inscrição deste grupo e parar de receber e-mails dele, envie um email para clojureunsubscribegooglegroups. Para mais opções, visite groups. googledoptout. Mike Fikes Existe realmente uma implementação de fila. Aqui está uma maneira de usá-lo para o seu problema: (defn make-moving-average-queue n (atom)) (defn update-moving-average-queue old-queue next-value (let current-total ((: current - Total-idade anterior) next-value) old-values ​​(conj (: old-values ​​old-queue) next-value) (se (gt (count old-values) (: length old-queue)) (deixe o total atual (- atual-total (primeiros valores antigos)) valores antigos Existe realmente uma implementação de fila. Aqui está uma maneira de usá-lo para seu problema: (defn make-moving-average-queue n (atom: current-total 0.0 : Old-values ​​(clojure. lang. PersistentQueueEMPTY))) (defn update-moving-average-queue old-queue next-value (let current-total ((: atual-total old-queue) next-value) old-values (Conj (old-values ​​old-queue) next-value) (se (gt (count old-values) (: length old-queue)) (let current-total (- current-total (first old-values)) Valores antigos (pop-olds) (assoc old-queue: current-total current-total: old-values ​​old-values)) (assoc old-queue: current-total current-total: old-values ​​old-values ))) (Defn moving-average old-queue next-value (deixe a nova fila (swap old-queue update-moving-average-queue next-value) ((: atual-total new-queue) (count (: Old-values ​​new-queue)))) (def queue-06 (make-moving-average-queue 6)) (entradas def-06 20 22 21 24 24 23 25 26 20 24 26 26 25 27 28 27 29 27 25 24) (entradas de entrada de doseq-06 (println (entrada de fila-06 média em movimento)) (def-fila-10 (make-moving-average-queue 10)) (entradas de def-10 20 22 24 25 23 26 28 26 29 27 28 30 27 29 28) (entradas de entrada de doseq-10 (println (entrada de fila média em movimento-10))) - Você recebeu esta mensagem porque está inscrito no grupo QuotClojurequot do Google Groups. Para enviar a este grupo, envie um email para clojuregooglegroups. Observe que as postagens dos novos membros são moderadas - seja paciente com sua primeira postagem. Para cancelar a inscrição deste grupo, envie um email para clojure unsubscribegooglegroups. Para mais opções, visite este grupo em groups. googlegroupclojurehlen --- Você recebeu esta mensagem porque está inscrito no Grupo Google quotClojurequot. Para cancelar a inscrição deste grupo e parar de receber e-mails dele, envie um email para clojureunsubscribegooglegroups. Para mais opções, visite groups. googledoptout. Mike Fikes Hey Cecil, além de usar o peek em vez de primeiro, como indicado por Plinio, a função de média móvel acima usa alguns nomes ruins, em retrospectiva, especialmente o nome do parâmetro quotold-queuequot. Eu sugeri nomear a fila, como se refere a um átomo. Você poderia mesmo considerar nomear a função em movimento-média. - Você recebeu esta mensagem porque está inscrito no grupo Grupos do Google QuotClojurequot. Para enviar a este grupo, envie e-mail para e-mail protegido. Observe que as postagens de novos membros são em 20 de julho de 2014 às 1:52 pm Além do uso de peek em vez de primeiro, conforme indicado por Plinio, a função de média móvel acima usa alguns Nomes ruins, em retrospectiva, especialmente o nome do parâmetro quotold-queuequot. Eu sugeri nomear a fila, como se refere a um átomo. Você poderia mesmo considerar nomear a função em movimento-média. - Você recebeu esta mensagem porque está inscrito no grupo Grupos do Google QuotClojurequot. Para enviar a este grupo, envie um email para clojuregooglegroups. Observe que as postagens dos novos membros são moderadas - seja paciente com sua primeira postagem. Para cancelar a inscrição deste grupo, envie um email para clojure unsubscribegooglegroups. Para mais opções, visite este grupo em groups. googlegroupclojurehlen --- Você recebeu esta mensagem porque está inscrito no Grupo Google quotClojurequot. Para cancelar a inscrição deste grupo e parar de receber e-mails dele, envie um email para clojureunsubscribegooglegroups. Para mais opções, visite groups. googledoptout. Jony Hudson Provavelmente não é a resposta que você está procurando, mas a média móvel ponderada exponencialmente não requer qualquer outro estado que não seja o valor atual: (defn ewma alpha (fn avg novo ((((1 alpha) avg) (alfa novo))) ) Jony - Você recebeu esta mensagem porque está inscrito no grupo Grupos QuotClojurequot do Google Groups. Para postar neste grupo, envie e-mail para email protegido. Observe que as postagens de novos membros são moderadas - seja paciente com sua primeira postagem. Para cancelar a assinatura deste grupo, envie No domingo, 20 de julho de 2014 às 12:48:19 UTC1, Cecil Westerhof escreveu: ou há uma maneira melhor. Provavelmente não é a resposta que você procura, mas a média móvel ponderada exponencial não requer nenhum outro estado Do que o valor atual: (defn ewma alpha (fn avg novo ((((1 alfa) avg) (alfa novo)))) - Você recebeu esta mensagem porque está inscrito no Grupo Google quotClojurequot. Para enviar a este grupo, envie um email para clojuregooglegroups. Observe que as postagens dos novos membros são moderadas - seja paciente com sua primeira postagem. Para cancelar a inscrição deste grupo, envie um email para clojure unsubscribegooglegroups. Para mais opções, visite este grupo em groups. googlegroupclojurehlen --- Você recebeu esta mensagem porque está inscrito no Grupo Google quotClojurequot. Para cancelar a inscrição deste grupo e parar de receber e-mails dele, envie um email para clojureunsubscribegooglegroups. Para mais opções, visite groups. googledoptout.