Weighted moving average c

Eu estou tentando calcular a média móvel de um sinal. O valor do sinal (um duplo) é atualizado em tempos aleatórios. Eu estou procurando uma maneira eficiente de calcular sua média ponderada de tempo ao longo de uma janela de tempo, em tempo real. Eu poderia fazer isso sozinho, mas é mais desafiador do que eu pensava. A maioria dos recursos que encontrei pela internet está calculando a média móvel do sinal periódico, mas atualizo as minhas em tempo aleatório. Alguém sabe bons recursos para isso O truque é o seguinte: Você recebe atualizações em horários aleatórios via void update (int time, float value). No entanto, você também precisa rastrear quando uma atualização cai da janela de tempo, para que você defina um alarme que é chamado na hora N, o que impede que a atualização anterior seja considerada novamente no cálculo. Se isso acontecer em tempo real, você pode solicitar que o sistema operacional faça uma chamada para um método void dropoffoldestupdate (int time) a ser chamado na hora N Se for uma simulação, você não poderá obter ajuda do sistema operacional e precisará faça isso manualmente. Em uma simulação, você chamaria métodos com o tempo fornecido como um argumento (que não se correlaciona com o tempo real). No entanto, uma suposição razoável é que as chamadas têm a garantia de que os argumentos de tempo estão aumentando. Nesse caso, você precisa manter uma lista ordenada de valores de hora do alarme e, para cada chamada de atualização e leitura, você verifica se o argumento de hora é maior que o da lista de alarmes. Embora seja maior o processamento relacionado ao alarme (desative a atualização mais antiga), remova a cabeça e verifique novamente até que todos os alarmes anteriores ao tempo determinado sejam processados. Então faça a chamada de atualização. Eu até agora assumi que é óbvio o que você faria para o cálculo real, mas vou elaborar apenas no caso. Eu suponho que você tenha um método float read (int time) que você usa para ler os valores. O objetivo é tornar essa chamada o mais eficiente possível. Portanto, você não calcula a média móvel toda vez que o método de leitura é chamado. Em vez disso, você pré-calcula o valor a partir da última atualização ou do último alarme e ajusta esse valor por algumas operações de ponto flutuante para considerar a passagem do tempo desde a última atualização. (isto é, um número constante de operações, exceto para talvez processar uma lista de alarmes empilhados). Espero que isso esteja claro - este deve ser um algoritmo bastante simples e bastante eficiente. Otimização adicional. Um dos problemas remanescentes é se um grande número de atualizações acontecer dentro da janela de tempo, então há um longo tempo para o qual não há leituras nem atualizações, e então uma leitura ou atualização aparece. Nesse caso, o algoritmo acima será ineficiente para atualizar incrementalmente o valor de cada uma das atualizações que está caindo. Isso não é necessário porque apenas nos preocupamos com a última atualização além da janela de tempo, portanto, se houver uma maneira de descartar todas as atualizações mais antigas, isso ajudará. Para fazer isso, podemos modificar o algoritmo para fazer uma pesquisa binária de atualizações para encontrar a atualização mais recente antes da janela de tempo. Se houver relativamente poucas atualizações que precisem ser descartadas, é possível atualizar incrementalmente o valor de cada atualização descartada. Mas, se houver muitas atualizações que precisem ser descartadas, será possível recomputar o valor desde o início, depois de deixar as atualizações antigas. Apêndice sobre Computação Incremental: Eu deveria esclarecer o que quero dizer com cálculo incremental acima na sentença ajustar este valor por um par de operações de ponto flutuante para explicar a passagem do tempo desde a última atualização. Cálculo inicial não-incremental: em seguida, iterar sobre as atualizações relevantes em ordem crescente de tempo: movingaverage (soma lastupdate timesincelastupdate) / windowlength. Agora, se exatamente uma atualização cair fora da janela, mas nenhuma nova atualização chegar, ajuste a soma como: (observe que é previousupdate que tem seu registro de data e hora modificado para iniciar o último início da janela). E se exatamente uma atualização entrar na janela, mas nenhuma nova atualização cair, ajuste a soma como: Como deve ser óbvio, este é um esboço, mas mostra como você pode manter a média de modo que seja O (1) operações por atualização em uma base amortizada. Mas observe a otimização adicional no parágrafo anterior. Observe também os problemas de estabilidade aludidos em uma resposta mais antiga, o que significa que os erros de ponto flutuante podem se acumular em um grande número dessas operações incrementais, de modo que haja uma divergência em relação ao resultado da computação completa que é significativa para o aplicativo. Se uma aproximação estiver correta e houver um tempo mínimo entre as amostras, você poderá tentar super-amostragem. Ter uma matriz que represente intervalos de tempo espaçados uniformemente menores que o mínimo e, a cada período de tempo, armazene a amostra mais recente que foi recebida. Quanto menor o intervalo, mais próxima a média será do valor real. O período não deve ser maior do que a metade do mínimo ou há uma chance de perder uma amostra. respondido Dez 15 11 at 18:12 respondido Dez 15 11 at 22:38 Obrigado pela resposta. Uma melhoria que seria necessária para realmente citar o valor da média total, de modo que não fiquemos em loop o tempo todo. Além disso, pode ser um ponto de menor importância, mas não seria mais eficiente usar um deque ou uma lista para armazenar o valor, uma vez que assumimos que a atualização virá na ordem correta. A inserção seria mais rápida do que no mapa. ndash Arthur Dec 16 11 at 8:55 Sim, você poderia armazenar em cache o valor da soma. Subtraia os valores das amostras que você apagar, adicione os valores das amostras inseridas. Além disso, sim, um dequeltpairltSample, Dategtgt pode ser mais eficiente. Eu escolhi o mapa para facilitar a leitura e a facilidade de invocar o map :: upperbound. Como sempre, escreva primeiro o código correto, depois faça o perfil e meça as alterações incrementais. ndash Rob Dez 16 11 às 15:00 Nota: Aparentemente, esta não é a maneira de abordar isso. Deixá-lo aqui para referência sobre o que está errado com essa abordagem. Confira os comentários. ATUALIZADO - baseado no comentário de Olis. Não tenho certeza sobre a instabilidade que ele está falando embora. Use um mapa ordenado dos tempos de chegada em relação aos valores. Após a chegada de um valor, adicione o horário de chegada ao mapa ordenado junto com seu valor e atualize a média móvel. aviso isso é pseudo-código: lá. Não totalmente elaborado, mas você entendeu. Coisas a notar. Como eu disse acima, é o pseudo código. Você precisará escolher um mapa apropriado. Não remova os pares enquanto faz a iteração, pois você invalidará o iterador e terá que começar novamente. Veja o comentário de Olis abaixo também. O que não funciona? Não leva em conta a proporção do tamanho da janela para a qual cada valor existe. Além disso, essa abordagem de adição e subtração é apenas estável para tipos inteiros, não flutuantes. Oliver Charlesworth Dez 15 11 at 12:29 OliCharlesworth - desculpe, eu perdi alguns pontos-chave na descrição (dupla e ponderada no tempo). Vou atualizar. Obrigado. ndash Dennis Dez 15 11 at 12:33 A ponderação de tempo é outro problema. Mas isso não é do que estou falando. Eu estava me referindo ao fato de que quando um novo valor entra pela primeira vez na janela de tempo, sua contribuição para a média é mínima. Sua contribuição continua aumentando até que um novo valor entre. A média ponderada de média móvel é uma média de dados calculada ao longo de um período de tempo, em que o peso maior é anexado aos dados mais recentes. A Média Móvel Ponderada pode ser usada com qualquer preço, incluindo o preço Hi, Low, Open ou Close, e também pode ser aplicada a outros indicadores. A Média Móvel Ponderada suaviza uma série de dados, o que é importante em um mercado volátil, pois ajuda a identificar tendências com muito mais facilidade. A ponderação é calculada a partir de uma soma de dias. O Dundas Chart para Windows Forms possui quatro tipos de médias móveis, incluindo Simple. Exponencial. Triangular. e ponderada. A diferença mais importante entre as médias móveis acima é como elas pesam seus pontos de dados. Recomendamos que você leia Usando fórmulas financeiras antes de prosseguir. O uso de fórmulas financeiras fornece uma explicação detalhada sobre como usar fórmulas e também explica as várias opções disponíveis ao aplicar uma fórmula. Um gráfico de linhas é uma boa opção ao exibir uma média móvel ponderada. Interpretação Financeira: A Média Móvel Ponderada é usada para comparar um valor com sua Média Móvel Ponderada, e dá mais influência para dados recentes e menos influência para dados passados. O elemento mais importante usado no cálculo da média móvel é um período de tempo, que deve ser igual ao ciclo de mercado observado. A média móvel ponderada é um indicador atrasado e estará sempre atrás do preço. Quando o preço segue uma tendência, a média móvel ponderada é muito próxima do preço. Quando um preço está aumentando, a média móvel ponderada provavelmente ficará inativa devido à influência dos dados históricos. Cálculo: A média móvel ponderada é calculada usando uma soma de índices de períodos de tempo (pontos de dados). O peso para cada período é calculado como índice / (Número de pontos de dados). A tabela a seguir demonstra como calcular uma média móvel ponderada de 5 dias: Eu sei que isso é possível com o aumento de acordo com: Mas eu realmente gostaria de evitar o uso de boost. Eu pesquisei e não encontrei nenhum exemplo adequado ou legível. Basicamente, quero rastrear a média móvel de um fluxo contínuo de um fluxo de números de ponto flutuante usando os 1000 números mais recentes como amostra de dados. Qual é a maneira mais fácil de conseguir isso, experimentei usar uma matriz circular, média móvel exponencial e uma média móvel mais simples, e descobri que os resultados da matriz circular se adequavam melhor às minhas necessidades. perguntou 12 de junho de 12 às 4:38 Se as suas necessidades são simples, você pode tentar usar uma média móvel exponencial. Simplificando, você cria uma variável de acumulador e, à medida que seu código examina cada amostra, o código atualiza o acumulador com o novo valor. Você escolhe um alfa constante que esteja entre 0 e 1 e calcula isso: você só precisa encontrar um valor de alfa onde o efeito de uma determinada amostra dura apenas cerca de 1000 amostras. Hmmm, eu não tenho certeza se isso é adequado para você, agora que eu coloquei aqui. O problema é que 1000 é uma janela muito longa para uma média móvel exponencial Não tenho certeza se existe um alpha que possa distribuir a média nos últimos 1000 números, sem underflow no cálculo do ponto flutuante. Mas se você quisesse uma média menor, como 30 números ou mais, essa é uma maneira muito fácil e rápida de fazer isso. respondeu 12 de junho às 12:44 1 em seu post. A média móvel exponencial pode permitir que o alfa seja variável. Então, isso permite que ele seja usado para calcular as médias da base de tempo (por exemplo, bytes por segundo). Se o tempo desde a última atualização do acumulador for maior que 1 segundo, você deixa o alpha ser 1.0. Caso contrário, você pode deixar o alpha ser (usecs desde a última atualização / 1000000). Basicamente eu quero acompanhar a média móvel de um fluxo contínuo de um fluxo de números de ponto flutuante usando os 1000 números mais recentes como uma amostra de dados. Observe que o abaixo atualiza o total como elementos adicionados / substituídos, evitando o deslocamento O (N) caro para calcular a soma - necessária para a média - sob demanda. Total é feito um parâmetro diferente de T para suportar, e. usando um longo longo ao totalizar 1000 long s, um int para char s, ou um double para total float s. Isso é um pouco defeituoso, pois as amostras podem passar do INTMAX - se você se importar, pode usar um sinal longo sem assinatura. ou use um membro extra de dados de bool para registrar quando o contêiner é preenchido pela primeira vez enquanto circula números em torno do array (melhor que renomeie algo inócuo como pos). Resposta: 12 de junho, às 5:19, assume-se que o operador "qvoid" (amostra T) é, na verdade, o operador "co-vi" ("amostra T"). ndash oPless Jun 8 14 às 11:52 oPless ahhh. bem manchado. na verdade eu quis dizer que seria void operator () (amostra T), mas é claro que você poderia usar qualquer notação que você gostasse. Vai consertar, obrigado. ndash Tony D 8 de junho 14 em 14:27