Algoritmo De Mediação Eficiente Em Movimento

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. Respondeu 15 de dezembro às 18:12 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 11 às 12: 35 Atualmente estou desenvolvendo um sistema LCD gráfico para exibir temperaturas, fluxos, voltagens, energia e energia em um sistema de bomba de calor. O uso de um LCD gráfico significa que metade do meu SRAM e 75 do meu flash foram usados ​​por um buffer de tela e strings. Atualmente estou mostrando números de minmaxaverage para energia À meia-noite, quando o valor diário é reiniciado, o sistema verifica se o consumo do dia está acima ou abaixo do mínimo ou mínimo anterior e armazena o valor. A média é calculada dividindo o consumo cumulativo de energia pelo número de dias. Gostaria de exibir a média diária na última semana e mês (4 semanas por simplicidade), ou seja, uma média móvel. Atualmente, isso envolve a manutenção de uma série de valores nos últimos 28 dias e o cálculo de uma média em toda a matriz para mensalmente e últimos 7 dias por semana. Inicialmente eu estava fazendo isso usando uma série de flutuadores (como a energia está na forma 12.12kWh), mas isso foi usando 28 4 bytes 112 bytes (5.4 de SRAM). Eu não me importo de ter apenas um único ponto decimal de resolução, então eu mudei para usar uint16t e multiplicando a figura por 100. Isso significa que 12.12 é representado como 1212, e eu dividir por 100 para exibição. O tamanho da matriz agora é de até 56 bytes (muito melhor). Não há uma maneira trivial de reduzir a figura para um uint8t que eu possa ver. Eu poderia tolerar a perda de uma casa decimal (12.1kWh em vez de 12.12kWh), mas o consumo é freqüentemente maior do que 25.5kWh (255 sendo o valor mais alto representado por um inteiro não assinado de 8 bits). O consumo nunca foi inferior a 10.0kWh ou acima de 35.0kWh, então, eu poderia subtrair 10 das figuras armazenadas, mas eu sei que um dia superaremos esses limites. Então testei o código para empacotar valores de 9 bits em uma matriz. Isso dá uma faixa de 0-51.2kWh e usa 32 bytes no total. No entanto, aceder a uma matriz como esta é bastante lento, especialmente quando você precisa iterar sobre todos os valores para calcular uma média. Então, minha pergunta é: existe uma maneira mais eficiente de calcular uma média móvel com três janelas - vida, 28 dias e 7 dias. Eficiência significa menor em termos de uso SRAM, mas sem a pena de um código enorme. Posso evitar armazenar todos os valores solicitados em 7 de março às 8:32. Eu já pensei e você está certo. Então, tecnicamente, torna minha resposta incorreta. Estou investindo mais tempo e paciência nisso. Talvez algo fora da caixa. Vou avisá-lo se eu encontrar alguma coisa. Fazemos algo assim muito no meu local de trabalho. Deixe-me perguntar ao redor. Desculpe pela confusão. Ndash Aditya Somani Mar 8 14 às 17:15 existe uma maneira mais eficiente de calcular uma média móvel com. 28 dias e 7 dias. Precisando lembrar 27 dias de história. Você pode ficar perto o suficiente armazenando 11 valores em vez de 28 valores, talvez algo como: Em outras palavras, ao invés de armazenar todos os detalhes de todos os dias durante os últimos 27 dias, (a) armazene 7 ou mais valores de informações diárias detalhadas para o passado 7 ou mais dias, e também (b) armazenar 4 ou mais valores resumidos de informações totais ou médias para cada uma das últimas 4 semanas.