CODEWITHSUNDEEP
c++data-structures
user1484638
user1484638

Reputation: 341

Which data structure to be applied?

there is a matrix of size n*n where n<=500000. Initially all elements are 0. We have to update an entire row or column by a certain number every time there is an input

example:

n=3    
RS 1 10

means that we have to update row 1 by 10

0 0 0
0 0 0
0 0 0

after update 

10 10 10
 0  0  0    
 0  0  0

same we have to do for column. In the end we have to count the number of 0's in the matrix

as n is very big double dimension array cannot be applied. So which data structure to apply?

Upvotes: 2

Views: 176

Answers (4)

Adi
Adi

Reputation: 1316

Sparse Matrix is a data structure appropriate for matrices populated mostly with zeros. Its implementation is oriented towards to space efficiency. It is appropriate for cases just like yours, when you have large matrices with very little information.

Upvotes: 3

Shai
Shai

Reputation: 114786

Taking @Techmonk's answer a bit further: I propose two approaches:

1. Techmonk's

O(1) for updates, O(n^2) for recovering the number of 0`s

 class matZeroCount {
     std::vector< int > m_rows;
     std::vector< int > m_cols;
 public:
     matZeroCount( unsigned int n ): m_rows( n, 0 ), m_cols( n, 0 ) {};
     void updateRow( unsigned int idx, int update ) { 
          // check idx range w.r.t m_rows.size()
          // ignore update == 0 case
          m_rows[ idx ] += update; 
     }
     void updateCol( unsigned int idx, int update ) { 
          // check idx range w.r.t m_cols.size()
          // ignore update == 0 case
          m_cols[ idx ] += update; 
     }
     unsigned int countZeros() const {
         unsigned int count = 0;
         for ( auto ir = m_rows.begin(); ir != m_rows.end(); ir++ ) {
             for ( auto ic = m_cols.begin(); ic != m_cols.end(); ic++ ) {
                  count += ( ( *ir + * ic ) == 0 );
             }
         }
         return count;
     }
 };

2. Fast count

This method allows for O(1) for recovering number of zeros, at the cost of O(n) for each update. If you expect less than O(n) updates - this approach might be more efficient.

 class matZeroCount {
     std::vector< int > m_rows;
     std::vector< int > m_cols;
     unsigned int       m_count;
 public:
     matZeroCount( unsigned int n ): m_rows( n, 0 ), m_cols( n, 0 ), count(0) {};
     void updateRow( unsigned int idx, int update ) { 
          // check idx range w.r.t m_rows.size()
          // ignore update == 0 case
          m_rows[ idx ] += update;
          for ( auto ic = m_cols.begin(); ic != m_cols.end(); ic++ ) {
               m_count += ( ( m_rows[ idx ] + *ic ) == 0 ); // new zeros
               m_count -= ( ( m_rows[ idx ] - update + *ic ) == 0 ); // not zeros anymore
          }
     }
     void updateCol( unsigned int idx, int update ) { 
          // check idx range w.r.t m_cols.size()
          // ignore update == 0 case
          m_cols[ idx ] += update; 
          for ( auto ir = m_rowss.begin(); ir != m_rows.end(); ir++ ) {
               m_count += ( ( m_cols[ idx ] + *ir ) == 0 ); // new zeros
               m_count -= ( ( m_cols[ idx ] - update + *ir ) == 0 ); // not zeros anymore
          }

     }
     unsigned int countZeros() const { return m_count; };
 };

Upvotes: 3

Techmonk
Techmonk

Reputation: 1469

Well this is interesting, it would ofcourse depend on the number of operations you are going to perform but I would save it as 2 single dimension arrays. One with the row inputs and the other with the column inputs.

row[n] and col[n]

So the when you want to know the value of say element (4,7) it would be row[4] + col[7]

Upvotes: 4

Aniket Inge
Aniket Inge

Reputation: 25695

You might need a user defined type that internally contains a std::list <std::list<int>>.

But really, can you hold 250000000000 integers in the memory at the same time? I doubt it!

You might need to use a much different, file-to-memory mapped data structure of two dimensional array of integers.

Upvotes: 1

Related Questions