[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)

0

A może by macierz rzadką pamiętać jako wektor o współrzędnych (row,col,value) ? Zajmuje trochę więcej miejsca ale bardzo upraszcza transponowanie.

0

szczerze.. nie wiem co Ci chodzi po glowie i nie chcialem sie czepiac, ale...

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

te dwa sposoby sa calkowicie tozsame i wzjamnie wymienne

wektor o współrzędnych (row,col,value)

z jakiegos powodu ta macierz byla trzymana w postaci takiej w jakiej trzymana byla.. to, ze w postaci trojki RCV transponowanie jest trywialne, jest oczywiste. zdziwilbym sie jesli jeszcze autor sam jej nie probowal..
nalezy wiec zastanowic sie., po jaka chorobe ktos zadawal sobie trud zeby te macierz przedstawic w innej, owej pierwszej formie. IMHO chodzilo wlasnie o pamiec, nie o szybkosc przetwarzania.

pozwolmy autorowi sie wypowiedziec, o ile jeszcze jest zainteresowany tematem, zamiast kombinowac w ciemno

0

Moim zdaniem (C++ znam po łebkach), poniższe dwa sposoby

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

nie są równoważne. Różnica wychodzi na jaw gdy chcesz posortować np. col i chcesz żeby analogicznie poprzestawiało się val
Który sposób jest mniej pamięciożerny zależy od "rzadkości" macierzy. Np. dla macierzy diagonalnej są one równoważne.
pozdrawiam
</quote>

0

wydaje Ci sie, poniewaz uzywasz gotowej meotdy Array.Sort. jesli napisalbys sortowanie samemu, albo uzyl bardziej rozbudowanego (pod katem konfiguracji wejscia-wyjscia) algorytmu, okazalo by sie nagle ze z bardzo dobrym powodzeniem mozna sortowac N wektorow na podstawie jednego wektora.. sprobuj np. napisac durne, glupie, sortowanie przez wstawianie ktore bedzie badalo wektor X a przestawialo analogiczne elementy w wektorze X i Y. i ocen ktore sortowanie bedzie lepsze, sortowanie przez wstawianie na parach (xy) czy na dwoch rownoleglych wektorach X Y. pamietaj oczywiscie ze dostep do elmeentu wektora to O(1). sposob mozna w trywialny sposob rozciagnac na dowolny algo sortowania

zakladajac ze wyniki wyjda Ci prawidlow, to wlasnie to rozumiem przez 'rownowaznosc'

bogdans napisał(a)

Różnica wychodzi na jaw gdy chcesz posortować np. col i chcesz żeby analogicznie poprzestawiało się val
Który sposób jest mniej pamięciożerny zależy od "rzadkości" macierzy.

nieno, teraz to pojechales.. chcesz powiedziec, ze trzymanie elementow jako dwa wektory VALS i COLS bedzie mialo inna zlozonosc pamieciowa niz trzymanie jednego wektora par elementow (val,col) ? i ze to zalezy od gestosci macierzy? cos Ci sie chyba ostro pomerdalo.. ilosc elementow jest identyczna w obu przypadkach, rowna theta(N) [N=ilosc niezerowych elemn. w macierzy], a ilosci wartosci podstawowych przechowywanych przez te elementy sa w obu przypadkach dokladnie sobie rowne, i rowne 2*sizeof(int) * N [N-patrz wczesniej]. gdzie roznica w zlozonosci pamieciowej?

i nadmieniam ze te dwa powyzsze 'stwierdzenia' niezaleznie od jezyka programowania.. wystarczy aby w nim istnialy realizacje wektorow z dostepem O(1) do elementu o zadanym indeksie

0

Ty poruszyłeś dwa tematy, ja również.
Zdanie

Który sposób jest mniej pamięciożerny zależy od "rzadkości" macierzy.
dotyczy modelu RCV.
Moim zdaniem dwa sposoby pamiętania danych zajmujące tyle samo pamięci nie są równoważne jeżeli jeden z nich do pożądanego przetworzenia wymaga jednego wiersza kodu, drugi zaś wymaga implementacji skomplikowanego algorytmu.

0
bogdans napisał(a)

Ty poruszyłeś dwa tematy, ja również.
Zdanie

Który sposób jest mniej pamięciożerny zależy od "rzadkości" macierzy.
dotyczy modelu RCV.

mmmmhmm.. tego nie dalo sie zauwazyc z tamtego postu..
w takim razie:

wzgledna pamieciozernosc RCV zalezy nie od gestosci macierzy, tylko od tego, ile srednio elementow jest w jednym wierszu macierzy. brzmi podobnie, ale jest to co innego.

jesli sredna ilosc elementow w wierszu =1, to jest to RCV jest rownowazny z vect (col,val).
jesli ponad/ponizej 1, to RCV odpowiednio ma wieksza/mniejsza niz vect (col,val).

a vect (col,val) ma zawsze dokladnie taka sama jak vect col + vect val, wiec sa rownowazne jak juz wspomnialem wyzej

0

Aleście się rozbrykali - szok ;]

no ale jedziemy:

  1. Racja, macierz jest rzadka. <- zresztą PISZE W TYTULE :-)
  2. Z informacji jakie otrzymałem wynika, że nie ma kolumn pustych w macierzy.
  3. Dane wejściowe są takie, jakie są. Natomiast dane wyjściowe (przynajmniej ja sobie tak założyłem) mogą być 2-rakie: macierz w postaci takiej, jak wejściowa; albo - plik wyjściowy z przetransponowanym paskiem.
  4. Nie widzę aktualnie sensu spierania się o sortowanie. Macierz przechowywana jest w taki sposób, że posortowana być nie musi, a operacje na niej wykonywane "mają gdzieś" kolejność elementów (byle kolejne pary wartości w wektorach sobie odpowiadały) (przynajmniej z tego co wiem dzisiaj...).
0

sortowanie nie mialo sluzyc sortowaniu macierzy, tylko posortowaniu par wartosc-kolumna(-wiersz) tak, aby mozna ja bylo latwiej transponowac..

0

No to ja też na koniec dołożę swoje 5 groszy :P .

#include <vector>

struct SparseRowItem
{ 
      double value;
      unsigned int column; 
};

typedef std::vector<SparseRowItem> SparseRow;

typedef std::vector<SparseRow> SparseMatrixRows;

class SparseMatrix
{
     SparseMatrixRows rows;
     unsigned int columns_count;
public:
     .... // inne metody konstruktory itp
     SparseMatrix& SetAsTranspositonOf( const SparseMatrix& source );
};

SparseMatrix& SparseMatrix::SetAsTranspositonOf( const SparseMatrix& source )
    {
    columns_count = source.rows.size();
    rows.clear();
    rows.setsize( source.columns_count );
   
    // idź po kolejnych wierszach źródła - kolumnach tej macierzy
    for( unsigned int column = 0; i < columns_count;  ++column )
         {
         SparseRow& sourceRow = source.rows[ column ];

         // idź po kolejnych elementach wiersza źródła - wierszach tej macierzy
         for( SparseRow::iterator i = sourceRow.begin(); i!=sourceRow.end(); ++i )
               {
               SparseRowItem item;
               item.value = i->value;
               item.column = column;
               rows[ i->column ].push_back( item );
               }
         }
    return *this;
    }

Myślę, że jest w miarę przejrzyście, zrozumiale i efektywnie.

0

Zakladam, ze dane sa zadeklarowane i zakladam rowniez, ze mtx_col zawiera kolejne nr'y kolumn poczawszy od 0.

Psudokod a'la C++:

sortuj_val_col();    /*sortowanie stabilne<?> wg kolumn -- wlasciwie to nie wiem czy potrzebne, ale dzieki temu uzyskujemy mtx_val w odpowiedniej 'wyjsciowej' kolejnosci*/
max_col = mtx_col.size();    //najwiekszy/maxymalny nr kolumny + 1
for (int i=0; i<max_col; ++i){
    mtx_nzl[i].push_back(ile_kolejnych_kolumn()); /*zlicza ile jest powtarzajacych sie liczb w poczatkowym mtx_col i 'tworzy' wynikowy mtx_nzl -- po posortowaniu sprawa b. prosta*/
}

Albo zapomnialem albo chwilowo nie wiem skad wytrzasnac mtx_col -- jezeli uzyskanie mtx_col jest uzaleznione od jakiegos wektora 'wejsciowego' to potrzebny bedzie minimum jeden dodatkowy wektor --- wszystko pozostale mozna realizowac na wektorach juz istniejacych.
Pozniej sie zastanowie dokladniej i podam kompletniejsze rozwiazanie jakie bym napisal(o ile nie zapomne o watku lub nie stwierdze ze malo wydajne ono[rozwiazanie] :P )

Pozdrawiam.

0

MarekR22 - w istocie, rozwiazanie ktore zaprezentowales jest hybryda tego co proponowalismy wczesniej:) algorytm prawie jeden-w-jeden z tym ktory podalem, zas struktury danych praktycznie takie jak opisal bogdans. ale wyglada ladniej :)

Joker - mtx_col jest zadane z gory. na wejsciu otrzymujesz wypelniony mtx_val, mtx_col i mtx_nzl. i tak wlasciwie.. to caly 'haczyk' algorytmu schowales pod zdawkowym "sortuj_val_col" -- a przeciez wlasnie w tej czesci jest najwiekszy problem algorytmiczny autora i tradeoff pamiec/szybkosc :)

0

quetzalcoatl, powiedz mi, kiedy Twój program wyjdzie z tej nieskończonej pętli? Bo tak sobie porównuje różne algorytmy i Twój się deczko wiesza i nie wiem, czy ja coś przegapiam, czy co...

No a co powiecie o takim sposobie:

  vector <float> mtx_val2;
  vector <unsigned long int> mtx_col2;
  vector <unsigned int> mtx_nzl2;
  vector <unsigned int> temp_nzl2; // wektor przechowujacy ilosc wpisanych juz elementow

  mtx_nzl2.assign ( mtx_nzl.size(), 0 );
  temp_nzl2.assign ( mtx_nzl.size(), 0 );
  mtx_col2.assign ( mtx_col.size(), 0 );
  mtx_val2.assign ( mtx_val.size(), 0 );

  for ( int i = 0; i < mtx_col.size(); i++ ) // wypelnienie wektora z iloscia el. niezerowych w kazdej kolumnie
    mtx_nzl2[ mtx_col[i] ]++;

 // przetworzenie ilosci niezerowych elementow w wierszach na informacje
 // od ktorego elementu dany wiersz sie rozciaga w przetransponowanej macierzy
  vector <unsigned int> idx_start;

  unsigned int col_str = 0; // start kolumny
  for ( vector <unsigned int>::iterator it = mtx_nzl2.begin(); it < mtx_nzl2.end(); ++it)
  {
    idx_start.push_back ( col_str );
    col_str += *it;
  }  
 // utworzono - wpisanie 4-go, kolejnego elementu do 5 wiersza bedzie na pozycji
 // mtx_val2[ idx_start [kolumna akt. elementu] + temp_nzl2[kolumna akt. elementu] ]
  unsigned int akt_elem = 0; // aktualnie badany element macierzy pierwotnej
  for (int wiersz = 0; wiersz < mtx_nzl.size(); wiersz++)
    for (int elem = 0; elem < mtx_nzl[wiersz]; elem++) {
      mtx_col2[ idx_start[ mtx_col [ akt_elem ] ] + temp_nzl2 [ mtx_col [ akt_elem ] ] ] = wiersz;
      mtx_val2[ idx_start[ mtx_col [ akt_elem ] ] + temp_nzl2 [ mtx_col [ akt_elem ] ] ] = mtx_val [ akt_elem++ ];
    }
0
MrokU napisał(a)

quetzalcoatl, powiedz mi, kiedy Twój program wyjdzie z tej nieskończonej pętli? Bo tak sobie porównuje różne algorytmy i Twój się deczko wiesza i nie wiem, czy ja coś przegapiam, czy co...

przegapiasz:)

quetzalcoatl napisał(a)
    for(;;)
    {
        ....
        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(!sa_elementy_w_wierszach) //wszystkie wiersze okazaly sie puste, nie ma potrzeby odpisywac samych zer na koniec
            break;   //<--------TU
0

No tylko problem w tym, że mi się on zapętla...

a ten mój przykład oglądałeś?

0

nie, sorrry, nie mam czasu na razie.. zerkne pozniej
zarzuc dane wejsciowe na ktorych moj odpalales, sprawdze i jak cos poprawie.
na tych danych ktore podal autor dziala poprawnie, na innych nie sprawdzalem

0

..oups.. zauwazylem wlasnie Twojego maila z danymi, wezme sie za to wieczorem

0

Dobra, to taka mała zmiana, bo ostatnio dowiedziałem się, że jednak piszę to nie tak jak (podobno) wymagano. Mianowicie:
wczytywać mam kolumnę, transponować ją i zapisywać. No i skupić się na optymalizacji pamięciowej... Kocham to...

0

mmhm.. jesli wazna jest optymalizacja pamieciowa, to moj (minus ow bug) jest ok.. wczytywanie kolumny i dopiero jej transponowanie jest bezsensu.. kazda jedna niezerowa wartosc w kolumnie moze tuz po odczytaniu zostac natychmiast zapisana do pliku wyjsciowego.. wprost nie ma sensu jej trzymac. na pewno zas trzeba bedzie trzymac indeks startowy kolejnych wierszy..

btw. ten plik binarny ktory mi wyslales - jaka ma strukture? to jest strumien wartosci czy wszystkie trzy strumienie?

0

wszystkie 3. Każdy kolejny element ma 4 bajty. A leci tak:
niezerowe w wierszu, kolumna, wartość, kolumna, wartość ... niezerowe w wierszu, kolumna, wartość, kolumna, wartość ...

A jak chcesz zapisywać od razu do pliku wyjściowego? Jak byś chciał tak robić, to musiałbyś duuużo razy tą macierz czytać, a to chyba mija się z celem...

0

macierz:

023
140
560

wyjscie:
? ? ?
? ? ?
? ? ?

czytasz kolumne 0..
o, pierwsza komorka to 0. wyjscie:
0 ? ?
? ? ?
? ? ?

o, druga komorka to 1. wyjscie:
0 1 ?
? ? ?
? ? ?

o, trzecia komorka to 5. wyjscie:
0 1 5
? ? ?
? ? ?
itd dla reszty

a wiec:

quetzalcoatl napisał(a)

wczytywanie kolumny i dopiero jej transponowanie jest bezsensu.. kazda jedna niezerowa wartosc w kolumnie moze tuz po odczytaniu zostac natychmiast zapisana do pliku wyjsciowego.. wprost nie ma sensu jej trzymac

k.p.w?

a co do mijania sie z celem - to jest dyskutowalne. powiedziales ze masz to zoptymalizowac pamieciowo, to to ze odbywa sie to kosztem szybkosci jest oczywiste.. jesli to masz zrobic to mialaby byc totalnie hardcore'owa minimalizacja uzycia pamieci [bo nie wiem.. zegarek CASIO bedzie ten program wykonywac], no to coz.. da sie ten problem rozwiazac w pamieci wielkosci O(1) ale kosztem zażynania dysku ciaglymi seek'ami po macierzy wejsciowej.. ale to moim zdaniem tez przegiecie, nie to proponowalem, patrz wyzej

co do pliku wejscia i crashu programu -- specjalnie podalem przykladowy plik wejscia. tamten moj algorytm zaklada, ze informacje sa posortowane!!! tzn. ze 'zrzut' kolejnych niezerowych komorek w wierszu jest poustawiany wg. numerow kolumn:

val: 1   6 2   1 2 1   3   1
col: [4] [1 2] [0 3 4] [1 6]     <- w wierszu posortowane po kolumnach
nzl: 1 2 3 2

w Twoim pliku wejsciowym nie jest to prawda. kolumny w wierszu sa wymieszane losowo. albo wstepnie je przesortuj w miejscu, albo uzyj innego algorytmu

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