Distance de Manhattan et matrice

Version imprimable

03/12/2015, 22h41
Aspic

Distance de Manhattan et matrice

Bonsoir,

Dans mon problème, j'utilise une matrice 2D représentant un terrain de jeu.
Par soucis d'optimisation, je n'ai pas voulu représenter ma matrice par un tableau 2D mais simplement par un tableau 1D.
En ayant le nombre de colonne, je peux donc retrouver ma matrice originale.

Considérons le terrain suivant 3x5 (3 lignes et 5 colonnes)

Citation:

1 2 3 4 5
6 7 8 9 10
11 12 30 31 40

Si je veux la distance de manhattan entre les points 10 et 30, je prends les coordonnées (1, 4) et (2, 2) et j'applique la formule : M = abs(1 - 2) + abs(4 - 2) = 3

Maintenant, en mémoire, ma représentation est la suivante :

Citation:

1 2 3 4 5 6 7 8 9 10 11 12 30 31 40

Comment appliquer la distance de manhattan dans ce cas ?

Merci :)

Bonne soirée
04/12/2015, 02h39
anapurna

tu te complique la vie la matrice 2d prend la même place en mémoire que le 1 d
mais si tu veut garder la linéarité il faut que tu calcule l'indice y
imagine que ta valeur soit en [3,3]
donc ton indice est x+(y-1)*L
donc dans note cas 3+(3-1)*5
=3+2*5 = 13
donc ta valeur ce trouve a la 13iem position

j’espère t'avoir mis sur la voie
04/12/2015, 10h12
wiwaxia

Distance de Manhattan et matrice

Bonjour,

Citation:

Envoyé par Aspic

Dans mon problème, j'utilise une matrice 2D représentant un terrain de jeu.
Par souci d'optimisation, je n'ai pas voulu représenter ma matrice par un tableau 2D mais simplement par un tableau 1D.
En ayant le nombre de colonnes, je peux donc retrouver ma matrice originale.
Considérons le terrain suivant 3x5 (3 lignes et 5 colonnes) ... Comment appliquer la distance de manhattan dans ce cas ?

La première réponse a ciblé l'essentiel ...

Citation:

Envoyé par anapurna

tu te compliques la vie la matrice 2d prend la même place en mémoire que le 1 d
... imagine que ta valeur soit en [3,3]

... mais peut-être aurait-il mieux valu proposer un couple de 2 valeurs différentes, par exemple (2, 4).

Pour repasser du terme de rang (k) de la liste indexée [1 ... N] à l'élément (i, j) de la matrice (LxC) contenant le même nombre de termes (N = L.C), il suffit d'un petit calcul d'arithmétique modulaire - puisque la descente d'une ligne augmente le rang (k) d'une quantité égale au nombre de colonnes (C):
i = 1 + ((k-1) DIV C) [ quotient de la division euclidienne ]
j = 1 + ((k-1) MOD C) [ reste de la division euclidienne ]
04/12/2015, 10h43
anapurna

salut ,

effectivement j'aurais pu donnée aussi cette solution mais vu l'heure de ma réponse, mon cerveau ne devez pas être a 100% de ses capacité
en fait tout dépend de ton point de départ.
j'ai supposé qu'il étais parti de son écran de jeux et donc de ces coordonnée en deux 2D
mais comme tu le démontre il est tout aussi facile de retrouver les coordonné à partir de l'indice du tableau linéaire

on a donc selon le cas les solution fournis précédemment
en gardant le même formalisme que le précédent post on aurais donc
ma proposition se traduirais donc comme ceci

Citation:

k = I+(J-1)*C

par contre je ne suis pas certain de ta notation ne serait ce pas plutôt

Citation:

J = 1 + ((k-1) DIV C) [ quotient de la division euclidienne ]
I = 1 + ((k-1) MOD C) [ reste de la division euclidienne ]

J donnant le nombre de lignes (pour moi c'est donc le Y)
I donnant la position sur la ligne (pour moi c'est donc le X)
prenons donc l'exemple proposé

Citation:

(2, 4) =>K := 2+(4-1)*5 = 2+3*5 = 17

cherchons donc les indices dans une matrice

Citation:

I = 1+((17-1) MOD 5) = 1+(16 MOD 5) = 1+1 = 2
J = 1+ ((17-1) DIV 5) = 1+(16 DIV 5) = 1+3 = 4

mes 2 cts
04/12/2015, 12h37
wiwaxia

1 pièce(s) jointe(s)

Distance de Manhattan et matrice

Salut,

Je n'avais aucun objection au sujet de la concision de ta première réponse. Je regrettais seulement la trop grande simplicité de l'exemple numérique (3, 3), dont il apparaît qu'il masquait sournoisement une divergence de notation beaucoup plus sérieuse.

Citation:

Envoyé par anapurna

... par contre je ne suis pas certain de ta notation ne serait ce pas plutôt ...
J donnant le nombre de lignes (pour moi c'est donc le Y)
I donnant la position sur la ligne (pour moi c'est donc le X)

Il a toujours été d'usage (et je ne crois pas que cela ait changé récemment) de localiser l'élément (i, j) d'une matrice en parlant d'abord de la i^me ligne, puis de la j^me colonne.
Le lien suivant est tout à fait explicite (le passage relatif aux définitions n'a pas pu être correctement imprimé)
http:// https://fr.wikipedia.org/wiki/Matrice_%28math%C3%A9matiques%29

Citation:

Dans ce cas, on dit que la matrice a m lignes et n colonnes, ou qu'elle est de dimension ou taille (m, n). En notant ai,j l'image d'un couple (i, j) par l'application A, la matrice peut alors être notée: A=(a_i,j),(1<=i<=m , 1<=j<=n)

Pièce jointe 194290
La correspondance (i, j) <---> (y, x) ne conserve pas l'ordre alphabétique, ce qui est parfois une source d'erreurs - je me plante ainsi de temps à autre lors de la programmation d'un page d'écran texte, en rédigeant de tête des instructions du genre:

Code:

Ecrire(x, y, 'Chaine .. ')

Le seul moyen (primaire, je l'avoue) de s'en prémunir est de penser au mot "colline".

Par contre, je ne vois pas bien comment une matrice (3x5) peut contenir un terme de rang = 17:

Citation:

prenons donc l'exemple proposé
(2, 4) =>K := 2+(4-1)*5 = 2+3*5 = 17
cherchons donc les indices dans une matrice
I = 1+((17-1) MOD 5) = 1+(16 MOD 5) = 1+1 = 2
J = 1+ ((17-1) DIV 5) = 1+(16 DIV 5) = 1+3 = 4

(2, 4) se situant à l'intersection de la 2^me ligne et de la 4^me colone, figure dans la liste au rang
k = j + (i-1)C = 4 + (1*5) = 9 , qui par la division euclidienne redonne:
i = 1 + (k-1) DIV C = 1 + 8DIV 5 = 1 + 1 = 2
j = 1 + (k-1) MOD C = 1 + 8 MOD 5 = 1 + 3 = 4
Les valeurs de (i) et (j) ont été permutées dans ton calcul ... Rien de pire que l'échange de symboles dans une formule !
04/12/2015, 13h10
anapurna

bonjour

c'est normal on ne part pas des même élément
je n'ai pas dis que la matrice étais de 3 par 5
j'ai juste repris tes éléments mais comme nous ne parlions pas de la même chose j'ai effectivement inversé les i et le j ...
étant développeur, l'utilisation de tableau ce font dans le sens Tbl[x,y] pour tout ce qui concerne le graphisme d'ou ma meprise
je reste cohérent avec moi même ;)

bon le principe est le même le résultat diffèrent c'est certain
ouais la permutation de symbole c'est pas cool :D
le principale c'est que l'on ai répondu a la question du demandeur

Bonjour,

Je ne savais pas qu'une matrice 2D avait la même taille mémoire qu'une matrice 1D, je pensais qu'il y aurait des pointeurs en plus pour créer la 2ème dimension... Merci pour l'info ;)

Pour mon problème, finalement, j'ai retrouvé les coordonnées des éléments grâce à la formule :
Code:

1 2 3 4 5 6 7 int x1 = (Position1 / col); int y1 = (Position1 % col); int x2 = (Position2 / col); int y2 = (Position2 % col); res = (std::abs(x1-x2) + std::abs(y1-y2));
Si on reprends mon tout premier exemple avec la matrice 3x5 et les deux points Position1 = 10 et Position2 = 30, je récupère bien les coordonnées (1, 4) et (2, 2)

En fait, ce que je voulais à la base, c'était appliquer la distance de Manhattan pour un tableau 1D sans repasser par les coordonnées mais uniquement avec les valeurs dans le tableau (mais ce n'est peut être pas possible).

Merci :)

06/12/2015, 11h55
dourouc05

Citation:

Envoyé par Aspic

Je ne savais pas qu'une matrice 2D avait la même taille mémoire qu'une matrice 1D, je pensais qu'il y aurait des pointeurs en plus pour créer la 2ème dimension... Merci pour l'info ;)

Ça dépend fortement de l'implémentation. En C, si tu fais deux couches de malloc() (un tableau de tableaux), oui, tu auras un vecteur de pointeurs inutile (et qui nuira à la performance de l'application, peut-être de manière perceptible, de par les déréférencements et la potentielle perte de localité pour les accès en mémoire). Par contre, avec MATLAB, inutile de penser à ces détails. Dans tous les cas, ça n'est pas sûr que ça ait un impact dans ton cas ;).

Citation:

Envoyé par dourouc05

oui, tu auras un vecteur de pointeurs inutile (et qui nuira à la performance de l'application, peut-être de manière perceptible, de par les déréférencements et la potentielle perte de localité pour les accès en mémoire). Par contre, avec MATLAB, inutile de penser à ces détails.

boff pas vraiment.. En C tu alloues m*n d'un coup, et tu gères.. ou tu fais comme tu décris..
Mais voir plus bas...

Citation:

Envoyé par Aspic

Je ne savais pas qu'une matrice 2D avait la même taille mémoire qu'une matrice 1D, je pensais qu'il y aurait des pointeurs en plus pour créer la 2ème dimension... Merci pour l'info ;)

Pour mon problème, finalement, j'ai retrouvé les coordonnées des éléments grâce à la formule :
...
En fait, ce que je voulais à la base, c'était appliquer la distance de Manhattan pour un tableau 1D sans repasser par les coordonnées mais uniquement avec les valeurs dans le tableau (mais ce n'est peut être pas possible).

En fait, tu peux passer par un tableau 1D...

Que ce soit ce que dourouc propose ou ce que je cite plus haut, tu peux effectivement optimiser un tableau 2D en un tableau 1D.. A CONDITION que tes opérations se passent sur des éléments successifs..

Reprenons ce qui se passe réellement dans le processeur :

Soit un élément mathématique d'une matrice M de dimension (m,n), M[i,j].
Si on a un adressage 2D "à la C", c'est à dire 1 tableau 1D (m) de tableaux 1D (n), on aura à calculer :

l'adresse de départ du tableau 1D i : i*taille du pointeur de type + adresse de base (ad_dep)
l'adresse de départ de l'élément j dans ce tableau : j*taille du type + adresse de départ

On a donc pour chaque élément référencé 2 multiplication plus 2 additions.

En mathématique, on aura m[i,j] puis par exemple m[i][j+1]. En info, avec la structure ci-dessus, pour CHACUN de ces 2 éléments on aura donc 2 multiplications ET 2 additions.
Si maintenant on prend un tableau 1D :

adresser l'élément m[i,j] se fera par : i*n*taille du pointeur de type + j*taille du type + adresse de base (donc ici 3 multiplications et 3 additions).

MAIS si on ne fait que jongler avec les adresses , pour passer de m[i,j] a m[i,j+1], il suffira d'incrémenter le pointeur de 1.

donc, si tes calculs impliquent des -1 ou +1, que ce soit en ligne ou en colonne, il est beaucoup plus rapide de se servir de pointeurs dans un tableau 1D que de l'adressage par défaut dans un tableau 2D.

Si par exemple tu veux explorer 1 tableau 2D "sous forme d'un tableau 1D" :

A chaque début de ligne : calculer l'adresse du début et stocker le pointeur (par un des 2 calculs plus haut, de toutes façons il n'est fait qu'une fois par ligne)
assigner le pointeur de colonne à ce pointeur
incrémenter le pointeur

Dans d'autres langages tu as la même chose (cachée), que ce soit en Fortran, en matlab ou n'importe quel langage, l'accès à des éléments d'un tableau 2D (ou xD) se fait à chaque fois par un calcul d'adresse.

Donc, une réelle optimisation passe par du 1D, mais à condition que ça puisse référencer des éléments/lignes voisin(e)s.

Exemple en C :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 int *image, *pligne, *pcol ; pligne = image ; for ( i = 0 ; i < m ; i++ ) { pcol = pligne ; for ( j = 0 ; j < n ; j++ ) { *pcol = ...... ; *pcol++ ; } pligne = pligne + n*sizeof(int) ; }
Bien entendu on peut sauvegarder des pointeurs sur les lignes précédentes (si par exemple on veut aller à i-2), ou suivantes, etc etc..) Mais du coup on ne fait qu'une seule fois le calcul d'adresse, et après on ne fait qu'une addition.
Citation:

Envoyé par dourouc05

Dans tous les cas, ça n'est pas sûr que ça ait un impact dans ton cas ;).

LOL oui c'est vrai.. :D