Não sei a terminologia correta para fazer esta pergunta, portanto, descreverei-a com muitas palavras.
Em segundo plano , apenas para estarmos na mesma página: os programas geralmente contêm caches - uma troca de tempo / memória. Um erro comum do programador é esquecer de atualizar um valor em cache após alterar uma de suas fontes / precedentes upstream. Mas o paradigma de programação de fluxo de dados ou FRP é imune a esses erros. Se tivermos várias funções puras e conectá-las em um gráfico de dependência direcionado, os nós poderão ter seu valor de saída em cache e reutilizados até que qualquer uma das entradas da função seja alterada. Essa arquitetura do sistema é descrita no artigo Armazenamento em cache em ambientes baseados em fluxo de dados e, em uma linguagem imperativa, é mais ou menos análoga à memorização.
Problema : Quando uma das entradas de uma função é alterada, ainda precisamos executar a função como um todo, descartando sua saída em cache e recalculando do zero. Em muitos casos, isso parece um desperdício para mim. Considere um exemplo simples que gera uma lista dos "5 melhores, seja qual for". Os dados de entrada são uma lista não classificada de qualquer coisa. É passado como entrada para uma função que gera uma lista classificada. Que, por sua vez, é inserido em uma função que leva apenas os 5 primeiros itens. No pseudocódigo:
input = [5, 20, 7, 2, 4, 9, 6, 13, 1, 45]
intermediate = sort(input)
final_output = substring(intermediate, 0, 5)
A complexidade da função de classificação é O (N log N). Mas considere que esse fluxo é usado em um aplicativo em que a entrada muda apenas um pouco de cada vez, adicionando 1 elemento. Em vez de re-ordenar do zero toda vez, seria mais rápido, de fato O (N), usar uma função que atualiza a lista classificada em cache antiga, inserindo o novo elemento na posição correta. Este é apenas um exemplo - muitas funções "do zero" possuem essas contrapartes de "atualização incremental". Além disso, talvez o elemento recém-adicionado nem apareça na final_output porque está após a 5ª posição.
Minha intuição sugere que pode ser possível, de alguma forma, adicionar funções de "atualização incremental" a um sistema de fluxo de dados, lado a lado com as funções "do zero" existentes. Obviamente, recalcular tudo do zero deve sempre dar o mesmo resultado que um monte de atualizações incrementais. O sistema deve ter a propriedade de que se cada um dos pares fromscratch-incremental primitivas individuais sempre produzir o mesmo resultado, então as funções compostas maiores construídos a partir deles devem também dar automaticamente o mesmo resultado.
Pergunta : É possível ter um sistema / arquitetura / paradigma / meta-algoritmo que possa suportar as funções FromScratch e suas contrapartes incrementais, cooperando pela eficiência e compostas em grandes fluxos? Se não, por que? Se alguém já pesquisou esse paradigma e o publicou, como é chamado e posso obter um breve resumo de como ele funciona?
Respostas:
Este campo foi inventado várias vezes e está sob muitos nomes, como:
(E possivelmente mais.) Esses não são os mesmos, mas relacionados.
Parafraseando Cai et al (1): Existem duas formas principais de implementar algoritmos on-line genericamente (ou seja, sem referência a qualquer problema algorítmico específico):
Incrementalização estática. As abordagens estáticas analisam um programa em tempo de compilação e produzem uma versão incremental que atualiza com eficiência a saída do programa original de acordo com as alterações nas entradas. As abordagens estáticas têm o potencial de serem mais eficientes do que as abordagens dinâmicas, porque nenhuma contabilidade em tempo de execução é necessária. Além disso, as versões incrementais computadas geralmente podem ser otimizadas usando técnicas padrão do compilador, como dobragem constante ou embutimento. Essa é a abordagem investigada em (1).
Incrementalização dinâmica. As abordagens dinâmicas criam gráficos de dependência dinâmicos enquanto o programa é executado e propagam alterações ao longo desses gráficos. A abordagem mais conhecida é a computação autoajustável da Acar. A idéia principal é simples: os programas são executados na entrada original em um ambiente de tempo de execução aprimorado que rastreia as dependências entre valores em um gráfico de dependência dinâmica; resultados intermediários são armazenados em cache. (Como você pode imaginar, isso tende a usar muita memória, e muitas pesquisas neste campo são sobre como limitar o uso de memória.) resultados finais; esse processamento geralmente é mais eficiente que a recomputação. No entanto, a criação de gráficos de dependência dinâmica impõe uma grande sobrecarga de fator constante durante o tempo de execução, variando de 2 a 30 em experimentos relatados.
Além disso, pode-se sempre tentar criar 'manualmente' uma versão on-line de um determinado algoritmo. Isso pode ser difícil.
(1) Y. Cai, PG Giarrusso, T. Rendel, K. Ostermann, A Theory of Changes for High-Order Languages: Incrementalizing λ-Calculi por diferenciação estática .
fonte
Você provavelmente está procurando programação adaptável . Veja também a tese de doutorado de Umut Acar . Não estou atualizado com esta área de trabalho, mas deve começar, você pode buscar referências.
fonte