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 :

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


Sujet :

Algorithmes et structures de données

  1. #1
    Membre habitué
    Profil pro
    Inscrit en
    Juin 2007
    Messages
    116
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France

    Informations forums :
    Inscription : Juin 2007
    Messages : 116
    Points : 149
    Points
    149
    Par défaut Matrices sous forme de tableaux à une dimension - Décallage variable
    Bonjour, j'ai un problème qui peux paraître tout bête mais qui me prend le chou depuis une journée et demi....

    Le problème est simple :
    J'ai une matrice schématisée sous forme d'un tableau à une seule dimension
    Donc la matrice :
    1 2 3
    4 5 6
    7 8 9

    Est en mémoire sous la forme 1 2 3 4 5 6 7 8 9

    Je souhaite ajouter une colonne
    la mémoire alloué est donc à la fin, nous avons donc

    1 2 3 4 5 6 7 8 9 0 0 0
    Soit
    1 2 3 4
    5 6 7 8
    9 0 0 0

    Il me faut donc décaller pour retomber sur mes pieds.

    Le problème c'est que le décallage est variable...

    C'est à dire qu'il faut décaller 9 de 2 crans vers la droite, la ligne du dessus de 1, et pas celle d'au dessus.

    Comment faire afin d'avoir
    1 2 3 0
    4 5 6 0
    7 8 9 0

    Merci de m'aider, je coince complétement....

    Merci d'avance

  2. #2
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 76
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Points : 1 913
    Points
    1 913
    Par défaut
    Ne pas mettre les zéros à la fin mais sur toutes les positions multiples de 3.
    Mais si l'opération est fréquente, le mieux est de:
    • transposer
    • ajouter à la fin
    • transposer à nouveau

    Cela marche dans tous les cas de figure.
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  3. #3
    Membre habitué
    Profil pro
    Inscrit en
    Juin 2007
    Messages
    116
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France

    Informations forums :
    Inscription : Juin 2007
    Messages : 116
    Points : 149
    Points
    149
    Par défaut
    Mais au niveau complexité y'a pas photo non ?
    Je suis en 2 * n^2 avec ta méthode ?

  4. #4
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    Bonjour,

    si tu souhaites avoir le meilleur gain en complexité, pourquoi ne pas allouer une nouvelle matrice à la bonne dimension, la remplir comme il se doit (O(N)) désallouer l'ancienne et pointer vers la nouvelle ?
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  5. #5
    Membre habitué
    Profil pro
    Inscrit en
    Juin 2007
    Messages
    116
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France

    Informations forums :
    Inscription : Juin 2007
    Messages : 116
    Points : 149
    Points
    149
    Par défaut
    Parce que j'ai des très grosses matrices, je ne peux pas me permettre d'avoir deux fois la matrice en mémoire...

    A la base je le faisais avec des memmoves mais j'ai des bugs......
    Mon but c'est d'avoir des perfs, car l'opération peux être effectués de très nombreuses fois. (c'est principalement une phase d'initialisation).


    Mais à défaut, la méthode proposé est très simple à mettre en place

  6. #6
    En attente de confirmation mail
    Inscrit en
    Octobre 2007
    Messages
    285
    Détails du profil
    Informations personnelles :
    Âge : 42

    Informations forums :
    Inscription : Octobre 2007
    Messages : 285
    Points : 348
    Points
    348
    Par défaut
    Bonjour Plorf,

    des petites questions pour affiner le problème :
    L'ajout de colonne est toujours à droite ? ou elle peut se faire à n'importe quelle position ?
    Est-ce qu'il y aussi besoin d'ajouter des lignes ?

    Suivant le cas, l'optimisation ne se fait pas de la même manière...

  7. #7
    Membre habitué
    Profil pro
    Inscrit en
    Juin 2007
    Messages
    116
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France

    Informations forums :
    Inscription : Juin 2007
    Messages : 116
    Points : 149
    Points
    149
    Par défaut
    J'ai aussi besoin d'ajouter des lignes mais c'est des fonctions différentes donc je peux faire différement

    En fait c'est en C, et l'agrandissement se passe via un realloc, donc toujours à la fin normalement (vu que au besoin l'OS fait un memcopy).

    L'ajout de colonne est toujours sur la dernière.

    La méthode de la transposé est pas mal car très simple à mettre en oeuvre, mais j'ai peur qu'elle soit un peu lente....

  8. #8
    Expert éminent sénior

    Avatar de Djug
    Homme Profil pro
    Inscrit en
    Mai 2007
    Messages
    2 980
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : Algérie

    Informations forums :
    Inscription : Mai 2007
    Messages : 2 980
    Points : 17 970
    Points
    17 970
    Par défaut
    petit algorithme (peut etre que sa va marcher)

    on prend un entier cpt initialisé à 0

    |pour i allant de 1 a nb_ligne*nb_colonne faire
    |
    | si cpt # nb_colonne alors cpt++
    | |
    | sinon decaler; avancer ;cpt=0;i++;
    | |
    | FinSi
    |
    | avancer
    |FinPour

  9. #9
    Membre habitué
    Profil pro
    Inscrit en
    Juin 2007
    Messages
    116
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France

    Informations forums :
    Inscription : Juin 2007
    Messages : 116
    Points : 149
    Points
    149
    Par défaut
    Citation Envoyé par Djug_ Voir le message
    petit algorithme (peut etre que sa va marcher)

    on prend un entier cpt initialisé à 0

    |pour i allant de 1 a nb_ligne*nb_colonne faire
    |
    | si cpt # nb_colonne alors cpt++
    | |
    | sinon decaler; avancer ;cpt=0;i++;
    | |
    | FinSi
    |
    | avancer
    |FinPour
    Je test demain et je te dit

  10. #10
    Expert éminent sénior
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 242
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 242
    Points : 36 699
    Points
    36 699
    Par défaut bourrin?
    Pourquoi ne pas allouer une matrice qui aurait le bon nombre de colonnes dès le départ puis de tracker les colonnes 'valides'.
    Ca devrait éviter pas mal de recopies, non?
    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  11. #11
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Si Zavonen a un bon algo de transposition in-place, je suis preneur.

    Sinon je propose d'utiliser un FIFO comme accumulateur pour réordonner la matrice.

    En java ca ferait ca:
    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
     
    void reorder(int[] m,int c,int l) {
    	int n=l*c;
     
    	// FIFO
    	LinkedList<Integer> fifo = new LinkedList<Integer>();
     
    	for(int i=(c-1);i<n;i++) {
    		fifo.addLast(m[i]);
    		if ((i+1)%c==0)
    			m[i] = 0;
    		else
    			m[i] = fifo.removeFirst();
    	}
    }

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    int[] m = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0};
    reorder(m, 4, 3);
    // résultat -->  m=[1, 2, 3, 0, 4, 5, 6, 0, 7, 8, 9, 0]
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  12. #12
    Membre habitué
    Profil pro
    Inscrit en
    Juin 2007
    Messages
    116
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France

    Informations forums :
    Inscription : Juin 2007
    Messages : 116
    Points : 149
    Points
    149
    Par défaut
    Je remet dans son contexte (je n'ai pas le choix)

    c'est en C, c'est une matrice qui est sous forme de double* !
    Donc c'est un grand tableau à une dimension !!

    Donc une fifo ne marche pas dans mon cas. Il faut que je recode le décallage à la main sinon... ce qui au niveau perf me parais pas forcément top....


    Et c'est dans une librairie d'interfaçage, c'est pour le chargement de problème d'algèbre linéaire, et je ne peux pas allouer tout d'un coup, car lors du chargement c'est une méthode ajout colonne et ajout ligne qui est appelé, et j'ai en plus besoin au moment de la résolution de mon problème de rajouter des colonnes supplémentaires.

  13. #13
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Plorf Voir le message
    Je remet dans son contexte (je n'ai pas le choix)

    c'est en C, c'est une matrice qui est sous forme de double* !
    Donc c'est un grand tableau à une dimension !!

    Donc une fifo ne marche pas dans mon cas.
    ?

    int*, double*, float* ou schtroumpf*, je ne vois pas où est la difference.

    PS: La fifo est de taille maximum l = nombre de lignes de la matrice. Ce n'est pas si enorme en complexité mémoire.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  14. #14
    Membre habitué
    Profil pro
    Inscrit en
    Juin 2007
    Messages
    116
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France

    Informations forums :
    Inscription : Juin 2007
    Messages : 116
    Points : 149
    Points
    149
    Par défaut
    Le pb c'est que je ne peux pas changer de type.

    C'est un tableau très très bas niveau, et pour cause, c'est un argument d'une fonction fortran.... Donc non je peux le gérer manuellement comme une fifo mais en complexité... autant transposer

    Une fifo étant codé normalement comme une liste chainé c'est rapide en mémoire !
    Mais n'étant pas mon cas....


    En tout cas merci de toutes vos réponses à tous !

  15. #15
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Plorf Voir le message
    Le pb c'est que je ne peux pas changer de type.
    qui te parle de changer de type ? J'ai implémenté mon algo avec des int*, mais tu peux mettre des double* si tu veux.

    Donc non je peux le gérer manuellement comme une fifo mais en complexité... autant transposer
    Bon courage pour coder l'algo de transposition in-place.

    Une fifo étant codé normalement comme une liste chainé c'est rapide en mémoire ! Mais n'étant pas mon cas....
    rien compris.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  16. #16
    Membre habitué
    Profil pro
    Inscrit en
    Juin 2007
    Messages
    116
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France

    Informations forums :
    Inscription : Juin 2007
    Messages : 116
    Points : 149
    Points
    149
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    qui te parle de changer de type ? J'ai implémenté mon algo avec des int*, mais tu peux mettre des double* si tu veux.
    Oula, en fait, tu as raison, j'avais pas vu que tu utilisais la fifo juste comme tampon !!

    En fait c'est super ce que tu as fait !!!! lol

    Je vais par contre préférer créer un tableau colonne avec un index que je déplacerais, mais ça revient au même

    Citation Envoyé par pseudocode Voir le message
    Bon courage pour coder l'algo de transposition in-place.
    Bahhhh je verais :p

    Citation Envoyé par pseudocode Voir le message
    rien compris.
    Normal j'ai dit de la merde... mea culpa !!


    Il n'y a pas moyen de décaller par bloc directement ?
    C'est à dire, que mon seul problème c'est que j'ai l'emplacement de ma nouvelle colonne qui contient des données, et en décalant les "lignes" de façon à laisser la place pour la colonne j'avais un truc qui permettais en 2-3 itérations (ici) à faire quelque chose qui ressemble à ce que tu fais.

    En gros tu as une fonction move[ destination, depuis, taille du bloc ].

    Si tu as une idée !

    Dans tous les cas, merci beaucoup !!

  17. #17
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 76
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Points : 1 913
    Points
    1 913
    Par défaut
    [QUOTE=pseudocode;3464642]Si Zavonen a un bon algo de transposition in-place, je suis preneur.
    /QUOTE]
    Bon, je ne sais pas (en n^2/2) mais simple:


    Code C++ : 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
    #ifndef MATRICE_H
    #define MATRICE_H
    #include <iostream>
     
    using namespace std;
     
     
    class Matrice
    {
    public:
        Matrice(unsigned int, double * );
        virtual ~Matrice();
        friend ostream& operator<<(ostream& os,Matrice M);
        double& operator()(unsigned int , unsigned int );
        Matrice& Mineur(unsigned int , unsigned int );
        double Det();
        void transpose_en_place();
    protected:
    private:
        unsigned int rang;
        double * coeffs;
    };
     
    #endif // MATRICE_H
    Code C++ : 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
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    #include "Matrice.h"
    #include <iomanip>
     
    Matrice::Matrice(unsigned int n, double * c)
    {
        rang=n;
        coeffs=new double[n*n];
        for (unsigned int i=0;i<n*n;i++)
            coeffs[i]=c[i];
    }
     
    double& Matrice::operator()(unsigned int i, unsigned int j)
    {
        return coeffs[(i-1)*rang+(j-1)];
    }
     
    Matrice::~Matrice()
    {
        delete[] coeffs;
    }
     
    ostream& operator<<(ostream& os,Matrice M)
    {
        for (unsigned int i=1; i<=M.rang;i++)
        {
            for (unsigned int j=1;j<=M.rang;j++)
                os<<setw(10)<<M(i,j);
            os<<endl;
        }
        os<<endl;
        return os;
    }
     
    Matrice& Matrice::Mineur(unsigned int i,unsigned int j)
    {
        unsigned int m=rang-1;
        double * c= new double[m*m];
        unsigned int k=0;
        for (unsigned int u=1;u<=rang;u++)
            for (unsigned int v=1;v<=rang;v++)
                if ((u!=i)&&(v!=j)) c[k++]=(*this)(u,v);
        Matrice *pMin=new Matrice(m,c);
        delete[] c;
        return *pMin;
    }
     
    // calcul récursif du déterminant par la méthode du développement
    // suivant la première ligne
     
    double Matrice::Det()
    {
        if (rang==1) return (*this)(1,1); // cas des matrices d'ordre 1
        double result=0;
        int alterne= +1;
        for (unsigned i=1;i<=rang;i++)
        {
            if ((*this)(1,i) )
                result+=(*this)(1,i)*Mineur(1,i).Det()*alterne; // Appel récursif
            alterne=-alterne;
        }
        return result;
    }
    void Matrice::transpose_en_place()
    {
        double r;
        for (int i = 1; i<=rang;i++)
            for (int j=i+1;j<=rang;j++)
            {
                r=(*this)(i,j);
                (*this)(i,j)=(*this)(j,i);
                (*this)(j,i)=r;
            }
    }
    Code C++ : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #include <iostream>
    #include "matrice.h"
     
    using namespace std;
     
    int main()
    {
        double c[]={1,2,3,0,1,4,0,0,-1};
        Matrice M(3,c);
        cout<<M;
        M.transpose_en_place();
        cout<<M;
        return 0;
    }
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  18. #18
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    Pourquoi ne pas travailler en ordre Fortran (surtout si c'est pour attaquer du Fortran) plutôt qu'en ordre C ?

  19. #19
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Zavonen Voir le message
    Bon, je ne sais pas (en n^2/2) mais simple
    Tricheur... Tu as pris une matrice carré.
    Essaye avec une matrice rectangulaire (genre 5x3), pour voir.

    Citation Envoyé par Plorf
    Je vais par contre préférer créer un tableau colonne avec un index que je déplacerais, mais ça revient au même
    Oui, c'est une bonne optimisation car on connait déjà la taille max du fifo ( = nombre de lignes).

    Citation Envoyé par Plorf
    Il n'y a pas moyen de décaller par bloc directement ?
    Hum... sans doute, meme si ca ne m'a pas l'air evident. Je laisse ce genre d'optimisation comme exercice au lecteur.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  20. #20
    Membre habitué
    Profil pro
    Inscrit en
    Juin 2007
    Messages
    116
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France

    Informations forums :
    Inscription : Juin 2007
    Messages : 116
    Points : 149
    Points
    149
    Par défaut
    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

+ Répondre à la discussion
Cette discussion est résolue.
Page 1 sur 2 12 DernièreDernière

Discussions similaires

  1. Copier D'une Matrice(sous form de text box)
    Par ClubberGuy dans le forum VB 6 et antérieur
    Réponses: 17
    Dernier message: 22/05/2011, 22h33
  2. Mettre une matrice sous forme d'une colonne unique
    Par mfontan dans le forum MATLAB
    Réponses: 2
    Dernier message: 26/09/2008, 15h32
  3. [MySQL] données sous forme de tableaux en php
    Par brindherbe86 dans le forum PHP & Base de données
    Réponses: 2
    Dernier message: 12/03/2008, 15h49
  4. Actualiser sous-form à partir d'une zone de liste
    Par louroulou dans le forum IHM
    Réponses: 3
    Dernier message: 30/08/2007, 00h12

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