Je ne connais pas la terminologie correcte pour poser cette question, donc je vais la décrire avec beaucoup de mots à la place, supportez-moi.
Contexte , juste pour que nous soyons sur la même longueur d'onde: les programmes contiennent souvent des caches - un compromis temps / mémoire. Une erreur courante d'un programmeur est d'oublier de mettre à jour une valeur mise en cache après avoir changé l'une de ses sources / précédents en amont. Mais le paradigme de programmation de flux de données ou FRP est à l'abri de telles erreurs. Si nous avons un certain nombre de fonctions pures et les connectons ensemble dans un graphe de dépendances dirigées, les nœuds peuvent avoir leur valeur de sortie mise en cache et réutilisée jusqu'à ce que l'une des entrées de la fonction change. Cette architecture système est décrite dans l'article Caching In Dataflow-Based Environments et dans un langage impératif, elle est plus ou moins analogue à la mémorisation.
Problème : lorsqu'une des entrées d'une fonction change, nous devons toujours exécuter la fonction dans son ensemble, en supprimant sa sortie mise en cache et en recalculant à partir de zéro. Dans de nombreux cas, cela me semble inutile. Prenons un exemple simple qui génère une liste des "5 meilleurs". Les données d'entrée sont une liste non triée de quoi que ce soit. Il est transmis en entrée à une fonction qui génère une liste triée. Qui à son tour est entré dans une fonction qui ne prend que les 5 premiers éléments. En pseudocode:
input = [5, 20, 7, 2, 4, 9, 6, 13, 1, 45]
intermediate = sort(input)
final_output = substring(intermediate, 0, 5)
La complexité de la fonction de tri est O (N log N). Mais considérez que ce flux est utilisé dans une application où l'entrée ne change que peu à la fois, en ajoutant 1 élément. Plutôt que de re-trier à partir de zéro à chaque fois, il serait plus rapide, en fait O (N), d'utiliser une fonction qui met à jour l'ancienne liste triée en cache en insérant le nouvel élément dans la position correcte. Ce n'est qu'un exemple - de nombreuses fonctions "à partir de zéro" ont de telles contreparties "mise à jour incrémentielle". De plus, peut-être que le nouvel élément ajouté n'apparaîtra même pas dans la sortie finale, car il se trouve après la 5e position.
Mon intuition suggère qu'il pourrait être possible en quelque sorte d'ajouter de telles fonctions de "mise à jour incrémentielle" à un système de flux de données, côte à côte avec les fonctions "à partir de zéro" existantes. Bien sûr, tout recalculer à partir de zéro doit toujours donner le même résultat qu'un tas de mises à jour incrémentielles. Le système devrait avoir la propriété que si chacune des paires FromScratch-Incremental primitives individuelles donne toujours le même résultat, alors les fonctions composites plus grandes construites à partir d'elles devraient également donner automatiquement le même résultat.
Question : Est-il possible d'avoir un système / architecture / paradigme / méta-algorithme qui peut prendre en charge à la fois les fonctions FromScratch et leurs homologues incrémentiels, coopérant pour l'efficacité et composé en grands flux? Sinon, pourquoi? Si quelqu'un a déjà étudié ce paradigme et l'a publié, comment s'appelle-t-il et puis-je obtenir un bref résumé de son fonctionnement?
Réponses:
Ce domaine a été inventé de nombreuses fois et porte plusieurs noms, tels que:
(Et peut-être plus.) Ce ne sont pas les mêmes, mais liés.
Paraphrasant Cai et al (1): Il existe deux façons principales de mettre en œuvre des algorithmes en ligne de manière générique (c'est-à-dire sans référence à un problème algorithmique spécifique):
Incrémentalisation statique. Les approches statiques analysent un programme au moment de la compilation et produisent une version incrémentielle qui met à jour efficacement la sortie du programme d'origine en fonction des entrées changeantes. Les approches statiques peuvent être plus efficaces que les approches dynamiques, car aucune comptabilité lors de l'exécution n'est requise. De plus, les versions incrémentielles calculées peuvent souvent être optimisées à l'aide de techniques de compilation standard telles que le pliage constant ou l'inlining. C'est l'approche étudiée dans (1).
Incrémentalisation dynamique. Les approches dynamiques créent des graphiques de dépendance dynamiques pendant l'exécution du programme et propagent les modifications le long de ces graphiques. L'approche la plus connue est le calcul autoréglable d'Acar. L'idée clé est simple: les programmes s'exécutent sur l'entrée d'origine dans un environnement d'exécution amélioré qui suit les dépendances entre les valeurs dans un graphique de dépendance dynamique; les résultats intermédiaires sont mis en cache. (Comme vous pouvez l'imaginer, cela a tendance à utiliser beaucoup de mémoire, et de nombreuses recherches dans ce domaine portent sur la façon de limiter l'utilisation de la mémoire.) Plus tard, les modifications apportées à l'entrée se propagent via des graphiques de dépendance des entrées modifiées aux résultats, mettant à jour les niveaux intermédiaire et résultats finaux; ce traitement est souvent plus efficace que le recalcul. Cependant, la création de graphiques de dépendance dynamique impose une surcharge importante à facteur constant pendant l'exécution, allant de 2 à 30 dans les expériences rapportées.
De plus, on peut toujours essayer de trouver «à la main» une version en ligne d'un algorithme donné. Cela peut être difficile.
(1) Y. Cai, PG Giarrusso, T. Rendel, K. Ostermann, A Theory of Changes for Higher-Order Languages: Incrementalizing λ-Calculi by Static Différenciation .
la source
Vous recherchez probablement une programmation adaptative . Voir également la thèse d' Umut Acar . Je ne suis pas à jour avec ce domaine de travail mais cela devrait vous aider à démarrer, vous pouvez rechercher des références.
la source