Thread: best way to run through loop and perform operation

I have a vector of bools that looks like

vector<bool> vals
position: 0 1 2 3 4 5
bool val: 0 1 0 0 1 1

the bool val indexes to a 6x6 matrix A where i have random values stored.
in my following vector, I would want to sum the values of A(1,4),A(4,5),A(5,5)

if i had
position: 0 1 2 3 4 5
bool val: 0 1 1 0 1 0

I would want to sum A(1,2), A(2,4),A(4,4)

what is the fastest way to loop through the bool vector and calculate the values i want?

Code:

double sum = 0;
int j = 0;
int k = 0;
for(int i =0; i<vals.size(); ++i)
{
k += -(vals[i]-1);
j= i*vals[i];
//sum +=A[j-k][j]
}

i was thinking something along the lines of the above, but there are problems when my bool vector vals[0]=1, and my matrix A might have non-zero values for A[row][col] that i sum.

thoughts?

Are you saying (and this seems like a huuuuuuuuuuge stretch, but it's the best pattern that I can find) that you will always have three "true" values in your vector (call them a, b, and c) and you will want to add A(a,b) + A(b,c) + A(c,c)?

yes, i will have a series of true values (not necessarily just 3) and i want to pull the 1st true value and then the next true value to give A(1st,2nd) on the last true value in the list, I want to repeate A(last,last) but this can probably be done after the loop has stopped.

unless your sparse matrix is populated according to some very odd pattern, you will need atleast M*N bools to record the 'valued' positions of an MxN matrix

Originally Posted by lawrenced

yes, i will have a series of true values (not necessarily just 3) and i want to pull the 1st true value and then the next true value to give A(1st,2nd) on the last true value in the list, I want to repeate A(last,last) but this can probably be done after the loop has stopped.

Then in your loop you will need to keep track of not only the current value but the most recent true value.

Originally Posted by tabstop

Then in your loop you will need to keep track of not only the current value but the most recent true value.

can anyone think of the best way to do that while running the loop? i think the code:

Code:

double sum = 0;
int j = 0;
int k = 0;
for(int i =0; i<vals.size(); ++i)
{
k += -(vals[i]-1);
j= i*vals[i];
sum +=vals[i]*A[j-k][j] //will only sum the value if true
}

will get rid of the problems in my A matrix - but how can I record the value of the most recent true without some container?

Originally Posted by lawrenced

can anyone think of the best way to do that while running the loop? i think the code:

Code:

double sum = 0;
int j = 0;
int k = 0;
for(int i =0; i<vals.size(); ++i)
{
k += -(vals[i]-1);
j= i*vals[i];
sum +=vals[i]*A[j-k][j] //will only sum the value if true
}

will get rid of the problems in my A matrix - but how can I record the value of the most recent true without some container?

Code:

if (vals[i])
    most_recent_true_value = i;

I don't think "variable" has quite the same connotations as "container".

Originally Posted by tabstop

Code:

if (vals[i])
    most_recent_true_value = i;

I don't think "variable" has quite the same connotations as "container".

tabstop, i am able to perform the above loop without any if statements - this should run signifcantly faster than using if statements correct?

Originally Posted by lawrenced

tabstop, i am able to perform the above loop without any if statements - this should run signifcantly faster than using if statements correct?

I haven't done any tests, but I'm pretty sure the answer is "definitely not". You have a subtraction, a negation, two multiplies, two additions, and three variable assignments on every pass through the loop. Contrast that with an if-comparison every time through the loop, plus one add and two variable assignments only when necessary.

to actually venture an answer to your question, you should store the non-zero positions in the vector, and not use the bitmask technique. somethign like this:

Code:

  std::vector<unsigned int>i; 
  i.push_back(1);
  i.push_back(4);
  i.push_back(5);
  int a[6][6]={0};
  unsigned int* index = &i[0];
  unsigned int* const end = (&i[0])+i.size();
  unsigned int sum=0;
  while(++index<end)
  {
    sum+=a[*(index-1)][*index];
  }
  std::cout<< sum;

all, have figured out how to do this with out containers or vectorizations is significantly faster than with vectors~ x2.