[C++] Transponowanie macierzy rzadkiej

0

Witam,
tym razem chciałem zapytać o jakieś sugestie co do transponowania macierzy...

Macierz przechowywana jest w 3 wektorach:

vector <float> mtx_val;         // kolejne wartości z wczytanej macierzy
vector <unsigned int> mtx_col;  // pozycje (kolumny) kolejnych el. niezer. z powyzszego wektora
vector <unsigned int> mtx_nzl;  // liczba elementów niezerowych w kolejnych wierszach

Ja sobie wymyśliłem transponowanie za pomocą 2 pomocniczych wektorów:

vector < vector <float> > trns_val;        // wektor roboczy przechowujacy transponowana macierz (wartosci)
vector < vector <unsigned int> > trns_col; // wektor roboczy przechowujacy transponowana macierz (kolumny)

przy czym jest do dość nieoptymalne pamięciowo, a na tym mi bardzo zależy (równie bardzo, co na szybkości), bo macierze mogą być dosyć duże.

pozdrawiam

0

aleś napchał tych wektorów tutaj, aż mi się przypomniało jak kumpel zrobił program z 9 wektorami, a można było zrobić z 2 :).

no więc tak ja bym to zrobił 2 vektory 2-wymiarowe
jeden wej. a drugi transponowany.

Załozmy ze to wej.

[ 1 2 3 ]
[ 4 5 6 ]

Taki ma byc wyj.

[ 1 4 ]
[ 2 5 ]
[ 3 6 ]
for( int i=0; i<il_wierszy_tab_wej; i++)
 for(int j=0; j<il_kolumn_tab_wej;j++)
  tabWyj[i][j]=tabWej[j][i];

Koniec :P

0

wiem, że byłoby prościej, ale problem polega na tym, że mam 3 wektory wejściowe i na tym muszę robić [glowa]

0

MrokU: zapomniales dodac najwazniejszej informacji: jest to macierz RZADKA. moze byc dosc trudno to zauwazyc poczatkujacym ktorzy na te 3 linie kodu zerkna..

liseeek: przede wszystkim, zwazcie ze po cos jednak te trzy wektory byly napychane i moze doczytaj o co chodzi.. dane jakie sa, w takiej postaci trzeba je jak najlepiej wykorzystac. majac na wejsciu macierz rzadka, raczej nie da sie nagle odworzyc pelnej macierzy po to aby sobie ja potem dwiema prostymi petlami transponowac

przykladowo - macierz:

   0 1 2 3 4 5 6
\_______________
0| 0 0 0 0 1 0 0
1| 0 6 2 0 0 0 0
2| 1 0 0 2 1 0 0
3| 0 3 0 0 0 0 1

bedzie reprezentowana jako:

mtx_val = {1 6 2 1 2 1 3 1};     // kolejne NIEZEROWE wartości z wczytanej macierzy
mtx_col = {4 1 2 0 3 4 1 6};     // pozycje (kolumny) kolejnych el. niezer. z powyzszego wektora
mtx_nzl = {1 2 3 2};             // liczba elementów niezerowych w kolejnych wierszach

widzisz oszczednosc miejsca? a teraz sobie wyobraz ze to nie jest macierz 7x4 tylko np. 1000000 x 3000

po transponowaniu, masz uzyskac macierz, o dziwo, rowniez rzadką:

   0 1 2 3
\_________
0| 0 0 1 0
1| 0 6 0 3
2| 0 2 0 0
3| 0 0 2 0
4| 1 0 1 0
5| 0 0 0 0
6| 0 0 0 1

czyli:

mtx_val' = {1 6 3 2 2 1 1 1};
mtx_col' = {2 1 3 1 2 0 2 3};
mtx_nzl' = {1 2 1 1 2 0 1};

mam nazieje ze teraz problem jest jasny.. MrokU - postaraj sie dostarczac wiecej informacji.. na skrotowosci sam tracisz

0

Metoda czołgowa: Przejdź do reprezentacji typu (x,y,wartość). transponowanie w takiej reprezentacji to zamiana iksa z ygrekiem, po czym wróć do Twojej reprezentacji (hint: będzie potrzebne sortowanie).

0
in.txt napisał(a)

val: 1 6 2 1 2 1 3 1
col: 4 1 2 0 3 4 1 6
nzl: 1 2 3 2

#include <iostream>
#include <vector>

std::vector<unsigned int> readstream_int(std::istream & input)
{
    using namespace std;

    vector<unsigned int> result;
    unsigned int number;

    while(cin >> number)
        result.push_back(number);

    cin.clear();
    return result;
}

void dumpstream(std::ostream & output, std::vector<unsigned int> & vect)
{
    for(std::vector<unsigned int>::const_iterator it = vect.begin(); it!=vect.end(); ++it)
        output << *it << " ";
}

int main()
{
    using namespace std;

    string const header1 = "val:", header2 = "col:", header3 = "nzl:";
    string tmp;

    cin >> tmp;
    if(tmp != header1) return -1;
    vector<unsigned int> mtx_val = readstream_int(cin);

    cin >> tmp;
    if(tmp != header2) return -1;
    vector<unsigned int> mtx_col = readstream_int(cin);

    cin >> tmp;
    if(tmp != header3) return -1;
    vector<unsigned int> mtx_nzl = readstream_int(cin);

    //START

    //przetworzenie ilosci niezerowych elementow w wierszach na informacje
    //od ktorego elementu do ktorego elementu dany wiersz sie rozciaga w mtx_val
    vector<unsigned int> idx_start;
    vector<unsigned int> idx_end;
    unsigned int start_kolumny = 0;
    for(vector<unsigned int>::iterator it = mtx_nzl.begin(); it<mtx_nzl.end(); ++it)
    {   idx_start.push_back(start_kolumny);
        start_kolumny += *it;
        idx_end.push_back(start_kolumny);
    }

    //teraz, zeby obejrzec jaki jest N-ty niezerowy element w wierszu X-tym,
    //wystarczy:
    //  mtx_val[ mtx_idx[X] + N ]
    //i na jakiej byl kolumnie:
    //  mtx_col[ mtx_idx[X] + N ]
    //X oraz N oczywiscie sa zero-based

    vector<unsigned int> mtx_val2; //wektory wyjsciowe
    vector<unsigned int> mtx_col2;
    vector<unsigned int> mtx_nzl2;

    unsigned int aktualnie_badana_kolumna = 0;
    for(;;)
    {
        unsigned int ilosc_elementow_w_kolumnie = 0;
        bool sa_elementy_w_wierszach = false;
        for(size_t numer_wiersza=0; numer_wiersza<idx_start.size(); ++numer_wiersza)
        {
            if(idx_start[numer_wiersza] >= idx_end[numer_wiersza])  //czy kolumny w tym wierszu juz sie skonczyly?
                continue;
            sa_elementy_w_wierszach = true;
            if(mtx_col[ idx_start[numer_wiersza] ] == aktualnie_badana_kolumna)    //czy wiersz 'zaczyna sie' kolumna o danym numerze?
            {
                mtx_val2.push_back( mtx_val[ idx_start[numer_wiersza] ] );  //wartosc komorki
                mtx_col2.push_back( numer_wiersza );
                ++ilosc_elementow_w_kolumnie;
                ++idx_start[numer_wiersza];  //'usuniecie' komorki z wiersza
            }
        }
        if(!sa_elementy_w_wierszach) //wszystkie wiersze okazaly sie puste, nie ma potrzeby odpisywac samych zer na koniec
            break;
        mtx_nzl2.push_back(ilosc_elementow_w_kolumnie);
        ++aktualnie_badana_kolumna;
    }

    //KONIEC

    dumpstream(cout, mtx_val2); cout << endl;
    dumpstream(cout, mtx_col2); cout << endl;
    dumpstream(cout, mtx_nzl2); cout << endl;
}

calosc miesci sie miedzy 'start' a 'koniec', pozostale fragmenty to wczytywanie i wypluwanie danych

zlozonosc pamieciowa = 2 iloscwierszy + danewejsciowe (dane wyjsciowe nie musza byc trzymane w pamieci)
obliczeniowa = hm.. ktos sie podejmie..? na pewno nie gorsza niz O(cols
rows) ;p

0

Wykorzystywany w problemie sposób pamiętania macierzy rzadkiej jest niepełny. Na podstawie tych trzech wektorów nie da się odtworzyć pierwotnej macierzy - trzeba jeszcze znać ilość kolumn.
Czy poniższy sposób pamiętania został Ci narzucony, czy sam go wybrałeś ? Jeśli to drugie, to moim zdaniem zdecydowanie szybszy sposób transponowania da się napisać jeśli zamiast poniższego

val: 1 6 2 1 2 1 3 1
col: 4 1 2 0 3 4 1 6
nzl: 1 2 3 2

użyć takiego sposobu

valcol (1,4) (6,1) (2,2) (1,0) (2,3) (1,4) (3,1) (1,6)
nzl      1 2 3 2
0

podejrzewam, ze zaklada sie dopelanianie macierzy z prawej/dolu dowolna iloscia kolumn/wierszy calkowicie zerowych i sa one pomijane przy zapisywaniu

valcol (1,4) (6,1) (2,2) (1,0) (2,3) (1,4) (3,1) (1,6)
nzl 1 2 3 2

opisz! on i tak oba pierwsze strumeinie trzyma w calosci w pamieci w vectorach, wiec smialo mozna je traktorac jako pary elementow

0

Jako że pewniej czuję się w Javie, to jej właśnie użyłem.
Oznaczenia:
A tablica zawierająca wartości niezerowe macierzy wejściowej
B tablica z numerami kolumn
C tablica z ilościami niezerowych wyrazów w wierszu
A2 tablica zawierająca wartości niezerowe macierzy wyjściowej
B2 tablica z numerami wierszy
C2 tablica z ilościami niezerowych wyrazów w kolumnie

        int k=0;
        Vector<Integer> wiersze=new Vector<Integer>(); //numery tych wierszy w których
                                                                                  //są niezerowe wyrazy
        for(k=0;k<C.length;k++)
        {
            if(C[k]>0)
            {
                wiersze.add(k);
            }
        }
        if(wiersze.size()==0)
        {
            return; // gdyby macierz wejściowa była skrajnie rzadka i zawierała tylko zera
        }
        int ile=0; // ile wyrazów z wiersza odczytano
        int pozycja=0; 
        int wiersz=wiersze.get(pozycja); // w którym wierszu leży odczytywana wartość
        Dane[] valColRow=new Dane[B.length];
        for(k=0;k<B.length;k++)
        {
            C2[B[k]]++; // liczenie wyrazów w kolumnach
            valColRow[k]=new Dane(A[k],B[k],wiersz);
            ile++;
            if(ile>=C[wiersz]) // zaczynamy czytać wyrazy z kolejnego wiersza
            {
                pozycja++;
                ile=0;
                if(pozycja<wiersze.size())
                {
                    wiersz=wiersze.get(pozycja);
                }
            }
        }
        Arrays.sort(valColRow);
        A2=new int[B.length];
        B2=new int[B.length];
        for(k=0;k<B.length;k++)
        {
            A2[k]=valColRow[k].val;
            B2[k]=valColRow[k].row;
        }

Klasa Dane jest pomocnicza, żeby się łatwo sortowało. Zawiera wartość, nr wiersza i nr kolumny.

    //--------------------------------------------
    class Dane implements Comparable
    {
        public int val;
        public int col;
        public int row;
        //--------------------
        public Dane(int val,int col,int row)
        {
            this.col=col;
            this.val=val;
            this.row=row;
        }
        //--------------------
        public int compareTo(Object o)
        {
            Dane d=(Dane)o;
            if(this.col!=d.col)
            {
                return (int)Math.signum(this.col-d.col);
            }
            else
            {
                return (int)Math.signum(this.row-d.row);
            }
        }
    }

Złożoność obliczeniowa O(M*log(M)), gdzie M, to ilość niezerowych wyrazów macierzy.

0

w zasadzie, jest to to co napisal marcin_mank w trakcie kiedy ja skrobalem sposob z lookup'em

btw. tamten moj sposob moze potrzebowac mniej pamieci niz ten zamieszczony przez Ciebie - ale kosztem tego jest jego wzgledna powolnosc [a przynajmnie tak mi sie wydaje].

o ile dobrze licze, moj jest wydajnieszy pamieciowo jesli srednia liczba wartosci niezerowych w wierszu [= Nvals/Nwierszy] > 2/3, czyli, w praktyce, wystarczy ze nie bedzie wierszy calkowicie zerowych (lub bedzie ich malo)

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0