2
$\begingroup$

I have a very large(up to 9 000 000) VectorXi vector defined in Eigen C++ which is read from a data file.

The vector consists of 0, 1, 2, ...n segments with randomized lengths like below:

[0 0 ... 0 1 1 1 ... 1 2 2 ...2 3 ... 3 ... k k ... k k+1 k+1 ... k+1 .... n n ...n]

I need to count the lengths of each segement and store them into a new n+1 VectorXi, and index the starting positions of each segment which is also stored into a new n+1 VectorXi.

How can I implement it faster? I found sometimes it may take me up to 1 hour or so to finish it!!

$\endgroup$
4
$\begingroup$

This is a O(m) problem where m is the size of the big array. So this should be fast:

int n = v[v.size()-1];
int k=0;
VectorXi lengths[n+1], starts[n+1];
for(int i=0; i<v.size(); ++i) {
  int i0 = i;
  while(v[i]==k && i<n) ++i;
  lengths[k] = i-i0;
  starts[k] = i;
  ++k;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.