Discussion :

[pseudocode]

Pour la postérité:

Code java :

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
 
void reorder(int[] m,int c,int l) {
	int n=l*c;
 
	// FIFO
	int[] fifo = new int[l];
	int poshead=0, posqueue=0;
 
	for(int i=(c-1);i<n;i++) {
		fifo[posqueue]=m[i];
		posqueue=(posqueue+1)%l;
 
		if ((i+1)%c==0) {
			m[i] = 0;
		} else {
			m[i] = fifo[poshead];
			poshead=(poshead+1)%l;
		}
	}
}

[Matthieu Brucher]

Je suis obligé de le faire en C, car c'est un wrapper

Merci de toutes vos réponses, je regarde ça tout à l'heure

Rien ne t'empêche d'avoir un ordre Fortran en C ! On fait du tratement d'image chez nous, notre conteneur C++ ets en ordre Fortran, la bibliothèque matricielle aussi

[Plorf]

Travaillerais tu aussi avec BLAS ? :p

[Matthieu Brucher]

Pas pour le moment, mais tout est fait pour qu'on puisse le faire par la suite.

[Plorf]

Oui, c'est une bonne optimisation car on connait déjà la taille max du fifo ( = nombre de lignes).

Je ne suis pas à la recherche de la solution optimale, mais il me faut quelque chose de relativement rapide. Disons que j'ai beaucoup de temps de calcul et je dois faire mieux que des solveurs d'algèbre linéaire commerciaux donc bon :p

Hum... sans doute, meme si ca ne m'a pas l'air evident. Je laisse ce genre d'optimisation comme exercice au lecteur.

Décallage par bloc
C'est ce que j'avais essayé de faire, mais je me marche dessus....
En gros le truc c'est que comme ta fifo qui se remplis de plus en plus, il faut que je décalle des blocs de plus en plus loin mais la taille ne varie pas, enfin bref, je m'étais fait vraiment chier... et d'ailleurs ça marche toujours pas :p XD

Je vais faire avec la méthode de fifo je pense

Merci en tout cas de toutes vos réponses

[Zavonen]

Parce que j'ai des très grosses matrices, je ne peux pas me permettre d'avoir deux fois la matrice en mémoire...

Peux tu donner un ordre de grandeur ?

[Plorf]

Peux tu donner un ordre de grandeur ?

En fait j'ai potentiellement des très grosses matrices :

Résolution d'algèbre linéaire :
Donc admettons qu'un problème ait 10 000 contraintes

Je dois en plus rajouter 10 000 colonnes
donc ça fait une petite matrice de 10 000 * 20 000 :/

Donc ca fait quelque chose genre humm dans ce cas : 200 000 000 Soit 200Go

Bon ok trop gros exemple, euuuh


5 000 contraintes

On a donc 5 Go... Sachant que j'ai d'autres trucs à côté.

bon en fait ça dépend du problème passé en arguments....


Je fais un solveur d'algèbre linéaire, et contrairement aux solveurs commerciaux je ne prends pas des matrices creuses, pour y gagner justement en utilisant BLAS pour le calcul.

[Plorf]

Je dois rajouter des colonnes car c'est sous la forme canonique.

(Algo révisé du simplex)

Les colonnes que je rajoute forme une matrice identité

[Plorf]

Pour la postérité:

Code java :

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
 
void reorder(int[] m,int c,int l) {
	int n=l*c;
 
	// FIFO
	int[] fifo = new int[l];
	int poshead=0, posqueue=0;
 
	for(int i=(c-1);i<n;i++) {
		fifo[posqueue]=m[i];
		posqueue=(posqueue+1)%l;
 
		if ((i+1)%c==0) {
			m[i] = 0;
		} else {
			m[i] = fifo[poshead];
			poshead=(poshead+1)%l;
		}
	}
}

t'es un roi

Merci à tous pour le temps passé à faire tout ça !!!

Merci aussi à Zavonen !!
Merci aussi à Matthieu Brucher !!

[pseudocode]

t'es un roi

Appelez-moi "sire"...


PS: un quart de page griffoné et 5 lignes de code, on ne peut pas dire que ca restera comme un de mes plus grands exploits.

[Zavonen]

Bon courage pour coder l'algo de transposition in-place.
rien compris.

La transposition d'une matrice rectangulaire en place n'est pas beaucoup plus difficile que dans le cas d'une matrice carrée.
Regarde l'image ci-jointe.
Tu transposes d'abord un carré, la suite n'est qu'une copie de blocs.

[Plorf]

Si dans le même style tu peux me griffoner l'équivalent pour enlever une colonne je suis preneur aussi :p

En gros c'est la même idée, décaller la dernière colonne à la fin, de façon qu'elle puisse être viré

[pseudocode]

@Zavonen: c'est sympa de m'expliquer la transposition de matrice.

Le problème c'est la transposition in-place, c'est à dire dans la même zone mémoire linéaire et sans utiliser de tampon intermédiaire.

Et là, c'est nettement moins évident... Ça mériterait même une petit défi.

[pseudocode]

Si dans le même style tu peux me griffoner l'équivalent pour enlever une colonne je suis preneur aussi :p

En gros c'est la même idée, décaller la dernière colonne à la fin, de façon qu'elle puisse être viré

Si c'est juste pour "enlever" une colonne, il suffit de faire une copie avec decalage. Les "L" derniers elements seront du garbage, mais comme c'est ceux que tu comptes supprimer ce n'est pas grave.

Code java :

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

1
2
3
4
5
6
7
8
9
10
 
public static void reorderreverse(int[] m,int c,int l) {
	int n=l*c;
 
	// copie avec decalage
	for(int i=(c-1),j=i;i<(n-l);i++,j++) {
		if ((j+1)%c==0) j++;
		m[i] = m[j];
	}
}

Code :

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

1
2
3
4
5
6
 
avant : [1, 2, 3, 0, 4, 5, 6, 0, 7, 8, 9, 0]
 
apres : [1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 9, 0]
                                    ~~~~~~~
                                   (garbage)

[Plorf]

Si c'est juste pour "enlever" une colonne, il suffit de faire une copie avec decalage. Les "L" derniers elements seront du garbage, mais comme c'est ceux que tu comptes supprimer ce n'est pas grave.

Code java :

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

1
2
3
4
5
6
7
8
9
10
 
public static void reorderreverse(int[] m,int c,int l) {
	int n=l*c;
 
	// copie avec decalage
	for(int i=(c-1),j=i;i<(n-l);i++,j++) {
		if ((j+1)%c==0) j++;
		m[i] = m[j];
	}
}

Code :

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

1
2
3
4
5
6
 
avant : [1, 2, 3, 0, 4, 5, 6, 0, 7, 8, 9, 0]
 
apres : [1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 9, 0]
                                    ~~~~~~~
                                   (garbage)

T'es un amour lol

Merci beaucoup encore une fois à tous !

[Zavonen]

Oui Pseudocode, t'as raison j'ai écrit n'importe quoi !!!
Voici quelque chose de plus sérieux:
Considérons une matrice aplatie de type (m,n) et sa transposée aplatie aussi de type (n,m) donc.
Il y a une correspondance entre les indices unidimensionnels qui est la suivante:
k --> f(k)=h= (k%n)*m + (k/n) à vérifier mais je crois que c'est bon.
On réalise la transposition "in-place" si après une manip le contenu de la case k est le contenu de la case f(k) (sans perte de données).
On commence donc à traiter les places mémoire de la façon suivante, on cheche le premier indice k tel que f(k) != k (dans notre cas ce sera 2).
appelons k0 cet indice.
On stocke la valeur de M[k0] puis on remplace M[k0] par M[f(k0)] , et on continue ainsi en écrasant M[f(f(k0)] avec M[f(k0)] on vérifie si f(f(k0))=k0, et ainsi de suite jusqu'à ce qu'un itéré de k0 soit égal à k0.
Alors on place M[k0] sur cet itéré, et j'affirme que tout est OK pour les cases d'indice k0, f(k0), f(f(k0), .....f(f(f(f...(k0))).
Comment continuer ?
Il faut trouver le premier indice k1 > k0 tel que: f(k1) !=k1 et k1 n'appartient à aucun des itérés précédents( ce qui suppose qu'on conserve les positions des cases marquées quelques part sous forme d'un tableau d'octets (ou même de bits..., il y a donc consommation de mémoire..). On stocke M[k1] et on recommence.
Le processus se termine, il est basé sur la décomposition d'une permutation en cycles.
Je l'ai fait à la main avec de petites matrices, ça fonctionne.
Seul problème la mémorisation des places traitées, je n'ai pas pu m'en affranchir.

[Zavonen]

La formule était fausse (je l'ai corrigée), l'idée était bonne.
On la reprend donc, jointe au fait que la permutation est en fait une involution.
Ce qui va donner en python:

Code Python :

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
L=[1, 2, 3, 4 ,5 ,6]
G=[]
 
def affiche (L,m,n):
    for i in range(0,m):
        for j in range(0,n):
            print L[i*n+j],
        print "\n"
 
 
def transpose (L,m,n):
    for k in range (0,m*n):
        if k not in G:
            i=k/n
            j=k%n
            h=j*m+i
            r=L[k]
            L[k]=L[h]
            L[h]=r
            G.append(k)
            G.append(h)
 
 
def main():
    affiche (L,3,2)
    transpose(L,3,2)
    affiche (L,2,3)
 
 
if __name__ == '__main__':
    main()

Mais il y a toujours ce problème du stockage des indices transposés.
On peut améliorer cela en prenant pour G une chaîne de caractères et n transposé se traduira par un 1 en position n dans la chaîne.
Mais enfin cela fait quand même m*n octets.
On peut aussi utiliser des bits, mais l'accès aux bits ralentira le stockage et les tests.

[Zavonen]

On peut s'affranchir du stockage des positions si on peut disposer d'un marqueur sur les cases du tableau.
Exemple: Supposons qu'on ne traite QUE des nombres >=0.
On peut alors utiliser les valeurs du tableau elles-mêmes pour marquer les positions transposées.
Voici un exemple où on ajoute une colonne de zéros à droite.

Code Python :

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
L=[1, 2, 3, 4 ,5 ,6]
 
def affiche (L,m,n):
    for i in range(0,m):
        for j in range(0,n):
            print L[i*n+j],
        print "\n"
 
 
def transpose (L,m,n):
    for k in range (0,m*n):
        if L[k]>=0:
            i=k/n
            j=k%n
            h=j*m+i
            r=-L[k]-1
            L[k]=-L[h]-1
            L[h]=r
            G.append(k)
            G.append(h)
    for k in range (0,m*n):
        L[k]=-L[k]-1
 
 
def main():
    global L
    affiche (L,3,2)
    transpose(L,3,2)
    L=L+[0]*3
    transpose(L,3,3)
    affiche(L,3,3)
 
 
if __name__ == '__main__':
    main()

[pseudocode]

On peut s'affranchir du stockage des positions si on peut disposer d'un marqueur sur les cases du tableau.
Exemple: Supposons qu'on ne traite QUE des nombres >=0.
On peut alors utiliser les valeurs du tableau elles-mêmes pour marquer les positions transposées.

Il y a meme des methodes recentes qui permettent de faire la transposition in-place de tout type de matrice (en ce basant sur des propriétés des cycles de permutations).

Le plus simple consiste quand meme à utiliser ta premiere méthode, en utilisant une zone tampon pour marquer les elements déjà parcourus. On a besoin d'un bit par element => m*n bits = m*n/8 octets.