Calcul efficace avec des tableaux

**khaourantin** · 08/09/2011, 10h19

Bonjour,

J'ai une grande quantité de calculs à faire sur des tableaux de réels : additions, multiplication par des constantes et recherche de maximum.

Est ce qu'il existe une solution plus efficace en terme de temps de calcul que de parcourir le tableau pour faire les opérations lignes à lignes? J'ai essayé avec un tableau classique, je récupère une erreur :

l'opérateur '*' n'est pas défini pour les types 'Tableau à 1 dimension(s) de Double et 'Double'.

J'ai quelque chose de similaire pour l'addition de tableau...

Il me semble par exemple qu'avec matlab faire une addition ou multiplication par une constante d'un vecteur se fait en O(1), bien sur si je le fais membre à membre c'est en 0(taille du tableau).

J'ai trouvé un type vector en VB.NET, mais ça ne semble être qu'à deux dimensions, mes calculs sont à faire sur des vecteurs à 24 lignes.

Question subsidiaire :
Originellement mes données sont stockées dans des datatables, quitte à faire les opérations ligne à ligne est ce que je gagnerais du temps de calcul à les transférer dans tableau ou le temps d'accès et de calcul est le même si je fais les opération directement avec mes datatables?

Merci de votre aide

**Pol63** · 08/09/2011, 11h05

tu peux rajouter une colonne dans ton datatable et faire un truc du genre
ca évitera de perdre du temps pour une recopie inutile
après niveau temps d'accès à une ligne, je pense qu'il n'y a pas énormément de différence, sauf si tu fais plusieurs accès par tour de boucle au lieu d'un comme ci après

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for each row in datatable 
  row.item(nouvellecolonne) = row.item(une colonne) * row.item(une autre colonne)
next

si tu as énormément de ligne tu peux paralléliser le tout avec plusieurs thread (sur le framework 4 : parallel.foreach ; avant le 4 : voir threadpool)

**tomlev** · 08/09/2011, 11h18

Envoyé par khaourantin

Est ce qu'il existe une solution plus efficace en terme de temps de calcul que de parcourir le tableau pour faire les opérations lignes à lignes?

Bah non, tu es bien obligé de lire toutes les valeurs pour pouvoir faire des calculs dessus...

Envoyé par Pol63

tu peux rajouter une colonne dans ton datatable et faire un truc du genre
ca évitera de perdre du temps pour une recopie inutile
après niveau temps d'accès à une ligne, je pense qu'il n'y a pas énormément de différence, sauf si tu fais plusieurs accès par tour de boucle au lieu d'un comme ci après

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for each row in datatable 
  row.item(nouvellecolonne) = row.item(une colonne) * row.item(une autre colonne)
next

Euh, pas la peine de faire si compliqué

Avec une colonne calculée :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

datatable.Columns.Add("NouvelleColonne", GetType(Double), "UneColonne * UneAutreColonne")

La nouvelle colonne se met à jour automatiquement en fonction des colonnes dont elle dépend.

**khaourantin** · 08/09/2011, 14h20

Merci de vos réponses, mais ces solutions ne s'appliquent pas à mon problème:

Les données que je traite viennent en fait de plusieurs datatable différentes, et il ne suffit malheureusement pas de sommer colonne à colonne dans une même datatable. Ou alors il faudrait que je revoit vraiment toute la structure de mes données...

Dans la classe Array il y a une méthode ForEach, qui requiert un argument de type Action, qu'est ce que c'est qu'une 'Action'? Comment implémenter la multiplication membre à membre comme une 'Action'? Est ce que vous pensez que ça pourrait me servir?

**Pol63** · 08/09/2011, 14h31

plutot que d'utiliser des datatables, il aurait mieux fallu faire de la poo, ca aurait été simple à écrire et lisible

action est un délégué, qui demande un pointeur vers une sub (ou le code d'une sub anonyme depuis le framework 4)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
dim a as new action(of integer)(addressof masub)
a.invoke(5)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
private sub (a as integer)
 'code
end sub

bref ca ne devrait pas te servir

après il nous faudrait le détail du calcul, surtout quelles colonnes de quelles dt tu utilises

**MABROUKI** · 08/09/2011, 20h07

bonjour khaourantin
Bah il te reste la biblitheque VNI IMSL CSharp de Rogue Wave mais payante .
Multiplication de matrice,addition, soustraction ,calcul de l'inverse.....etc...
Elle comporte meme un raccourci vers Excel pour la sortie graphique.......
Sur ce lien un apercu de IMSL VNI:http://www.google.fr/url?sa=t&source...SSwPuxeTLGsRGg

bon code.................

**khaourantin** · 09/09/2011, 11h37

Je vais essayer de détailler les calculs que je fais :

L'objectif de l’algorithme est de déterminer la puissance électrique appelée heure par heure dans un village.
Pour chaque type d'appareil: TV, frigo, lampe etc, j'ai un datatable de 24 ligne et 3 colonnes. Chaque colonne correspond à un scenario différent d'utilisation, chaque ligne contient la puissance appelée pour l'heure en question.

Les profils de consommations de chaque appareil n'est pas le même suivant le standing du ménage qui s'en sert (les riches ont des TV à écrans plasma, les pauvres des tubes cathodiques, les riches allument la TV 10h/jr les pauvre 8hr/jr), j'ai un datatable de consommation horaire par standing (bas, moyen haut)

Chaque classe de ménage (standing) a un nombre moyen différent d'appareil (les riches auront 5,2 TV, les pauvres 0,3...)

j'ai le même type de données pour les commerces et activités présentent dans un village

Il faut que j’agrège toutes ces courbes pour connaitre la courbe de puissance totale par village.

Là où je commence à faire beaucoup de calcul c'est que je veux connaitre cette courbe année par année sur 20 ans, et pour plusieurs milliers de villages. Chaque village a un nombre de ménage de chaque standing qui évolue année par année.

Pour être tout à fait précis, je ne cherche pas à avoir toute la courbe sur 24hr mais seulement le maximum et l'aire de cette courbe.

Pour l'instant mon algorithme fonctionne de la manière suivante :

Je commence par initialiser des vecteurs (double()) pour chaque appareil, chaque scénario et chaque standing à partir de tous mes datatables puis je lance ma boucle:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
        For v = 0 To nbVillage
            DeterminationNombre() = NombreDePersonne(v)
            For a = 0 To nbAnnee
                NbPauvre(a) = DeterminationNombre(Pauvre, a)
                NbMoyen(a) = DeterminationNombre(Moyen, a)
                NbRiche(a) = DeterminationNombre(Riche, a)
                For s = 0 To nbScenario
                    For h = 0 To nbHeure
                        CourbeTotale(h, s) = CourbePauvre(h, s) * NbPauvre(a) + CourbeMoyen(h, s) * NbMoyen(a) + CourbeRiche(h, s) * NbRiche(a)
                    Next
                    ConsoDePointe(a,v,s)=TrouvePointe(CourbeTotale(s))
                Next
            Next
        Next

Le nombre de personne de chaque classe dépends du village et de l'année,
Ce que je voulais faire avec mes vecteurs était de me passer de la dernière boucle. Chaque courbe de charge aurait été représentée par un vecteur et j'aurais juste eu à additionner mes vecteurs CourbePauvre/Moyen/Riche avec les bons coefficients multiplicatifs...
Sachant que ces vecteurs CourbePauvre/Moyen/Riche sont initialisé avant d'entrer dans mes boucles villages et années, dans les boucles je ne les modifies pas, seuls les coefficients NbPauvre/Moyen/Riches changent d'année en année.

Pour l'instant mon calculs prends quelques minutes si j'ai 1500 villages, et que je calcule seulement 3 ou 4 ans sur les 20 ans de la période. C'est encore trop il faudrait que je passe sous la minute...

Je pense que je vais me pencher sur la parallélisation avec plusieurs thread, le problème c'est que j'y connait rien... Pourriez vous m'indiquer de bons tutos sur la question?

**DonQuiche** · 09/09/2011, 15h17

Bonjour à toi.

Passons en revue les solutions :
* Désactiver les boundaries checks (à chaque accès d'un élément, le framework vérifie l'index par rapport aux bornes inférieures et supérieures du tableau). Pour ça on peut soit passer par du code unsafe, soit, en C# du moins (mais j'imagine que ça fonctionne aussi en VB), utiliser une boucle qui soit strictement : "for(int i = 0; i < array.Length; i++)". Attention, toute variante rétablira les vérifications (on peut seulement changer le nom de la variable d'itération).
* Utiliser un wrapper vers une biblio de calcul matriciel en C, comme la célèbre bibilio mathématique gpl dont j'ai oublié le nom et pour laquelle il existe justement un tel wrapper.
* La parallélisation.
* L'utilisation du GPU.

Accessoirement, le code présenté pourrait déjà être aisément accéléré : plutôt que d'accéder à chaque itération aux éléments NbPauvre(a), NbMoyen(a) et NbRiche(a), on peut les stocker au préalable dans des variables locales et virer 6 des 23 branchements conditionnels de la boucle centrale. Ensuite, les tableaux bidimensionnels sont typiquement plus lents que les unidimensionnels, on préfèrera donc ces derniers. Voire des jagged arrays qui se prêteraient bien au code proposé (on peut mettre en cache les sous-tableaux dans des variables locales juste avant le dernier for). Ces seuls changements devraient permettre de multiplier la vitesse par deux ou trois. Accessoirement, on peut aussi revoir l'ordre des boucles pour rendre certaines optimisations encore plus efficaces. Enfin, des double sont-ils vraiment nécessaires ?

Avec les astuces du dernier paragraphe et la structure "for" proposée au début, on doit pouvoir multiplier la vitesse par 5 à 10.

**Pol63** · 09/09/2011, 17h04

unsafe en vb.net, je ne pense pas que c'est faisable ...

**khaourantin** · 09/09/2011, 17h11

Merci de tous ces conseils, je vais tester tout ça et vous tenir au courant.

Je viens de découvrir comment utiliser le backgroundworker, je sens que je vais en utiliser qqn pour essayer d'améliorer la vitesse.

J'ai aussi vu comment utiliser les threads, mais si les methodes de calculs qu'ils appellent ne peuvent pas prendre d'argument ni sortir de résultat je ne vois pas bien comment les utiliser dans mon cas...

**DonQuiche** · 09/09/2011, 17h29

Envoyé par khaourantin

Merci de tous ces conseils, je vais tester tout ça et vous tenir au courant.

Je viens de découvrir comment utiliser le backgroundworker, je sens que je vais en utiliser qqn pour essayer d'améliorer la vitesse.

J'ai aussi vu comment utiliser les threads, mais si les methodes de calculs qu'ils appellent ne peuvent pas prendre d'argument ni sortir de résultat je ne vois pas bien comment les utiliser dans mon cas...

Il suffit de passer une méthode d'instance.

Cela dit, j'insiste, il y a des solutions plus simples à faire avant d'avoir recours au parallélisme. Qui plus est, concernant cette dernière solution, le mieux est de passer par Parallel.For au niveau de la boucle supérieure.

**Pol63** · 09/09/2011, 18h00

ne pas faire de multithreading de nos jours devrait être interdit

il y a plusieurs années qu'intel, microsoft et les autres ont prévenu que les fréquences n'augementeront pas énormément alors que le nombre de core ne cessera de grandir (quelques centaines de cores dans quelques années surement)

un thread peut tout à fait sortir un résultat, le code que tu as déjà écrit s'exécute sur un thread de toute façon, le thread principal de ton application, et il fait plein de choses
on peut faire la même chose à partir d'un autre thread, hormis modifier l'interface

le threadpool est à mon avis la solution, tu lui dit que tu veux un thread pour chaque village ou année ou village/année, tu lui donnes un nombre de thread maxi (tant qu'à faire le nombre de core du pc, trouvable sur une classe en propriété shared)
il lance x threads en même selon ce que tu lui as dis, et quand un thread se termine il lance le suivant automatiquement tout en ne pas dépasser le nombre fixé

en répartissant ainsi le travail, sur un serveur avec 16 cores logiques tu mettras 16x moins de temps (environ. y a toujours une légère différence entre la théorie et la pratique)

**Pol63** · 09/09/2011, 18h16

j'ajouterais que le multithreading peut dans certains cas être plus complexe
quand on fait des calculs qui dépendent du résultat d'autres calculs il faut gérer l'attente de la fin d'un thread pour continuer

certaines chosent peuvent causer des bugs
par exemple lors d'un for each sur une collection, si un autre thread fait collection.add(nouvel element) ca plantera le thread du for each car la collection a changé
ou encore i = i + 1
si i vaut 1 et que 2 threads font ca, ca devrait faire 3 mais si les 2 threads sont réellement en même temps ca fera 2 car il vont lire i (1) ajouter et ensuite stocker la valeur
pour ca il y a des solutions pour bloquer un thread à un endroit (synclock, readerwriterlock, incrément atomique etc...)

**DonQuiche** · 09/09/2011, 21h58

Envoyé par Pol63

il y a plusieurs années qu'intel, microsoft et les autres ont prévenu que les fréquences n'augementeront pas énormément alors que le nombre de core ne cessera de grandir (quelques centaines de cores dans quelques années surement)

Attention tout de même, ce n'est pas parce que les fréquences stagnent que la vitesse des coeurs reste constante. Après, si une appli ne fait pas de multithreading, au moins laisse t-elle les autres coeurs pour les autres applis, tout dépend des besoins. Et quand tu vois que la plupart des utilisateurs n'ont que deux coeurs...

**khaourantin** · 12/09/2011, 09h17

Je pense que je vais me lancer dans le multithreading, j'imagine qu'il est plus efficace de créer soit même ses threads mais je me demandais si l'utilisation de plusieurs backgroundworker pouvait avoir le même résultat?

Je me suis rendu compte que la moitié du temps je faisais... 0 + 0 = 0 ..., déjà en sautant cette étape je devrais gagner du temps...

**Pol63** · 12/09/2011, 09h19

le backgroundworker est un encapsulation d'un thread et tout ce qui est souvent nécessaire avec un thread (annulation, report d'avancement, modification de l'ui ...)

donc thread ou backgroundworker ca revient à peu près au même

**DonQuiche** · 12/09/2011, 12h20

Envoyé par khaourantin

Je pense que je vais me lancer dans le multithreading, j'imagine qu'il est plus efficace de créer soit même ses threads mais je me demandais si l'utilisation de plusieurs backgroundworker pouvait avoir le même résultat?

Créer soi-même les threads n'est pas forcément le plus efficace, Parallel.For serait un meilleur pari car ce dernier détermine lui-même, empiriquement, le nombre de threads à utiliser, via une montée en charge progressive. Sur un calcul de plusieurs minutes, c'est très efficace.

Cela dit, faire les choses à la main est instructif et un bon exercice pédagogique.

Je me suis rendu compte que la moitié du temps je faisais... 0 + 0 = 0 ..., déjà en sautant cette étape je devrais gagner du temps...

Ça semble être une très mauvaise idée.

En effet, le compilateur a plusieurs façons de traduire le code que tu écriras en x86. Dans le meilleur des cas, il utilisera l'instruction ftst (tester si le nombre est nul) avant d'insérer un branchement conditionnel. En soi c'est plus rapide qu'une soustraction mais les branchements conditionnels de ce genre tendent à mal se marier avec le pipelining : nos processeurs débutent le traitement des instructions successives (ou qu'ils croient successives d'après leurs prédictions sur les branchements conditionnels intermédiaires) avant que l'instruction en cours ne soit terminée. En clair : cette optimisation a toutes les chances de ne pas en être une et elle obcurcit le code.

Dans le pire des cas, le compilateur générer un code qui testera si x est inférieur à y, avec y = 0. C'est à dire qu'il soustraira 0 de x puis regardera le signe du résultat. Autrement dit tu auras fait une soustraction pour éviter une soustration.

Si tu cherches des optimisations, je t'invite plutôt à regarder mes suggestions précédentes. Après, tu peux tester celle-ci mais même si elle se révélait être bénéfique, ce ne serait que de peu.

**khaourantin** · 15/09/2011, 09h20

2ms!!

C'est le temps nécessaire à l’exécution d'une boucle sur 20 ans pour un village, la semaine dernière quand j'ai posté pour la première fois il me fallait 10 fois plus de temps...

cette réduction drastique je la dois:
-à l'utilisation de backgroundworker (2 pour l'instant)
-à l'utilisation de jagged array, (le code unsafe et la simplification des boucle for ne marche pas en vb.net)
-à l'utilisation de mes propres objets pour la structure de donnée, au début j'avais moult datatable, ça ralenti énormément le calcul.

Merci de vos conseils, je passe en résolu!