IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Tableau de 4096x4096


Sujet :

Algorithmes et structures de données

  1. #1
    Membre averti
    Profil pro
    Inscrit en
    avril 2005
    Messages
    898
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : avril 2005
    Messages : 898
    Points : 363
    Points
    363
    Par défaut Tableau de 4096x4096
    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

  2. #2
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    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
    Savoir pour comprendre et vice versa.

  3. #3
    Membre régulier
    Profil pro
    Inscrit en
    février 2010
    Messages
    84
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : février 2010
    Messages : 84
    Points : 109
    Points
    109
    Par défaut Tri à bulle o ln n
    Il faut trier le tableau avec un bulle short

  4. #4
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    3 268
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 3 268
    Points : 7 495
    Points
    7 495
    Par défaut
    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)
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  5. #5
    Membre à l'essai
    Homme Profil pro
    Développeur Web
    Inscrit en
    juin 2018
    Messages
    31
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : juin 2018
    Messages : 31
    Points : 21
    Points
    21
    Par défaut
    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

  6. #6
    Membre expérimenté

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    482
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 482
    Points : 1 516
    Points
    1 516
    Par défaut C et les pointeurs récalcitrants
    Bonjour tbc92,
    Citation Envoyé par tbc92 Voir le message
    ...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.

    Citation Envoyé par tbc92 Voir le message
    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
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  7. #7
    Membre expérimenté

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    482
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 482
    Points : 1 516
    Points
    1 516
    Par défaut Pavé de bonnes intentions
    Bonjour Francortes,

    Citation Envoyé par francortes Voir le message
    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
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

Discussions similaires

  1. trier un tableau et compter des elements du tableau
    Par remi51 dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 17/06/2002, 16h51
  2. Réponses: 2
    Dernier message: 27/05/2002, 19h46
  3. verification de doublons dans un tableau
    Par bohemianvirtual dans le forum C
    Réponses: 11
    Dernier message: 25/05/2002, 12h21
  4. transmision de tableau en parametre
    Par Horus dans le forum C++Builder
    Réponses: 3
    Dernier message: 16/05/2002, 11h15
  5. Réponses: 4
    Dernier message: 13/05/2002, 16h43

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo