2

Now I am writing some code for solving vehicle routing problems. To do so, one important decision is to choose how to encode the solutions. A solution contains several routes, one for each vehicle. Each route has a customer visiting sequence, the load of route, the length of route. To perform modifications on a solution the information, I also need to quickly find some information.

For example,
Which route is a customer in?
What customers does a route have?
How many nodes are there in a route?
What nodes are in front of or behind a node?

Now, I am thinking to use the following structure to keep a solution.

struct Sol
{
    vector<short> nextNode;   // show what is the next node of each node;
    vector<short> preNode;    //show what is the preceding node
    vector<short> startNode; 
    vector<short> rutNum;
    vector<short> rutLoad;
    vector<float> rutLength;
    vector<short> rutSize;
};

The common size of each vector is instance dependent, between 200-2000.

I heard it is possible to use dynamic array to do this job. But it seems to me dynamic array is more complicated. One has to locate the memory and release the memory. Here my question is twofold.

How to use dynamic array to realize the same purpose? how to define the struct or class so that memory location and release can be easily taken care of?

Will using dynamic array be faster than using vector? Assuming the solution structure need to be accessed million times.

ildjarn
  • 62,044
  • 9
  • 127
  • 211
Jackie
  • 1,071
  • 2
  • 12
  • 17
  • Why do you have a struct of arrays of members, instead of an array of a struct with members? The latter is less confusing, less error-prone, and faster. – Mooing Duck Oct 07 '11 at 17:05
  • The information in each array is different, not for the same item – Jackie Oct 07 '11 at 17:41

3 Answers3

6

It is highly unlikely that you'll see an appreciable performance difference between a dynamic array and a vector since the latter is essentially a very thin wrapper around the former. Also bear in mind that using a vector would be significantly less error-prone.

It may, however, be the case that some information is better stored in a different type of container altogether, e.g. in an std::map. The following might be of interest: What are the complexity guarantees of the standard containers?

It is important to give some thought to the type of container that gets used. However, when it comes to micro-optimizations (such as vector vs dynamic array), the best policy is to profile the code first and only focus on parts of the code that prove to be real -- rather than assumed -- bottlenecks.

Community
  • 1
  • 1
NPE
  • 486,780
  • 108
  • 951
  • 1,012
  • Thanks for the answer. I like using vector, but if using dynamic array can make the code much faster, then I will choose it. That is what I mainly hope to know. Is there any open source code which we use for such comparison? – Jackie Oct 07 '11 at 16:50
1

It's quite possible that vector's code is actually better and more performant than dynamic array code you would write yourself. Only if profiling shows significant time spent in vector would I consider writing my own error-prone replacement. See also Dynamically allocated arrays or std::vector

Community
  • 1
  • 1
Mark B
  • 95,107
  • 10
  • 109
  • 188
0

I'm using MSVC and the implementation looks to be as quick as it can be.

Accessing the array via operator [] is:

return (*(this->_Myfirst + _Pos));

Which is as quick as you are going to get with dynamic memory.

The only overhead you are going to get is in the memory use of a vector, it seems to create a pointer to the start of the vector, the end of the vector, and the end of the current sequence. This is only 2 more pointers than you would need if you were using a dynamic array. You are only creating 200-2000 of these, I doubt memory is going to be that tight.

I am sure the other stl implementations are very similar. I would absorb the minor cost of vector storage and use them in your project.

DanDan
  • 10,462
  • 8
  • 53
  • 69