Challenge mathématiques #23 : Intersection de deux tableaux

[emmanuel-fr]

Bonjour,

Avec un peu d'avance d'une journée, voici le nouveau challenge !

Cette fois il s'agit d'un défi d’algorithme mathématique optimisé… donc crayon, papier (et peut être la plage avec pour certains).

Il y a deux tableaux d’entiers triés, A et B. Il faut trouver l’intersection I des deux tableaux (= les éléments en commun)

Exemple :

A = [1 3 4 5 8 10 11 34 58] (n éléments)

B = [2 3 7 10 25 26 27 34 100] (m éléments)

I = [3 10 34]

Règles :

• Trouver les éléments communs le plus vite possible (une mesure de la vitesse sera faite)
  
• Impérativement documenter le code afin de décrire l’algorithme utilisé et les optimisations
• Utiliser les fonctions LabVIEW standard et pas de bibliothèques externes type OpenG ou des fonctions d’intersection toutes prêtes.
• Les 2 tableaux de test seront fabriqués avec une taille qui peut aller jusqu’à 1000000 et avec des différentes tailles entre les deux (100 fois ou 1000 fois plus d’éléments par exemple)
• Utilisez le VI Intersection_Mon Pseudo.vi (ci-joint) pour votre réponse afin de le placer dans le VI de test de vitesse avec les E/S.

Le gagnant est celui qui remplira le tableau de sortie le plus rapidement (algorithme le plus rapide).Il remportera la possibilité de passer une certification gratuitement. Pour ceux qui veulent le faire pour le fun uniquement sans courir après le prix, pas de soucis !  dites le moi sur votre réponse

Envoyez-moi votre code Intersection_Mon Pseudo.vi à emmanuel.roset@ni.com et postez sur la communauté un « code envoyé » afin que je puisse vérifier ma boite.

Bonne analyse et astuces

Gagnant ce mois-ci _MathieuPerrin

[Nico_EMC]

Code envoyer (pour le fun)

[Cisco]

Hello,

Petite précision sur les tableaux: est-ce qu'on aura systématiquement des tableaux classés, comme c'est le cas pour l'exemple fournit?

[Nico_EMC]

Dans l'énoncé, il est dit : "deux tableaux d’entiers triés", donc je pense que oui

[Cisco]

Merci Nico, je m'étais concentré sur la seconde partie de l'énoncé et avait occulté le début... Je ramasse mes dents et je regarde pour faire un petit bout de code...

[Laurent_Vaylet]

Bonjour à tous,

Je prends le relais en l'absence d'Emmanuel pour vous confirmer que les tableaux sont déjà triés dans l'ordre croissant. Sinon le problème perd tout son côté astucieux et vous êtes coincés avec une complexité temporelle de O(n*m). Le fait que les tableaux sont triés permet d'optimiser largement le traitement de gros tableaux, pour se rapprocher par exemple d'une complexité O((n+m)log(n+m)).

Amusez-vous bien !

Laurent

PS : j'ai donné d'autres idées à Emmanuel pour les prochains challenges, vous allez adorer 🙂

[MathieuPerrin]

Bonjour,

Peut-il y avoir des éléments répétés dans les tableaux en entrée, et quel est le comportement attendu dans ce cas ? Par exemple si

A = [1 3 4 5 8 10 10 11 34 58]

B = [2 3 7 10 10]

Est-ce que l'on s'attend à avoir I = [3 10] ou bien I = [3 10 10] ?

Mathieu

[Yann_50]

Bonjour,

code tout simple envoyé

[Laurent_Vaylet]

@Mathieu: on va rester simple. Pas d'éléments dupliqués dans les tableaux.

[emmanuel-fr]

Un coucou depuis mes vacances, ca cogite on dirai

Merci Laurent pour ton aide

J'ai recu les premiers codes et je suis en train de les regarder...

Ca reste simple en effet, mais l'optimisation peut prendre plus de temps.

Merci a ceux qui renvoient leur code pour le fun.

Et a tous, n'hésitez pas à envoyer vos codes même simples et non optimisés

[MathieuPerrin]

Bonjour, Code envoyé.

[MohamedBelmelia]

Bonjour,

est-il possible d'envoyer le code et faire éventuellement profiter la certification en cas de gain d'un de mes collègues ?

[Cisco]

Salut à tous!

Code envoyé, pour le fun!

[emmanuel-fr]

@MohamedBelmeliani, Il est préférable que cela soit la personne qui répond au challenge qui bénéficie du passage gratuit de la certification. Maintenant, si l'un de vos collègues veut participer, il n'y a pas de soucis pour qu'il m'envoie son code et post des messages sur la communauté

[Adrien.L]

Bonjour,

Code envoyé!

[adcpc]

Bonjour,

Code envoyé.

Intéressants ces challenges d'optimisation vitesse/mémoire.

[Alceste]

Hop, code envoyé !

[emmanuel-fr]

Bonjour,

J'ai recu pas mal de codes ces derniers temps. Voici la liste des personnes que j'ai. Si vous n'apparaissez pas, dites le moi

1 - Intersection_lulu4483

2 - Intersection_Nico_EMC

3 - Intersection_Yann-50

4 - Code MathieuPerrin

5 - Intersection_Cisco

6 - Intersection_Adrien L

7 - Intersection_adcpc

8 - Intersection_M@x

[R3g]

Code envoyé.

Je ne sais si c'est trop tard

[emmanuel-fr]

Bon voici les résultats : _MathieuPerrin est notre gagnant du mois !

j'ai ajouté R3g sur le fil mais malgré une bonne performance, _MathieuPerrin se détache avec un code... plutot sophistiqué

Il a envoyé 2 types de codes mais dans les 2 cas les résultats sont les meilleurs.

Les tests ont été fait par appel de VI avec 1000 valeurs et 100000 valeurs et des tableaux de tailles identiques. L'execution est effectuée 10 fois et ensuite on fait la moyenne. Au vu des résultats qui sont retournés par les 2 tailles de valeurs, seul le résultat de 100000 compte, bien plus challenging sur les optimisations.

Donc voici le premier tableau de toutes les valeurs brutes. Juste quelques personnes ont soit des valeurs de sorties pas correctes, soit un temps infini pour le calcul des 100000.

Dans le deuxième tableau des résultats trié par exécution la plus rapide en sec, sur la valeur moyenne

Nom	Type	Moyen	Max	Min	Valeurs
1 - Intersection_lulu4483.vi	Pour 1k	0,002156	0,002598	0,002034	Erreur
1 - Intersection_lulu4483.vi	Pour 100k	0,008973	0,010577	0,008306	Erreur
2 - Intersection_Nico_EMC.vi	Pour 1k	0,002697	0,003431	0,00246	Valide
2 - Intersection_Nico_EMC.vi	Pour 100k	0,015457	0,016482	0,015046	Valide
3 - Intersection_Yann-50.vi	Pour 1k	0,016622	0,017803	0,015876	Valide
3 - Intersection_Yann-50.vi	Pour 100k	0,117419	0,118947	0,116018	Valide
4 - Intersection_MathieuPerrin_2.vi	Pour 1k	0,000942	0,001134	0,000855	Valide
4 - Intersection_MathieuPerrin_2.vi	Pour 100k	0,013517	0,013967	0,013295	Valide
4 - Intersection_MathieuPerrin_1.vi	Pour 1k	0,000627	0,000918	0,000559	Valide
4 - Intersection_MathieuPerrin_1.vi	Pour 100k	0,013398	0,014582	0,012368	Valide
5 - Intersection_cisco.vi	Pour 1k	0,002842	0,003458	0,002686	Valide
5 - Intersection_cisco.vi	Pour 100k	Hors temps
6 - Intersection_Adrien L.vi	Pour 1k	0,000719	0,001054	0,000649	Valide
6 - Intersection_Adrien L.vi	Pour 100k	Hors temps
7 - Intersection_adcpc.vi	Pour 1k	0,000706	0,000764	0,000662	Valide
7 - Intersection_adcpc.vi	Pour 100k	8,108386	8,511044	8,011621	Valide
8 - Intersection_M@x.vi	Pour 1k	0,002569	0,002732	0,002443	Valide
8 - Intersection_M@x.vi	Pour 100k	0,015911	0,016582	0,015377	Valide
9 - Intersection_R3g.vi	Pour 1k	0,002692	0,002882	0,002533	Valide
9 - Intersection_R3g.vi	Pour 100k	0,015454	0,016019	0,015144	Valide

Nom	Type	Moyen
4 - Intersection_MathieuPerrin_1.vi	Pour 100k	0,013398
4 - Intersection_MathieuPerrin_2.vi	Pour 100k	0,013517
9 - Intersection_R3g.vi	Pour 100k	0,015454
2 - Intersection_Nico_EMC.vi	Pour 100k	0,015457
8 - Intersection_M@x.vi	Pour 100k	0,015911
3 - Intersection_Yann-50.vi	Pour 100k	0,117419
7 - Intersection_adcpc.vi	Pour 100k	8,108386

Bientot publication des codes réponses sur la page. Merci pour la communauté pour les codes commentés

[adcpc]

Bravo à MathieuPerrin.

Pour l'évaluation des résultats, ne serait-il pas mieux de répeter l'exécution du VI pendant une durée définie et prendre l'exécution la plus rapide ? Les temps d'exécution peuvent varier énormèment en fonction de ce que le système d'exploitation exécute en arrière plan. En faisant une moyenne on prend forcèment ces variations (qui ne sont pas dues à l'algorithme) en compte, non ?

[emmanuel-fr]

Oui c'est ce qui est fait, le code est appelé et lancé puis fermé 10 fois de suite et ensuite on fait la moyenne de tout. Pour la charge CPU, les codes sont lancés après que tout soit chargé et quand il y n'y pas de charge CPU en cours sur d'autres tâches windows afin que cela soit impartial et comparables pour tous. Et également lancé plusieurs fois dans la journée pour vérifier qu'il n'y a pas d'écart suspects.

[adcpc]

C'est justement le fait de faire une moyenne qui ne me semble pas correct. L'algorithme exécuté avec les deux même tableaux en entrée sur le même matériel devrait s'exécuter à chaque fois avec le même nombre d'instructions et donc à chaque fois avec la même durée sauf si les variations dues à l'OS entrent en jeu, auquel cas le temps d'exécution minimum me semble plus approprié.

D'ailleurs il est intéressant de voir qu'avec cette méthode, le classement final change et c'est Nico_EMC qui se retrouve 3ème devant R3g.

C'est évidemment un détail mais il est intéressant de voir que la méthode d'évaluation des résultats a son importance.

[emmanuel-fr]

Prendre le pic d'exécution le plus rapide (Min) uniquement ne reflette pas vraiment la réalité d'avoir les données dans un temps concret car nous ne savons pas exactement ce que fait Windows dans ses bufferisations et pipelining internes (parfois étrangement optimistes), je les ai ajouté pour détecter s'il y a avait un écart énorme afin d'enquêter pourquoi si besoin.

[MathieuPerrin]

Bonjour,

je suis bien content d'être arrivé premier ! C'est vrai que j'avais commencé ça en dilettante et ça avait fini par bien me prendre la tête... J'en étais arrivé à faire de la rétroingénierie sur la loi de probabilité utilisée dans la génération des tableaux ! ...avant de me dire que j'avais peut-être d'autres choses à faire !J'ai attendu d'avoir accès à un ordi avec LV 2014 pour regarder les codes et faire des commentaires.

@adcpc : c'est normal que les temps d'exécution de R3c et Nico_EMC soient très proches, car leurs codes sont quasi identiques. La seule différence est que Nico_EMC ne fait avancer qu'un indice en cas d'égalité, le second indice étant avancé à l'itération suivante. Comme il le met lui-même en commentaire, j'ai du mal à voir pourquoi ça accélère(rait) les choses, car il y aura des opérations dont on pourrait se passer à l'itération suivante... Pour ce qui est du benchmarking, personnellement, je n'ai testé qu'avec les tableaux donnés en exemple, et j'avais des résultats très stables en prenant la moyenne sur 500 itérations. Je crois que ce que windows fait a moins d'influence dans le cas d'un système multiprocesseurs tant qu'un des proc est disponible.

Leur code est similaire à mon algo 1. Si celui-ci est plus rapide, c'est peut-être parce que je teste l'égalité sans faire de différence, ou alors que le compilateur de LV2012 est meilleur que celui de 2014 (ce serait bizarre).

L'algo de M@x est aussi très proche même s'il a l'air différent au premier abord. Le principe de tous ces codes est d'avancer linéairement dans les tableaux et de retenir les éléments communs. Au passage, pour adcpc (et peut-être M@x), il existe maintenant un mode de tunnel dit conditionnel qui permet de construire un tableau en filtrant à partir d'une condition. J'aime bien aussi le code de Yann-50 qui économise vachement de place sur le diagramme !

@emmanuel-fr : il était écrit qu'il y aurait des tests avec des tableaux de taille très différentes. Mon algo 2 était plus optimisé pour ce cas de figure, mais finalement les tests que vous avez faits étaient sur des tableaux de taille identique, non ? Dans le cas de tailles différentes, il vaut mieux faire une recherche de chaque élément du petit tableau dans le grand, mais pas une recherche linéaire qui prend O(M) étapes, mais plutôt dichotomique en O(log(M)) étapes. Mon algo 2 est basé sur le code de la fonction Rechercher dans un tableau ordonné de la palette Mathématiques/Interpolation et extrapolation que j'ai intégré et modifié. Je suis surpris de voir qu'il marche aussi bien que l'algo1 dans le cas de tableaux de taille identique. Ce n'était pas le cas pour les petits tableaux fournis en exemple.

Par contre, j'avais fait un wrapper Intersection_MathieuPerrin qui décide tout seul de quel algo utiliser et surtout qui parallélise le code en découpant les tableaux. @emmanuel-fr, peux-tu le tester sur les grands tableaux en me disant le nombre de processeurs de ta machine ? Je suis curieux de voir le gain que ça peut représenter. Sur mon quadriprocesseur et avec les tableaux d'exemples, je n'avais qu'un gain de ~20-30%, loin du 4x auquel on pourrait s'attendre. Mais peut-être que sur des gros tableaux le gain est plus important...

[emmanuel-fr]

Bonsoir, merci pour ces explications ! Pour les tests, J'ai mis en pièce jointe votre fichier ZIP contenant tous les VI. Je referai des essais de mon coté sur mon PC.

[emmanuel-fr]

Merci thib_fr pour m'avoir encore envoyé votre code pour le fun !

Voici les résultats en utilisant les mêmes critères de test :

10 - Intersection_thib_fr.vi

Pour 100k

0,045285

0,049230

0,042489

Valide

10 - Intersection_thib_fr.vi

Pour 1k

0,001676

0,002394

0,001479

Valide