Java Moving Average Queue

Implementando uma fila FIFO de comprimento fixo em Java Ao trabalhar com dados de séries temporais, muitas vezes precisa calcular somas de números consecutivos por um período de tempo predeterminado. Imagine, por exemplo, calcular uma média móvel com um tamanho fixo. Vamos ver uma série de tempo muito simples. Assumindo que uma média móvel do comprimento 4 resulta na seguinte matriz: A fórmula para uma média móvel do comprimento 4 é assim: MA t (Soma de todos os elementos de t-3 a t) 4 Como implementaremos isso eficientemente no código Java. O problema é que precisamos calcular a Soma na fórmula para cada média móvel. É claro que sempre é possível reiterar sobre todos os números no atual período de tempo para fazê-lo, mas isso é desnecessariamente lento. Em vez disso, podemos simplesmente subtrair o último elemento no intervalo de tempo e adicionar o mais novo a Sum. Desta forma, podemos salvar um número significativo de cálculos desnecessários. Ainda temos que acompanhar o que realmente são os elementos antigos e novos. Nós devemos armazenar esses números em algum lugar. Uma estrutura de dados apropriada seria uma fila de números first-in-first-out (FIFO). Mas como exatamente uma fila FIFO pode ser implementada em uma linguagem de programação (não funcional), como Java. A primeira idéia geralmente é usar uma implementação baseada em matriz e mudar a posição de elementos na matriz criando repetidamente cópias ligeiramente deslocadas de A matriz. No exemplo acima, precisamos criar uma nova matriz cinco vezes, uma vez por cada nova Soma sendo calculada. Isso é, obviamente, muito ineficiente, porque a criação de uma matriz na memória é relativamente lenta. As implementações baseadas em classes como java. util. ArrayList ou java. util. Vector já são muito melhores, porque internamente dependem de matrizes e índices mais longos. Ainda assim, esta não é a melhor solução, porque uma vez que os índices internos se movem para fora dos limites internos da matriz39, uma nova cópia da matriz interna deve ser criada. Uma alternativa típica para a implementação de filas FIFO é, portanto, usando uma lista vinculada: a vantagem é óbvia, não mais copiando ou recriando arrays na memória. Tudo o que temos a fazer é manipular algumas dicas. Claro que perdemos a vantagem de avaliar diretamente um elemento na fila por índice, mas para nosso propósito - calcular as médias móveis - isso é algo que não queremos fazer de qualquer maneira. Ontem, de repente, ocorreu-me que existe uma alternativa ainda melhor se o comprimento da fila for corrigido (como no nosso exemplo). Nós podemos efetivamente usar um anel. Adicionar um novo número à fila e deixar o mais antigo é o mesmo que simplesmente substituir o elemento mais antigo neste anel por um novo. Internamente, podemos usar novamente uma matriz de um comprimento fixo em combinação com um índice rotativo. É assim que o código se parece em Java. Primeiro, let39s criem nossa própria interface de fila: esta interface se desvia um pouco da fornecida nas bibliotecas Java, mas isso não é importante por enquanto. Em seguida, a implementação da nossa fila: a fila quotrollsquot através do anel. Adicionar um novo elemento na cabeça da fila remove automaticamente o elemento mais antigo na fila - nenhuma cópia de arrays ou reinicialização de referências de objeto necessárias. Ao contrário das listas vinculadas, podemos realmente acessar cada elemento no anel diretamente com o método get. Finalmente, podemos criar uma subclasse do nosso objeto de fila que irá rolar graciosamente à medida que novos valores são adicionados ao queuering. Nós podemos usar a classe agora. O comprimento da média móvel é inicialmente definido através do comprimento da matriz dada ao seu construtor. Preciso acompanhar os últimos 7 dias de horas de trabalho em um loop de leitura de arquivo plano. Está sendo usado para medir a fatigabilidade das listas de trabalho. Agora eu tenho algo que funciona, mas parece bastante detalhado e não tenho certeza se há um padrão que é mais sucinto. Atualmente, tenho uma classe Java com uma matriz estática para armazenar os últimos dados de x dias, então, ao ler o arquivo, retiro o primeiro elemento e mova os outros 6 (por um total de uma semana) de volta por um. O processamento desta matriz estática é feito em seu próprio método, ou seja. A minha pergunta: é uma abordagem de design razoável, ou há algo extremamente óbvio e simples de fazer essa tarefa. Obrigado. Eles pediram 30 de agosto 11 às 14:33. Agradeço muito, pessoal: eu recebi a mensagem: use um objeto de nível superior e aproveite o Métodos relevantes ou um buffer circular. Excelentes respostas, todas elas. Quando você pensa sobre isso, você sempre precisa ter acesso a toda a matriz para que você possa se livrar dessa primeira entrada - da qual eu não tinha certeza por minha conta. Eu aliviei que eu não tivesse perdido algum liner e estava basicamente em uma faixa razoável, se não eficiente e fácil. Isso é o que eu adoro neste site: respostas de alta qualidade e relevantes de pessoas que conhecem seu sht. Ndash Pete855217 30 de agosto 11 às 15:05 Por que você inicializa o runningTotal para null O que é seu tipo Onde é declarado Isso faria bem se você colocar alguns exemplos de código que se assemelham ao código Java atual. Em frente, minha crítica seria a seguinte: sua função faz demais. Uma função ou método deve ser coeso. Mais apropriadamente, eles devem fazer uma coisa e uma coisa apenas. Pior ainda, o que acontece no seu loop for quando x 5 Você copia runningTotal6 em runningTotal5. Mas então você tem duas cópias do mesmo valor na posição 5 e 6. No seu projeto, sua função movesshuffles os itens em sua matriz calcula o material total de impressões para o erro padrão retorna o total. Faz demais. Minha primeira sugestão não é mover coisas na matriz. Em vez disso, implemente um buffer circular e use-o em vez da matriz. Isso simplificará seu design. A minha segunda sugestão é dividir as coisas em funções que são coesas: tenha uma estrutura de dados (um buffer circular) que lhe permita adicionar a ela (e isso diminui a entrada mais antiga sempre que ela atinja sua capacidade.) Tenha a estrutura de dados implementada Interator tem uma função que calcula o total no iterador (você não se importa se você estiver calculando o total de uma matriz, lista ou operador circular). Não o chame total. Chame isso de soma, que é o que você está informando. Isso é o que eu faço :) Essa é a ótima informação de luis, no entanto, lembre-se de que esta função é uma pequena parte da funcionalidade da classe, e seria demais para adicionar muito código para torná-la perfeita. Você é tecnicamente correto, e eu entendo que meu código faz 39 muito muito39, mas, ao mesmo tempo, às vezes é melhor errar ao lado de um código menor e mais claro do que ir para a perfeição. Dadas as minhas habilidades em Java, mesmo fazer o pseudocódigo que você descreve a compilação me faria soprar meu orçamento neste (), mas obrigado pela descrição clara. Ndash Pete855217 31 de agosto 11 às 2:23 Hmmm, não é sobre a perfeição, mas sobre práticas industriais estabelecidas que conhecemos há 3 décadas. O código limpo é sempre um que é particionado. Temos décadas de evidências que indicam que este é o caminho a seguir no caso geral (em termos de custo-eficiência, redução de defeitos, compreensão, etc.). A menos que seja um código descartável por um tipo de coisa única. Nunca é dispendioso fazer isso quando se inicia qualquer análise de problema dessa maneira. Codificação 101, quebra o problema e o código segue, nem excesso nem dificuldade) ndash luis. espinal Ago 31 11 às 15:55 Sua tarefa é muito simples e a abordagem que você adotou é certamente boa para o trabalho. No entanto, se você quiser usar um design melhor, você deve se livrar de todo esse movimento numérico, você usa uma fila FIFO melhor e faz bom uso de métodos push e pop de forma que o código não reflete qualquer movimento de dados, apenas as duas ações de lógica De novos dados e remova dados com mais de 7 dias. Respondeu 30 de agosto 11 às 14:49