[FMX] Implémentation de MapReduce

Bonjour,

Dans cet exemple, je vous propose une implémentation des méthodes map, reduce, filter que l'on retrouve dans d'autres langages (essentiellement fonctionnels).

Pré-requis vous devez avoir au minimum Delphi 10.3 (Rio). En effet, j'ai développé cet exemple avec Delphi 11 et j'ai utilisé les génériques (disponibles à partir de Delphi 2009) et les variables inline et l'inférence de type (disponibles à partir de Delphi 10.3 il me semble).
Le projet exemple fourni est réalisé avec FMX mais l'unité GBEArray.pas peut être utilisée en VCL également.

Explications
Très brièvement, je vais détailler les rôles de ces 3 méthodes.
La méthode map permet à partir d'un tableau et d'une fonction anonyme passée en paramètre, de créer un nouveau tableau de la même taille que le tableau d'origine mais en appliquant la fonction anonyme à tous les éléments du tableau. La méthode map est souvent comparée à une boucle for.
La méthode filter permet à partir d'un tableau et d'une fonction anonyme passée en paramètre, de créer un nouveau tableau de taille inférieure ou égale au tableau d'origine. La méthode anonyme passée en paramètre permet de filtrer et de ne conserver que les éléments souhaités du tableau d'origine. Le nouveau tableau résultant est donc très souvent de taille plus petite que le tableau d'origine. C'est l'objectif du filtre.
La méthode reduce permet à partir d'un tableau et d'une fonction anonyme passée en paramètre, de créer un unique élément (donc pas un tableau) qui agrège des informations du tableau d'origine à l'aide de la fonction anonyme passée en paramètre.

Exemple
Si vous n'êtes pas familier des langages fonctionnels (comme moi), vous pouvez vous demander quel est l'intérêt de ces méthodes. Nous allons voir cela dans le projet exemple joint à ce post.
Dans le projet joint, vous trouverez l'unité GBEArray.pas qui contient l'implémentation de ces méthodes plus deux autres Sort et Print.
Un petit mot sur ces deux méthodes. Comme je manipule des objets de type TArray, il pouvait être utile d'utiliser leur méthode "sort" pour trier le tableau : d'où 'ajout de la méthode sort au TGBEArray. La méthode Print sert à afficher (à l'aide d'une fonction anonyme passée en paramètre) tous les éléments du tableau. Elle m'a servit au debug et je l'ai laissée.

Le programme exemple fourni lui aussi dans le zip se présente de la manière suivante :
Pièce jointe 619108

Le bouton "Initialiser" permet d'initialiser une liste aléatoire de 20 entiers affichés dans la liste de gauche. Cela permet d'initialiser un tableau d'entier pour tester les méthodes map, reduce et filter.

Le bouton "Map (x2)" permet de lancer l'exécution de la méthode map sur ce tableau en passant en paramètre la fonction anonyme :

Code:

---

1 2 3 4

function(value: integer): integer begin result := value * 2; end

---

qui va permettre de multiplier par 2 chaque élément du tableau. Le résultat est est un nouveau tableau affiché dans la listbox2 (celle de droite).

Le bouton "Filter (>20)" permet de lancer l'exécution de la méthode filter sur le tableau d'origine en passant en paramètre une fonction anonyme qui indiquera qu'il ne faut conserver que les éléments dont la valeur est > 20.

Le bouton "Reduce (valeur init 0)" permet de lancer l'exécution de la méthode reduce sur le tableau d'origine en passant en paramètre une fonction anonyme qui permettra d'additionner les valeurs des différents éléments du tableau. La valeur initiale est un second paramètre de la méthode reduce qui permet de préciser une valeur initiale au calcul (dans notre cas 0 car on souhaite calculer la somme de tous les entiers du tableau).

Le bouton "Tri" permet de lancer l'exécution de la méthode sort sur le tableau d'origine ce qui produira un nouveau tableau avec les éléments du tableau d'origine trié. A noter, il est possible de passer un TComparer pour spécifier le tri que l'on souhaite faire sur des tableau de types plus complexes qu'un tableau d'entier (voir après ;) )

Là où ça devient intéressant, c'est que les méthodes map, reduce, filter, sort et print peuvent s'enchainer indéfiniment... Le bouton "Map x2, Filter >100 puis Reduce" montre cela car il enchaine :
- un appel à map en multipliant les valeurs par 2
- puis, un appel à filter pour ne conserver que les éléments dont la valeur obtenue est > 100
- puis un appel à reduce pour calculer la somme des valeurs obtenues

Enfin, le bouton "Exemple sur objets" est un exemple avec un tableau d'objet complexe (TPersonne fourni dans l'unité uPersonne.pas). Je crée un jeu d'essai dynamiquement de 10 personnes, puis j'utilise la méthode print pour simplement afficher ce jeu d'essai dans la liste 1, puis appel à filter pour ne sélectionner que les personnes dont le genre est renseigné, puis appel à map pour affecter à ces personnes un nombre de points aléatoire, puis appel à sort (avec utilsation d'un TComparer) pour trier le tableau obtenu par ordre décroissant des points, puis print pour afficher le résultat dans la liste 2 et enfin appel à reduce pour calculer le nombre de points total attribué.
Voici le résultat :
Pièce jointe 619110

Voici le zip du projet : Pièce jointe 619112

Hello, deux petites remarques sur ton code

1) les réallocations

dans initialiserList2 tu utilises "monTableau := monTableau + [StrToInt(s)];" c'est fonctionnel, mais cela implique à chaque itération une réallocation de monTableau pour avoir un élément de plus...selon le gestionnaire mémoire en place ça ne sera pas systématique (allocation d'une zone plus grande que demandée selon le gestionnaire), mais ce n'est pas optimal.

il est préférable de préallouer le tableau quand on en connait la taille car l'allocation mémoire est un process couteux en temps de calcul

Code:

---

1 2 3 4 5 6 7 8

procedure TForm2.initialiserList2; begin ListBox2.Clear; SetLength(monTableau, ListBox1.Items.Count); // une seule allocation mémoire for var i := 0 to in ListBox1.Items.Count - 1 do monTableau[i] := StrToInt(ListBox1.Items[i]); end;

---

même remarque pour l'unité GBEArray; pour Filter il est préférable d'allouer un premier tableau de la taille de Data puis de le réduire à la taille réellement utile...dans le pire des cas on aura une grosse allocation pour rien, mais ça restera 2 allocations, alors que par iteration sur un très gros tableau tu auras tout un tas d'allocation mémoire.

2) petit détail, mais dans la méthode Print tu retournes un nouveau TGBEArray<T> alors que tu pourrais retourner Self...au final ça ne change pas grand chose vu Delphi va faire la copie lui même puisqu'on est sur des Record et pas des Objets...mais dans l'idée, on est supposé retourner Self car Data n'est pas modifié :)

Bien vu Paul :)

Voici la version corrigée : Pièce jointe 619124

Pour la fonction Print, à l'origine c'était un copier/coller de la fonction map qui ne devait pas rester mais je la trouve finalement pratique.

Bonjour,

Voici une V3 du projet : Pièce jointe 619323

Cette version apporte de nouvelles méthodes au TGBEArray :
- any : elle prend une fonction anonyme en paramètre. Son objectif et de renvoyer un boolean indiquant s'il y a au moins un élément du tableau qui correspond au(x) critère(s) défini(s) dans la fonction anonyme);
- concat : elle prend un autre TGBEArray<T> en paramètre et permet de concaténer son contenu au TGBEArray d'origine;
- gather : elle prend une fonction anonyme en paramètre et une chaine de caractères (qui servira de séparateur). Son objectif est de générer un nouveau TGBEArray<string> qui permet de définir des couples clés/valeurs et qui regroupe les clés identiques afin qu'il n'y ait plus de doublon sur ces clés. Les valeurs peuvent alors être la concaténation des valeurs des clés identiques, leurs sommes... C'est la fonction anonyme qui indiquera le traitement à effectuer.

J'ai mis à jour l'application exemple en ajoutant des exemples pour ces nouvelles fonctionnalités :
Pièce jointe 619325

Les boutons sont regroupés dans des cadres colorés.
Le cadre bleu contient les boutons pour lancer les actions sur un tableau de valeurs entières généré aléatoirement. Il faut cliquer sur le bouton Initialiser pour générer ce jeu de données. Le jeu de données sera généré dans la listbox1. Les autres boutons du cadre bleu prendront ce jeu de données pour réaliser leurs actions. Les résultats des traitements seront affichés dans listbox2.
Le cadre violet est un essai avec un tableau d'un type plus complexe TPersonne. En cliquant sur le bouton correspondant, un jeu de données sera aussi générés dans listbox1 et le résultat des traitements sera affiché dans listbox2.
Enfin, le cadre jaune contient un TMemo contenant un texte exemple mais il est possible de l'éditer à sa convenance. Le clic sur le bouton de ce cadre va déclencher un traitement qui va lister les mots composants le texte du TMemo et pour chaque mot, compter le nombre d'occurrences de celui ci dans le texte. Un tri est effectué en fin de traitement afin de trier le résultat par ordre alphabétique des mots. Le résultat est affiché dans la listbox2.

Cela permet de voir de nouveaux exemples sur les possibilités de TGBEArray.

Pour information, j'ai mis le projet MapReduce sur mon GitHub : https://github.com/gbegreg/MapReduce
Il y a déjà une petite évolution suite à une remarque : les méthodes map et reduce peuvent maintenant avoir des types d'entrée et de sortie différents.

Les futures évolutions de ce projet seront faites sur le GitHub :)

Bonjour,
en fait ce n'est pas pour critiquer le projet, mais le titre que j'émets cette note.

MapReduce, tu m'as tellement habitué à la 3D qu'au départ je n'ai même pas regardé que le code n'était pas sur un dessin de carte que je cochai lu sans même regarder ! :oops:

puis-je suggérer quelque chose de plus explicite comme : 'Ajout des fonctions map, reduce et filter à un tableau'

Bonjour Serge,

Ça change un peu, il n'y a pas que la 3D :)

Par contre, il y aura certainement bientôt un nouveau petit sujet sur la 3D...

Bonsoir,

Petit up de cette discussion car j'ai ajouté pas mal de choses au TGBEArray depuis :) en m'inspirant de ce qui se fait dans d'autres langages. Le TGBEArray permet d'ajouter les méthodes suivantes à un TArray :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

function Add(aValue : T): integer; // ajoute une valeur du tableau et renvoie la nouvelle longueur du tableau function Any(Lambda: TPredicate<T>): boolean; // Y a t'il au moins un élément du tableau qui correspond au lambda passé en paramètre function Concat(anArray: TGBEArray<T>): TGBEArray<T>; // concatène le tableau avec un autre function Every(const Lambda: TPredicate<T>): Boolean; // Est ce que tous les éléments du tableau respecte la lambda passé en paramètre function Extract(fromElement : integer = 0; toElement : integer = 0): TGBEArray<T>; // renvoie un nouveau TGBEArray en extrayant du TGBEArray initial à partir de l'élément fromElement jusqu'à l'élément toElement function Fill(aValue : T; iStart : integer = 0; iEnd : integer = -1): TGBEArray<T>; // Remplit un TGBEArray<T> avec la valeur passé en paramètre function Filter(Lambda: TPredicate<T>): TGBEArray<T>; // renvoie un nouveau TGBEArray en ayant filtré à l'aide du lambda les éléments du tableau initial function FilterEvenItems(Lambda: TPredicate<T>): TGBEArray<T>; // même utilisation que Filter mais uniquement sur les éléments pairs du tableau initial function FilterOddItems(Lambda: TPredicate<T>): TGBEArray<T>; // même utilisation que Filter mais uniquement sur les éléments impairs du tableau initial function FindIndex(Lambda: TPredicate<T>):integer; // Renvoie l'indice du premier élément qui correspond au lambda function FirstOrDefault(const Lambda: TPredicate<T> = nil): T; // Renvoie le premier élément du tableau ou le premier élément qui correspond au lambda passé en paramètre procedure ForEach(Lambda: TProc<T>; fromElement : integer = 0); // exécute le lambda sur tous les éléments du tableau (pas de retour, le tableau d'origine est modifié) function Gather(Lambda: TFunc<T,string, string>; sep : string = ';'): TGBEArray<string>; // regroupe des éléments en fonction du lamda function Insert(aValue : T; index : integer = 0): TGBEArray<T>; // Insère une valeur à l'indice passé en paramètre et retourne un nouveau TGBEArray function LastOrDefault(const Lambda: TPredicate<T> = nil): T; // Renvoie le dernier élément du tableau ou le dernier élément qui correspond au lambda passé en paramètre function Map<S>(Lambda: TFunc<T, S>): TGBEArray<S>; // map : applique la lambda à tous les éléments du tableau et retourne un nouveau tableau (le tableau d'origine n'est pas modifié) function MapParallel<S>(Lambda: TFunc<T, S>): TGBEArray<S>; // même chose que map mais multithreadé function Pop:T; // renvoie le dernier élément du tableau et le supprime du tableau initial function Print(Lambda: TFunc<T, T>): TGBEArray<T>; // pour debug, comme map mais en vue d'afficher les éléments du tableau function Reduce<S>(Lambda: TFunc<S, T, S>; const Init: S): S; // reduce : permet d'avoir un accumulateur appliqué sur tous les éléments du tableau function ReduceRight<S>(Lambda: TFunc<S, T, S>; const Init: S): S; // même chose que reduce mais le tableau est inversé avant l'accumulation function Reverse:TGBEArray<T>; // Inverse le tableau function Shift: T; // renvoie le premier élément du tableau et le supprime du tableau initial function Swap(index1, index2 : integer): TGBEArray<T>; // Renvoie un nouveau tableau avec échange des éléments index1 et index2 function Sort(const Comparer: IComparer<T> = nil): TGBEArray<T>; // tri du tableau avec possibilité de passer en paramètre un IComparer afin de préciser la manière de trier function SuchAs(index : integer; aValue : T): TGBEArray<T>; // Renvoie un nouveau tableau similaire au tableau d'origine avec pour unique différence une valeur particulière à l'indice index function ToArray: TArray<T>; // convertit le TGBEArray en TArray function ToDictionary(iStartKey : integer = 0): TDictionary<integer, T>; // convertit le TGBEArray en TDictionary avec un paramètre facultatif permettant de spécifier l'indice de départ function ToString(Lambda: TFunc<T, String>; sep : string = ','): String; // convertit le TGBEArray en string en utilisant le lambda passé en paramètre qui doit permettre de transformer T en string function Unique: TGBEArray<T>; // Renvoie un nouveau tableau sans doublon

---

L'application exemple fournie avec l'unité GBEArray.pas a été mise à jour aussi pour montrer différents exemples.
En particulier, un petit exemple avec un TGBEArray<TValue> : utilisation de ces méthodes sur un tableau qui contient des éléments de types différents.

Le projet est disponible sur mon GitHub