Discussion :

[cjacquel]

Bonjour,

Mon programme dois appeler des paramètres qui sont stockés dans un tableau de 4096x4096 integers.

Comment faire pour avoir rapidement ce tableau de valeurs dans la fonction de calcul.

J'utilise le c++

Merci,
Christophe

[valentin03]

Trier le tableau et le diviser en sections.
Et comme tu sais ce que tu cherche, cherche le dans la bonne section.
ça t'évitera de parcourir tout le tableau

[mach1974]

Il faut trier le tableau avec un bulle short

[tbc92]

Je ne sais pas si tu as trouvé ta réponse par ailleurs. Mais je ne suis même pas sûr de comprendre ce qui te bloque.
En tout cas, ce que ta question m'inspire, ce sont ces 2 mots clés : passage par adresse // passage par valeur.

Si tu passes l'adresse de ton tableau, le système n'a pas besoin de dupliquer ton tableau. L'adresse d'un tableau, c'est un entier système... et peu importe si le tableau fait 10x10, ou 4096x4096.

Passage par adresse, passage par valeur, dans le jargon C, ça devient 'Pointeur'.

Parmi les petits jouets autour de cette notion, si tu veux accéder à l'élément Tablo(i,j), tu pourras faire par exemple (code très approximatif, j'ai juste de très lointains souvenirs de C) :

Code :

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

1
2
3
4
x = &Tablo       // l'adresse du tableau
n =i*4096 + j             // On va sauter i lignes complètes , plus j éléments, on va donc sauter (i*4096+ j) éléments
y = x + n * sizeof(int) //   on veut sauter n entiers, il faut donc se déplacer de n * la taille d'un entier.    
resu = *y                   //  si resu est déclaré comme entier, resu contiendra la valeur de ce qui se trouve à cette adresse. Donc la valeur de Tablo(i,j)

[francortes]

si le tableau de 4096 * 4096 octets représente des valeurs de lumnance pour une image, ou des poids pour un réseau de neurones prenant des images 4K en entrée, il se peut que l'ordre [i, j] des valeurs soit important.

Il existe des structures de données comme les octrees, les quad-trees et les k-d trees qui me semblent ils permettrent de gérer des partitions dans un tel espace 2D.

un moteur de bases de données SQL rapide comme SQLite (local) ou PostgreSQL pourrait peut être stocker des points ou des partitions de points:

Code :

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

1
2
3
4
5
6
7
 
    CREATE TABLE points (
       frame_key: integer(11)
        col: integer,
        row: integer,
        greyscale_value: integer
    );

soit on stocke les points individuels dans la table, soit on fait des groupes de 256 * 256 points par exemple, en ajoutant un champ sérialisé sous forme de string pour les 65536 valeurs possibles par groupe, ce qui fera toujours (65536 / 256) * (65536 / 256) = 256 * 256 = 65536 groupes pour une image (à portée de performance d'un SGBD).

**********

une dernière idée: si on fait 65536 groupes de 65536 points on peut peut être utiliser deux HashMaps, une pour les partitions de lignes et une pour les partitions de colonne :

* chaque map est indexés par les entiers (au plus 256) dont on veut connaitre la position en termes de ligne et colonnes de groupe

* la valeur stockée dans la Map est un tableau de références de partition (ligne ou colonne) dans lesquelles apparait la valeur cherchée : par exemple quels sont les numéros de ligne des partitions dans lesquelles apparaissent la valeur 128 ?

* on calcule les produits cartésiens [partition_indedx_ligne] * [partition_index_colonne]

* on fait l'intersection les tableaux [lignes, colonne] constituant le résultat du produit cartésian pour trouver les partitions dans lesquelles il faut chercher les points

Il ne faut pas oublier de mettre à jour les Maps au moment de l'insertiton / maj d'une valeur datas.set(i, j, value))

Enfin c'est une idée,car: produit cartésien + intersection = aie, aie, pour les performances ! Il faut tester...

Voilà ce que cela m'inspire pour le moment.

A + F - E

[Guesset]

Bonjour tbc92,

...je ne suis même pas sûr de comprendre ce qui te bloque....

Je partage la même réflexion; 4096x4096 ne fait que 16 Mégapixels (un pixel sur 32 bits = un entier de base) ce qui est relativement faible aujourd'hui.

Code :

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

x = &Tablo       // l'adresse du tableau

Si Tablo est un tableau c'est aussi le pointeur sur Tablo[0] soit l'adresse du premier élément du tableau.

Aussi au lieu d'écrire x = &Tablo il faudrait écrire int * x = Tablo; ou pour faire inutilement compliqué int * x = &(Tablo[0]);
La première forme signifie que x pointe sur la même adresse que Tableau soit celle du premier élément. La seconde forme récupère l'adresse (&) du premier élément (Tablo[0]). C'est donc identique.

Salut

[Guesset]

Bonjour Francortes,

Soit on stocke les points individuels dans la table, soit on fait des groupes de 256 * 256 points par exemple...

La solution des damiers est une très bonne idée très utilisée dans les traitements d'images (et toujours avec des puissances de 2 pour les dalles ce qui peut augmenter le volume nécessaire au delà du volume utile si les dimensions ne sont pas des multiples de celles des dalles comme 4097x4097 par exemple ). Comme le stockage reste linéaire, il y a nécessairement un axe privilégié. Par exemple sous GIMP, le scroll horizontal est sensiblement plus rapide que le scroll vertical. Et si la machine est un peu surchargée on peut avoir le temps d'apercevoir les dalles du damier lors d'un réaffichage.

Les autres techniques (par exemple le hachage) sont rarement optimales pour un cas standard. En revanche pour des images ayant des propriétés particulières comme une image avec beaucoup de valeurs identiques (un dessin au trait sur du papier blanc par exemple) cela peut diminuer sensiblement les volumes utilisés, ce qui peut compenser (ou pas) une recherche plus complexe donc plus lourde.

Salut

[anadoncamille]

Je suis étonné que cette discussion ne soit pas résolue malgré la quantité de solutions proposée.

Que te manque-t-il ?

[cjacquel]

OK résolu.