How can I efficiently position the different segments of a large vector in Eigen C++?

Question

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!!

Answer 1

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;
}