Recherche somme minimum
Je génère de nombreuses matrices contenant des nombres.
Je cherche la matrice dont la somme des éléments soit le minimum possible.
Avec une difficulté supplémentaire : selon la valeur de la somme sur une ligne donnée, le résultat à prendre en compte peut être minoré.
J'ai fait un algorithme qui, pour chaque matrice, parcourt systématiquement chaque ligne pour vérifier la condition, calcule la somme et si cette somme est inférieure à celle stockée temporairement, on conserve la matrice et ainsi de suite.
Pour quelques dizaines de matrice, c'est supportable.
Mais comme il arrive que j'ai plusieurs centaines de milliers de matrices, le temps de calcul explose
Je précise que je code en python.
Existe-t-il une fonction python qui permet de calculer la somme des éléments d'une matrice ?
J'ai pensé modifier l'algorithme en arrêtant le calcul en cours pour une matrice dès que la somme cumulée des lignes dépasse le minimum stockée en mémoire, mais cela ajoute autant de comparaison que de lignes à la place d'une seule comparaison à la fin du calcul pour la matrice : pas sûr que ce soit efficace.
Pour que ce soit plus clair, voici un exemple avec 2 matrices.
[1,2,3]
[0,0,0]
[1,2,0]
[0,0,5]
Premier calcul :
1 + 2 + 3 = 6
0 + 0 + 0 = 0
6 + 0 = 6
On stocke cette valeur et la matrice en temporaire.
Second calcul :
1 + 2 + 0 = 3
0 + 0 + 5 = 5
3 + 5 = 8
On compare à la valeur stockée en temporaire : supérieure, on ne retient pas.
Second calcul avec condition :
1 + 2 + 0 = 3
0 + 0 + 5 = 5 --- Condition : Somme > 4 : on retire 3 --> 5 - 3 = 2
3 + 2 = 5
On compare à la valeur stockée en mémoire : inférieure, on retient et on stocke dans le temporaire.
Connaissez-vous un algorithme plus rapide et/ou plus simple ?
Répondre avec citation
Envoyé par Nemerle
Partager