Matrices sous forme de tableaux à une dimension - Décallage variable

Version imprimable

Voir 40 message(s) de cette discussion en une page

Pour la postérité:

Code:

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;
		}
	}
}

10/07/2008, 10h06
Matthieu Brucher

Citation:

Envoyé par Plorf

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 ;)
10/07/2008, 11h58
Plorf

Travaillerais tu aussi avec BLAS ? :p
10/07/2008, 12h06
Matthieu Brucher

Pas pour le moment, mais tout est fait pour qu'on puisse le faire par la suite.
10/07/2008, 14h25
Plorf

Citation:

Envoyé par pseudocode

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

Citation:

Envoyé par pseudocode

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

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 :)
10/07/2008, 14h38
Zavonen

Citation:

Envoyé par Plorf

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

Peux tu donner un ordre de grandeur ?
10/07/2008, 14h46
Plorf

Citation:

Envoyé par Zavonen

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 :D

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.
10/07/2008, 14h58
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é

Citation:
Envoyé par pseudocode
Pour la postérité:
Code:

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; } } }
:king: t'es un roi :)

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

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

10/07/2008, 15h52
pseudocode

Citation:

Envoyé par Plorf

:king: t'es un roi :)

Appelez-moi "sire"... :P

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. :mouarf:
10/07/2008, 15h53
Zavonen

1 pièce(s) jointe(s)

Citation:

Envoyé par pseudocode

Bon courage pour coder l'algo de transposition in-place. :aie:
rien compris. 8O

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.
10/07/2008, 15h54
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é ;)
10/07/2008, 17h00
pseudocode

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

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. :roll:

Citation:

Envoyé par 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é ;)

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:

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:

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)

Citation:
Envoyé par pseudocode
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:

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:

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 ! :)

10/07/2008, 20h33
Zavonen

Oui Pseudocode, t'as raison j'ai écrit n'importe quoi !!!:oops:
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.

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:

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.

transposition in-place (suite)

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:

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()

11/07/2008, 09h52
pseudocode

Citation:

Envoyé par 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.

:applo:

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.

Voir 40 message(s) de cette discussion en une page