CODEWITHSUNDEEP
c++performancematrixvector
user313
user313

Reputation: 699

Most efficient way to implement matrix on large inputs in c++?

I am trying to figure out the best way to create a matrix in C++. So far I have two options I have come up with:

1) One vector which stores all the data in one "line," but using modulo and arithmetic, can be accessed like a 2D table.

OR

2) A vector holding pointers to other vectors, such that the original vector represents set columns and the vectors it points to contain the values going down the rows of each column.

For example, if we have a table like so:

Name  |  Course   |  Grade
Allen | Chemistry |  76
Rick  | English   |  84
Mary  | Physics   |  93

My first example would store all the data in one vector like this:

my_vec = {Name, Course, Grade, 
          Allen, Chemistry, 76, 
          Rick, English, 84, 
          Mary, Physics, 93}

(assume the heterogeneous nature of the values stored in the same vector is not a problem for now)

My second example would store the data like so: 

vec1 = {Name, Course, Grade};

Where each spot would contain a pointer to a vector (3 "sub" vectors in this ex.)

Name -> name_vec = {Allen, Rick, Mary}
Course -> course_vec = {Chemistry, English, Physics}
Grade -> grade_vec = {76, 84, 93}

Some requirements on the matrix:

Does anyone know if one of these options would be significantly more efficient than the other on large inputs? Alternately, does anybody have a better suggestion for implementing this matrix?

Upvotes: 3

Views: 968

Answers (1)

Vaughn Cato
Vaughn Cato

Reputation: 64308

In my experience, the main issue is good cache usage. There isn't a huge win for using modulo arithmetic vs pointers for accessing the rows, but keeping the data in contiguous memory is very important for efficient access. A vector of vectors is probably not going to be the most efficient because the individual vectors could be scattered throughout memory, unless you use a custom allocator. A vector of pointers which point to sections of one contiguous block of elements is probably better.

The details about how to lay out your data is going to depend on your particular usage patterns though. Where performance is concerned, you always need to measure.

Upvotes: 2

Related Questions