Copy 3-dimensional array to another 3-dimensional array

[mosahab]

How can I copy second and third dimension of a 3-dimensional array, which is absolutely a 2-dimensional array, into another 3-dimensional array?
The following code generate an empty array(b). The following is just concept code. The performance is also important that is why I used memcpy.

int a[ 12 ][ 51 ][ 4 ];
int b[ 20 ][ 51 ][ 4 ];  
int main()
   int i;
	for( i= 0; i< 12 ; i++)
	{
	    memcpy(b[i], a, sizeof(a));
        }
    return 0
}	

[kevinkjt2000]

for(int i = 0; i < 12; ++i)
{
   for(int j = 0; j < 51; ++j)
   {
      for(int k = 0; k < 4; ++k)
      {
         b[i][j][k] = a[i][j][k];
      }
   }
}

As far as performance goes calling a function adds a slight overhead for such a small amount of array data.
Performance in this particular code could be done by specifying optimization flags to the compiler.

[mosahab]

1-What about array of size [ 10000 ][ 51 ][ 4 ] with 3000 iteration in program?
2-Is your suggestion efficient?
3- Is my way of using memcpy can not be used with some amendment and would not work at all in this case?

[TheIdeasMan]

Hi mosahab,

I know I mentioned earlier about you doing multiple posts, but now I am seeing posts with different questions, that all seemed to be aimed towards the same thing. That is fine, I am not having a go at you here.

It is just that now I am thinking it might be better if you explained exactly what you are trying to do. I can't help thinking that if you think you need a 3 dimensional array, then there probably is a better way of doing it.

There are lots of ways of doing things: sometimes one's initial idea might not be the best way; those with more experience can help you with different ideas (use of algorithms or containers in C++ say).

Some questions :

Are you doing C or C++ ?

Your use of memcpy implies C, but you may not be aware of the C++ equivalent.

So you have 10000 objects which need to contain 51 by 4 pieces of data, what is the type of that data?

Is the number of objects known or fixed, or does it vary?

What operations / calculations do you need to do on the objects?

Do the operations need to be done to all the objects, or only some of them?

If you already have a brief, or the homework question, then post it here in full.

With the design of your code & the amount of data, I find it worthwhile to design the code with the need to cope with large amounts of data, but test it with a relatively small amount of data first. When that that works, test it with larger amounts of data. In terms of complexity, keep it simple to start with, then add complexity once you have each stage working.

Hopefully all this is of some help, I (& others) look forward to helping you out, once we have a decent goal to aim at. 8+)

[kevinkjt2000]

1-What about array of size [ 10000 ][ 51 ][ 4 ] with 3000 iteration in program?

Uhh what about such an array? (This question does not make much sense)

2-Is your suggestion efficient?

Whenever someone asks me this I tell them the order notation of the algorithm. O(n^3) which is to say the algorithm is cubic. (this is based on the dimensions of the array)
And the space taken up by the algorithm is only the size of the two arrays.
So in answer to your question: no. this is not efficient. I personally would never use a 3 dimensional array in a project that would require a O(n^3) algorithm.

3- Is my way of using memcpy can not be used with some amendment and would not work at all in this case?

Yes you can use old C functions if that is what you wish.

for(int i= 0; i < 10000 ; ++i)
{
   for(int j=0; j < 51; ++j)
   {
      memcpy(b[i][j], a[i][j], 4*sizeof(int));
   }
}

This is not any more efficient than the code I gave earlier. If anything it is less efficient because this function is being called 10000*51 times. Whereas, in my other code there would only be a local assignment operation. If you were to think about the CPU Assembly code there would be less jumps and returns without the function call. I think a good compiler with optimization turned on would optimize the code without too much worry though.

[mosahab]

@ TheIdeasMan (2451).
Glad to here you finally found I just need some immediate help because I am a beginner in C++.
1-I do not the equivalen of memcpy
2- Data are fix.
3-My problem as a whole is as following.
Do you know something about "Traveling Salesman Problem" (TSP). It is a salesman who must start traveling from one city to another city and sales its products (suppose it’s goods is enough for all the cities) and must just one time meet every city and come back to the first city while he go the lowest distance . Each city has 4 records: 2 for geographical X, Y, and one as index number and one for demand. These cities some time reach to 10000 or more in some hypothetical problem.
One solution to the problem is that generating different combination of these cities to reach the lowest distance that salesman travels. My problem flowcahrt would be as follow.
1. Generating a 2-dim array[10000][4] by random combination of cities (each array row for each city) and calculate the distance for each as the cost of soluton. This needs just sum() and sqrt() operation.
2. Do the step one for 20 times and put them all in a 3-dim array[20][10000][4] while putting the costs and the index of solution into a 2-dim array.
3. Sort 2-dim array of step 2 and extract 5 of them with the lowest cost solution.
4. By the 5 solution in step3 do the search in 3-dim array[20][10000][4] to find the equivalent solution. Delete the other 15 solution from the 3-dim array[20][10000][4].
5. For every 5 solution do every time put on in a new 2-dim array and do some random exchange in the rows and calculate it to reach the lowest cost. This needs at least 3000 exchange.
6. Finally the lowest cost solution report as best answer.



I do not know these mas description is whether helpful or just verbiage. But I am ready to response any question.

[mutexe]

i'd just have a class called City. and each City has a class inside it called Coordinate (or just a 2d array, whatever).

Then you could just work out the distances between each city using vector maths.

[zb0S216C]

You can copy a 3-dimensional array with a single loop:

int main( )
{
  int SourceArray[2][2][2] =
  {
    { { 1, 2 }, { 3, 4 } },
    { { 5, 6 }, { 7, 8 } } 
  };
  
  int DestinationArray[2][2][2] = 
  {
    { { 0, 0 }, { 0, 0 } },
    { { 0, 0 }, { 0, 0 } } 
  };
  
  int const Length( 2 * 2 * 2 );

  int *CurrentSource( &SourceArray[0][0][0] );
  int *CurrentDest( &DestinationArray[0][0][0] );
  for( int I( 0 ); I < Length; ++I, ++CurrentSource, ++CurrentDest )
  {
    *CurrentDest = *CurrentSource;
    std::cout << *CurrentDest << " ";
  }

  return( 0 );
}

Note that "int[2][2][2]" is theoretically the same as "int[8]."

_Wazzak

[TheIdeasMan]

Hi mosahab,

I don't know much about TSP, but I was reading about it here :

http://en.wikipedia.org/wiki/Travelling_salesman_problem

Hopefully you have already read / studied this.

If you haven't, I noted these points :

wiki wrote:

Exact algorithms

The most direct solution would be to try all permutations (ordered combinations) and see which one is cheapest (using brute force search). The running time for this approach lies within a polynomial factor of O(n!), the factorial of the number of cities, so this solution becomes impractical even for only 20 cities. One of the earliest applications of dynamic programming is the Held–Karp algorithm that solves the problem in time O(n^2 2^n)

wiki wrote:

Other approaches include:

Various branch-and-bound algorithms, which can be used to process TSPs containing 40–60 cities.

So it seems that brute force algorithms that try for an exact solution would only work for a small number of cities. That's why it seems to be wise to get a solution working with a small system first.

More practical solutions seem to use heuristics that give a high probability of being close to an exact solution.

Just curious about what your assignment said about how many cities the solution needs to work for. 10,000 seems to be a very mean & difficult target to achieve. Or is it one of the On-line problems, like online judge for example or Project Euler? If that is the case then I hope you realise that these problems are definitely not as trivial as they first seem.

For your basic Data Structure you could have a class, like mutexe said :

class City {
private:

double X; // The X ordinate of the position
double Y; // The Y ordinate of the position
std::size_t Index; 
std::size_t Demand; 

public:

// interface functions here

};

With your methodology (your problem flowchart), was this given to you as a hint, or did you think of it your self? Some of the solutions on the wiki page might be better - like Branch & Bound for example.

I have some problems with it :

So for your methodology to work, you might have only 8 cities, because the list of all the permutations would have 40,320 items in it (8 factorial) or 5,040 (7 factorial).

Step 1. You seem to want to store the random combination of the Cities and their associated info into one data structure - which doesn't make sense to me. Better to separate them into a City Table and a Route Table.

const unsigned int NumCities = 8;
// use City class shown above
City CityTable[NumCities];

Step 2. This seems to be the Route Table, which could be a 2d array - 20 by number of cities. But choosing only 20 random permutations, seems to be a very small sample out of a total of 20,160 which is only for 8 cities (8 factorial / 2) . Even though in step 5 you do 3000 more combinations, there is absolutely no way of knowing whether these 20 combinations are anywhere near being close to a good solution. By choosing 5 of these, seems only to further reduce the probability of a good answer. A permutation of one of the other 15 might prove better than the smallest of the 5 chosen.

class Route {
std::size_t Entry[NumCities]; // contains City Identifiers
double DistanceCost;
};

const unsigned NumRoutes = 20;

Route RouteTable[NumRoutes]; // put the random permutations in here

So this is much better because [20][8] plus [20][4] = 240, is much better than [20][8][4] = 640, and represents a big saving in memory usage and time to process.

Step 4. If the City table & Route Table are separate, then there is no need to go back and search for a corresponding route - you already have this.

For which ever method you choose in the end, here are two things you can use to help you:

There is the STL std::next_permutation algorithm which you could use to create routes, but you need to get rid of half of these because 1,2,3,4 is the same as 4,3,2,1 for example.

You can use std::push_back to put various routes into a std::vector of all the routes. Then go through and calc the cost for each route, using the info in the City Array.

Well hopefully all this is of some help, I look forward to seeing how you get on :-)

[JLBorges]

> Copy 3-dimensional array to another 3-dimensional array

#include <vector>
#include <string>

class City
{
    private:
        std::string name ;
        double X; // The X ordinate of the position
        double Y; // The Y ordinate of the position
        std::size_t Index;
        std::size_t Demand;

    public:

    // interface functions here

};

int main()
{
    typedef std::vector< std::vector< std::vector<City> > > array_3d ;
    array_3d first_array ;
    array_3d second_array ;

    // populate first_array with cities

    // copy first_array to second_array
    second_array = first_array ;
}

[TheIdeasMan]

@JLBorges

I am thinking the OP shouldn't have a 3d array for this problem, it seems he is trying to combine atomic City data along with combinations of Route data all into one data structure.

Moreover, I think the algorithm probably won't work: it uses too small a sample for it to give a valid answer IMO. I am not the best at maths or stats, but that's the way it seems to me.

It just occurred to me that if one numbers the cities from 1 to N, and only look at the combinations that start with 1 say, then the number of combinations is greatly reduced (divided by N?). After all we might want the TSP solution starting from 1 City, not from ANY City.

I am thinking this doesn't render my argument invalid, one can't ignore the vast majority of combinations for this type of problem IMO. The solution isn't that easy, that's why the wiki page refers to trials that take years of CPU time.

Any way what do you think? I am travelling in the right direction here :+), or do you have some different thoughts?

[JLBorges]

> I am thinking the OP shouldn't have a 3d array for this problem,

I was just answering the question posed in the title of the thread: how to copy a 3-dimensional array to another 3-dimensional array.

The travelling salesman problem is known to be NP-complete. It is one of the earliest known NP-hard problem and has been the subject of intense study for over eighty years. There is no dearth of literature on the subject - one just has to search for it.

[TheIdeasMan]

Alright, thanks & cheers.