Média Ponderada C ++

Estou tentando calcular a média móvel de um sinal. O valor do sinal (um duplo) é atualizado em horários aleatórios. Estou procurando uma maneira eficiente de calcular sua média ponderada no tempo ao longo de uma janela de tempo, em tempo real. Eu poderia fazê-lo sozinho, mas é mais desafiante do que eu pensava. A maioria dos recursos que eu encontrei pela internet calculam a média móvel do sinal periódico, mas as atualizações das minas em tempo aleatório. Alguém conhece bons recursos para isso. O truque é o seguinte: você obtém atualizações em horários aleatórios através da atualização vazia (tempo int, valor flutuante). No entanto, você também precisa acompanhar quando uma atualização cai fora da janela de tempo, então você define um alarme chamado no momento N, que remove a atualização anterior de ser novamente considerado novamente na computação. 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) para ser chamado no tempo N Se esta é uma simulação, você não pode obter ajuda do sistema operacional e você precisa 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 são garantidas de tal forma que os argumentos de tempo estão aumentando. Neste caso, você precisa manter uma lista ordenada de valores do tempo de alarme e, para cada atualização e leitura, você verifica se o argumento de tempo é maior do que a cabeça da lista de alarmes. Embora seja maior, você faz o processamento relacionado ao alarme (abandone a atualização mais antiga), remova a cabeça e verifique novamente até que todos os alarmes anteriores ao tempo fornecido sejam processados. Em seguida, faça a chamada de atualização. Tenho até agora assumido que é óbvio o que você faria para a computação real, mas vou elaborar apenas no caso. Eu suponho que você tenha um método flutuante lido (int time) que você usa para ler os valores. O objetivo é tornar este chamado tão eficiente quanto possível. Então você não calcula a média móvel sempre que o método de leitura é chamado. Em vez disso, você precomputa o valor a partir da última atualização ou o último alarme, e ajuste esse valor por algumas operações de ponto flutuante para explicar a passagem do tempo desde a última atualização. (I. E. Um número constante de operações, exceto para talvez processar uma lista de alarmes empilhados). Esperemos que isso seja claro - este deve ser um algoritmo bastante simples e bastante eficiente. Otimização adicional. Um dos problemas restantes é se uma grande quantidade de atualizações acontecer dentro da janela de tempo, então há muito tempo para o qual não há leituras nem atualizações e, em seguida, uma leitura ou atualização vem junto. Nesse caso, o algoritmo acima será ineficiente para atualizar de forma incremental o valor de cada uma das atualizações que está caindo. Isso não é necessário porque nos preocupamos apenas com a última atualização além da janela de tempo, então, se houver uma maneira de descartar as atualizações mais antigas, isso ajudaria. Para fazer isso, podemos modificar o algoritmo para fazer uma busca binária de atualizações para encontrar a atualização mais recente antes da janela de tempo. Se houver relativamente poucas atualizações que precisam ser descartadas, pode-se incrementar o valor para cada atualização descartada. Mas se houver muitas atualizações que precisam ser descartadas, pode-se recalcular o valor a partir do zero depois de deixar as atualizações antigas. Apêndice sobre Computação Incremental: Devo esclarecer o que quero dizer com a computação incremental acima na frase ajustar esse valor por um par de operações de ponto flutuante para explicar a passagem do tempo desde a última atualização. Computação inicial não incremental: então iterar sobre os atuais relevantes em ordem crescente de tempo: tempo de exibição de motionaverage (sum tempo de atualização). Agora, se exatamente uma atualização cai fora da janela, mas nenhuma nova atualização chegou, ajuste a soma como: (note que é priorupdate que tem o timestamp modificado para iniciar o início da última janela). E se exatamente uma atualização entrar na janela, mas nenhuma nova atualização cai, ajuste a soma como: Como deve ser óbvio, este é um esboço áspero, mas espero que mostre como você pode manter a média de que é O (1) operações por atualização Em uma base amortizada. Mas observe uma otimização adicional no parágrafo anterior. Observe também as questões de estabilidade aludidas em uma resposta mais antiga, o que significa que os erros de ponto flutuante podem se acumulam em um grande número de tais operações incrementais, de modo que existe uma divergência com o resultado da computação total que é significativa para o aplicativo. Se uma aproximação é OK e há um tempo mínimo entre amostras, você pode tentar super-amostragem. Tenha uma matriz que represente intervalos de tempo uniformemente espaçados que sejam menores do que o mínimo, e em cada período de tempo armazene a última amostra que foi recebida. Quanto menor for o intervalo, mais próxima será a média para o valor verdadeiro. O período não deve ser superior a metade do mínimo ou há uma chance de perder uma amostra. Respondido 15 de dezembro às 18:12 respondido 15 de dezembro às 22:38 Obrigado pela resposta. Uma melhoria que seria necessário para realmente quotcachequot o valor da média total, então nós não vamos fazer o loop o tempo todo. Além disso, pode ser um ponto menor, mas não seria mais eficiente usar um deque ou uma lista para armazenar o valor, já que assumimos que a atualização virá na ordem correta. A inserção seria mais rápida do que no mapa. Ndash Arthur 16 de dezembro 11 às 8:55 Sim, você pode armazenar em cache o valor da soma. Subtrair os valores das amostras que você apaga, adicione os valores das amostras que você inseriu. Além disso, sim, um dequeltpairltSample, Dategtgt pode ser mais eficiente. Eu escolhi o mapa para legibilidade e a facilidade de invocar o mapa :: upperbound. Como sempre, escreva primeiro o código correto, depois perfile e mude as mudanças incrementais. Ndash Rob Dec 16 11 at 15:00 Nota: Aparentemente, esta não é a maneira de abordar isso. Deixando-o aqui para referência sobre o que há de errado com essa abordagem. Verifique os comentários. ATUALIZADO - com base no comentário Olis. Não tenho certeza sobre a instabilidade de que ele está falando. Use um mapa ordenado dos tempos de chegada contra valores. Após a chegada de um valor, adicione a hora de chegada ao mapa ordenado juntamente com seu valor e atualize a média móvel. Advertindo isso é pseudo-código: lá. Não totalmente elaborado, mas você consegue a ideia. Coisas a serem observadas. Como eu disse, o acima é pseudo-código. Você precisará escolher um mapa apropriado. Não remova os pares à medida que você itera, pois você invalidará o iterador e terá que começar de novo. Veja o comentário Olis abaixo também. Respondeu 15 de dezembro às 12:22 Isso não funciona: ele não leva em consideração a proporção do comprimento da janela para cada valor. Além disso, essa abordagem de adicionar e depois subtrair é apenas estável para tipos inteiros, não flutuadores. Ndash Oliver Charlesworth 15 de dezembro às 12:29 OliCharlesworth - desculpe, perdi alguns pontos-chave na descrição (dupla e ponderada no tempo). Vou atualizar. Obrigado. Ndash Dennis 15 de dezembro às 12:33 O tempo de ponderação é mais um problema. Mas isso não é o que eu estou falando. Eu estava me referindo ao fato de que quando um novo valor primeiro entra na janela de tempo, sua contribuição para a média é mínima. Sua contribuição continua a aumentar até um novo valor entrar. Ndash Oliver Charlesworth 15 de dezembro às 12: 35 Na minha aplicação comercial eu tenho ticks ao vivo dos preços das ações. Eu preciso manter a SMA. Vamos assumir que eu quero SMA de 20 velas, onde a duração de cada vela é de 10 segundos. Isso significa que a cada 10 segundos eu tenho checkpoint onde: Fecho a vela atual e armazene o preço médio nos últimos 10 segundos. A média é (máximo - min) 2 Eu lanço uma vela nova e armazeno o último preço. Eu limpo a vela desactualizada. Eu atualizo o último preço da vela de formação atual e recalculo o SMA. Então, em qualquer marca, preciso recalcular a SMA. Na maioria dos casos, apenas o preço da última vela é alterado (porque usamos o último preço). Uma vez por 10 segundos, eu preciso de um pouco mais de trabalho extra - preciso esquecer a média da vela desactualizada e armazenar a média da vela apenas criada. Você pode sugerir como implementar isso com menor latência. A baixa latência é um requisito primário. Perguntou 28 de abril às 10h21. Eu não tenho certeza se esta é a abordagem que você está procurando, mas aqui está o pseudocódigo para SMAs muito rápidos. Média de Movimento Simples: Eu suponho que seus dados vêm na forma de algum fluxo e armazenados na localização de memória contínua (pelo menos com endereços que podem ser mapeados continuamente). Assim, com duas adições e uma multiplicação (com 12000) você pode gerar médias móveis subsequentes para Os novos tiques. Média móvel exponencial: Essa é uma alternativa decente, como mencionado acima: Aqui não é realmente uma média móvel de N-dia. É apenas uma média móvel ponderada com 87 pesos até os últimos N-dias, então quase N-dias é mais parecido. Nota sobre otimizações do compilador: observe que ativar as opções SSE ou AVX, se disponível, habilitará uma aceleração maciça desses algoritmos, pois vários cálculos podem ser produzidos em um único ciclo de CPU. É improvável que o algoritmo produza um erro, a menos que as áreas de memória que estão sendo usadas também estão sendo alteradas por outro segmento. Quanto ao recálculo completo. Uma maneira de acelerar seu código é transferir esse processo para um segmento alternativo para que ele não bloqueie a execução do seu cálculo MA principal. Uma vez que esta é uma operação independente, seria muito fácil paralelizar este código ndash hnk 14 de julho 14 às 12:30 Então você precisa de uma fila, de tamanho bastante fixo, onde você pode adicionar itens de forma eficiente e remover o item mais antigo ( Para removê-lo do total de execução). Por que não std :: fila Isso pode se sentar em cima de vários recipientes, mas se você realmente tiver apenas 20 elementos, eu suspeito que um vetor funcionaria bem. (Remover um item requer mover todos os outros itens para baixo - mas mover blocos contíguos de memória é rápido.) Você pode querer comparar o desempenho com um deque ou lista. (A resposta pode depender do que você armazena para cada vela - apenas um único floatdoubleint, ou uma estrutura mais complexa)