Est-il recommandé d'implémenter des séries temporelles en programmation fonctionnelle (F#) ?

Question

Je développe un projet en .NET, dans le cadre duquel je vais manipuler des séries temporelles.

Étant donné que la partie principale du projet a été implémentée en C#, j'ai esquissé une conception orientée objet héritant de SortedDictionary.

Cependant, je suis amoureux de la programmation fonctionnelle depuis quelques années, et j'ai pensé que puisque ce composant sera soumis à des algorithmes assez sauvages et intenses, je serais prêt à le traiter en parallèle et j'apprécierais d'avoir une structure immuable.

J'ai envisagé de le concevoir en F# en définissant un type comme suit :

type TimeSeries<'t> = (DateTime * 't) seq

et continuer ainsi.

Cela aurait l'avantage d'être immuable, et l'exécution en parallèle serait assez simple en utilisant le module Async de F#. Je pourrais également utiliser la fonctionnalité d'unité de mesure de F#.

Je suis juste un peu inquiet de devoir utiliser les résultats des calculs en C#, et je me demandais si quelqu'un qui l'a déjà essayé pourrait me donner un retour d'expérience concernant le résultat en pratique.

Était-ce facile à utiliser au final ou était-ce trop compliqué de passer de C# à F# ?

Le fait que la collection soit immuable ne pose-t-il pas un problème d'efficacité lorsque les séries temporelles deviennent plus importantes?

Serai-je en mesure de garder le type générique lorsque je vais essayer de diviser les éléments, ou devrai-je rapidement passer à TimeSeries avec mes fonctions?

Si je veux utiliser des algorithmes basés sur C# sur les séries temporelles pour certaines fonctionnalités, est-ce que cela rendrait toute cette idée inutile?

Avez-vous des références de recherches sur l'efficacité de l'implémentation fonctionnelle des séries temporelles?

Answer 1

Il aurait l'avantage d'être immutable, et l'exécution en parallèle serait assez simple en utilisant le module Async de F#.

Par contre, les seq sont lents et intrinsèquement séquentiels. L'équivalent littéral de F# de SortedDictionary est Map mais il n'a pas de support pour le parallélisme. Le module Async est bon pour la programmation concurrente asynchrone mais mauvais pour le parallélisme.

En supposant que vous voulez une recherche rapide en fonction du temps et itérer dans l'ordre mais pas d'insertion ou de suppression incrémentale, alors vous voulez un tableau trié de KeyValuePair car cela offre une excellente localité et, par conséquent, une complexité de cache pour les algorithmes parallèles. Notez que les tableaux peuvent être purement fonctionnels si vous évitez de les muter. Attention, F# 2 ne spécialise pas les opérations (comme la comparaison) sur DateTime donc vous devrez les appeler manuellement.

L'équivalent purement fonctionnel idiomatique de cela serait un arbre de recherche équilibré partitionné par le temps :

type TimeSeries<'a> =
  | Leaf of DateTime * 'a
  | Branch of TimeSeries<'a> * DateTime * TimeSeries<'a>

Cela permet des fonctions "parallèles" élégantes. Cependant, la réalité est que la programmation purement fonctionnelle n'est pas bonne pour le parallélisme multicœur car elle ne peut pas garantir quoi que ce soit sur la localité et, par conséquent, la complexité du cache des algorithmes purement fonctionnels est imprévisible et les performances sont souvent médiocres.

N'est-ce pas un problème d'efficacité que la collection soit immutable lorsque les séries temporelles deviennent plus grandes ?

Tout dépend de ce que vous voulez en faire.

Avez-vous des références de recherches faites sur l'efficacité de l'implémentation fonctionnelle des séries temporelles ?

Vous n'avez rien dit sur les algorithmes que vous avez l'intention d'implémenter ou même sur les opérations que vous voulez être rapides donc il est difficile de parler de performance mesurée de façon utile. En lançant un test rapide sur mon netbook, l'insertion de 1 000 000 liaisons dans un dictionnaire prend 5,2s avec le SortedDictionary mutable et 11,8s avec le Map immutable donc il y a une différence significative mais pas énorme. Construire l'array équivalent ne prend que 0,027s. L'itération prend ensuite 0,38s, 0,20s et 0,01s, respectivement.

Je suis juste un peu effrayé à l'idée de devoir utiliser les résultats des calculs en C#, et je me demandais si quelqu'un qui l'a déjà essayé pourrait me donner des retours sur le résultat en pratique.

Il suffit d'exposer une interface standard .NET depuis votre code F# et c'est facile.

Answer 2

Quelques points à noter :

• Dans le cas où vous souhaitez exposer une API de composant F# à C# (ou un autre langage CLR), vous devriez utiliser le BCL (ou les types orientés objet) dans l'API publique du composant F#. Sinon, vous devrez comprendre tous les types que la bibliothèque de base de F# utilise pour implémenter la sensation fonctionnelle de F#. Par exemple : FsharpFunc
• Le traitement parallèle (en lecture seule) des structures de données immuables est bon car vous êtes sûr que personne ne modifiera les données en arrière-plan et vous n'avez donc pas besoin de verrouillage, etc.
• Une structure de données immuable ne semble peut-être pas bonne lorsque vous voulez par exemple ajouter un élément à la fin d'une liste, ce qui, théoriquement, dans le cas de données immuables, copiera toute la liste avec le nouvel élément. Cela est généralement évité par certaines implémentations intelligentes de structures de données immuables comme les structures de données persistantes en clojure qui ne sont pas présentes en F# (encore).

J'espère que les points ci-dessus vous aideront à décider ce qui correspondrait le mieux à votre implémentation spécifique.