CODEWITHSUNDEEP
c++c
smhx
smhx

Reputation: 2266

How to select a column from a row-major array in sub-linear time?

Lets say that I'm given a row major array.

int* a = (int *)malloc( 9 x 9 x sizeof(int));

Look at this as a 2D 9x9 array where a (row,column) index corresponds to [row * 9 + column] Is there a way where I can select a single column from this array in sub-linear time? Since the columns wont be contiguous, we cant do a direct memcpy like we do to get a single row.

The linear-time solution would be obvious I guess, but I'm hoping for some sub-linear solution.

Thanks.

Upvotes: 1

Views: 836

Answers (2)

David Rodríguez - dribeas
David Rodríguez - dribeas

Reputation: 208323

It is not clear what you mean by sublinear. If you consider the 2D array as NxN size, then sublinear on N is impossible. To copy N elements you need to perform N copy operations, the copy will be linear on the number of elements being copied.

The comment about memcpy seem to indicate that you mistakenly believe that memcpy is sublinear on the number of elements being copied. It is not. The advantage of memcpy is that the constant hidden in the big-O notation is small, but the operation is linear on the size of the memory being copied.

The next question is whether the big-O analysis actually makes sense. If your array is 9x9, then the effect hidden in the constant of the big-O notation can be more important than the complexity.

Upvotes: 3

111111
111111

Reputation: 16148

I don't really get what you mean but consider:

 const size_t x_sz=9;
 size_t x=3, y=6; //or which ever element you wish to access
 int value=a[Y*x_sz+x];

this will be a constant time O(1) expression. It must calculate the offset and load the value.

to iterate through every value in a column:

 const size_t x_sz=9, y_sz=9;
 size_t x=3; //or which ever column you wish to access

 for(size_t y=0; y!=y_sz; ++y){
     int value=a[Y*x_sz+x];
     //value is current column value
 }

again each iteration is constant time, the whole iteration sequence is therefore O(n) (linear), note that it would still be linear if it was contiguous.

Upvotes: 0

Related Questions