Discussion :

[Simon_e]

Bonjour,

J'ai un petit soucis de temps de calcul sur une matrice numpy, et j'aurais besoin d'aide.
J'ai une matrice de taille n*n ( 10 < n < 9000 environ) qui ne peut contenir que 3 valeurs : 0, 1 ou 2



0 = Noir
1 = Rouge
2 = Vert

Le but étant d'obtenir:



C'est à dire d'étendre le rouge (1) sur le noir (0) en définissant le vert (2) comme délimitation.

Un moyen assez direct de le faire serait:

Code :

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

1
2
3
4
5
 
for i in range(n):
    for j in range(n):
        if liste[i,j] == 1 and liste[i,j+1] == 0:
            liste[i,j+1] = 1

Le problème étant que c'est bien trop lent ! Réaliser les calculs un par un prend trop de temps. On peut penser à rajouter quelques lignes pour ne pas effectuer de calcul dans la zone entre la bordure et la ligne verte mais cela ne change pas le problème.

Je voulais donc savoir s'il y avait un moyen d'utiliser les fonctionnalités de numpy (notamment le multiprocessing sur les matrices) afin d'accélérer le tout.
Je m'en remets à vous.
Merci !

[wiztricks]

Je voulais donc savoir s'il y avait un moyen d'utiliser les fonctionnalités de numpy (notamment le multiprocessing sur les matrices) afin d'accélérer le tout.

Il y a certainement moyen de moyenner

Mais avant tout vous avez un problème d'algorithme à améliorer et à consulter la rubrique ad hoc.... puis si c'est encore trop lent, on peut ajouter des ressources avec du multiprocessing.

note: si je regarde vos images, je "vois" des lignes et des colonnes où on peut calculer des intervalles entre différents points rouges donnant les segments à changer de couleur. Produire les segments et changer de couleur peuvent être 2 étapes indépendantes à faire exécuter par plusieurs processus (en partitionnant le boulot sur des sous-ensembles de...).

- W

[Invité]

Salut !

Si je m'appelais Sve@r je te conseillerais d'utiliser un algorithme de remplissage ! ^^'
https://fr.wikipedia.org/wiki/Algori...0comme%20Paint.

J'avais pondu ça en début d'année :

(Evidemment c'est extrêmement ralenti pour voir comment ça marche, le script en lui-même est ultra performant et ne nécessite pas numpy (ma maigre expérience m'invite à ne pas utiliser numpy à cause de sa lenteur))

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
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
area = [[],[]]
start = (x,y) #de mémoire x c'est l'axe vertical et y l'axe horizontal
def get_all_valide_cases(pos, added, k):
    x, y = pos
    poles = [(x-1, y),(x,y-1),(x,y+1),(x+1,y)]
    next_cases = []
 
    k+=1
    for X, Y in poles:
        if X < 0 or Y <0:
            continue
        if (X, Y) not in added:
            try:
                if area[X][Y]==1 or area[X][Y]>k:
                    next_cases.append((X, Y, k))
                    added.append((X, Y))
            except IndexError:
                pass
 
    return next_cases, added
 
def main():
    path_to_go = [(start[0], start[1], 1)]
    added = [start,start]
 
    while path_to_go:
        x, y, k = path_to_go.pop(0)
 
        next_cases, added = get_all_valide_cases((x, y), added, k)
 
        for _ in next_cases:
            added.pop(0)
 
        path_to_go.extend(next_cases)
 
        area[x][y]=k

Mais il y a peut-être plus efficace ?

[Simon_e]

ma maigre expérience m'invite à ne pas utiliser numpy à cause de sa lenteur
?

L'algorithme es en effet intéressant. La raison pour laquelle j'utilise majoritairement des listes numpy sur ce programmes vient du fait que malgré le fait qu'elles sont effectivement plus lente en général sur les calculs, elles sont nettement plus rapide lors de leur création. Si tu dois créer une liste de taille n*n*3*2 (profondeur 4), ça sera (pour avoir tester à mes dépends) bien plus rapide sur numpy.

[Simon_e]

Il y a certainement moyen de moyenner

si je regarde vos images, je "vois" des lignes et des colonnes où on peut calculer des intervalles entre différents points rouges donnant les segments à changer de couleur. Produire les segments et changer de couleur peuvent être 2 étapes indépendantes à faire exécuter par plusieurs processus (en partitionnant le boulot sur des sous-ensembles de...).

- W

Effectivement, travailler sur des segments s'avère être très efficace, merci !