Arry elements with not consecutive indexes

[gallerto]

Hello,

I woul like to know If there is any way to allocate two positions of memory for a pointer to double but in such way that this positions are not consecutive.

What I really whant is to have one vector of two components where I can get the first component with the index 1, it means: VECTOR[1] but to get the second component I don't want to use the index two: VECTOR[2].

I would like to be able to get it using other index, for instance 10: VECTOR[10]

I dont want to allocate memory for the positions in the middle because of reasons of memory efficiency.


Thank you.

[Ganon11]

I don't think there is a way to do this without using two different variables (instead of arrays/vectors). Arrays are actually pointers that point to the first element of many - each time you use the [x] operators, you are accessing the memory x * (size of variable) ahead of that pointer. Thus, an array cannot be split up over many locations.

A vector, however, should be storing these elements in separate locations, holding the pointers to each location in its own array (or some similar implementation). However, you still cannot create a Vector with 2 elements and access the element at vector[10]. You may, however, be able to create a vector with room for 10 elements, but only add 2 or 3 at specified indexes.

[AdrianH]

Hmm, you could define your own vector like class that overloads the operator[]. You could also use map. I'm not sure how memory efficent it is, but the locations of the elements may or may not be side by side (most likely not) as this is a hash and according to Wikipedia is usually implemented as a balanced tree, which means that access to any elment is O(lg n), where n is the number of elements in the map. (lg = log base 2)

Just make the first template parameter an int (which is your key) and away you go. What looks like an array is really a map.

Also, this has more memory overhead than an array when you have many elements, but for a sparce array, it is pretty good.

Here is an example of how to use it: http://www.sgi.com/tech/stl/Map.html

Hope this helps.


Adrian

[gallerto]

I don't think there is a way to do this without using two different variables ( You may, however, be able to create a vector with room for 10 elements, but only add 2 or 3 at specified indexes.

That is what I do now, But it is not efficient in terms of memory.

Thank you anyway

[gallerto]

Hmm, you could define your own vector like class that overloads the operator[]. You could also use map. I'm not sure how memory efficent it is, but the locations of the elements may or may not be side by side (most likely not) as this is a hash and according to Wikipedia is usually implemented as a balanced tree, which means that access to any elment is O(lg n), where n is the number of elements in the map. (lg = log base 2)

Just make the first template parameter an int (which is your key) and away you go. What looks like an array is really a map.

Also, this has more memory overhead than an array when you have many elements, but for a sparce array, it is pretty good.

Here is an example of how to use it: http://www.sgi.com/tech/stl/Map.html

Hope this helps.


Adrian

Thank you but think that I can't do it in C. I don't use C++. I forgot to tell that.

[AdrianH]

Thank you but think that I can't do it in C. I don't use C++. I forgot to tell that.

C... C++, it is all the same :). The main differences are things like constructors and destructors, strong type casting, automatic passing of the object pointer and auto-destruction of automatic variables (variables allocated on the stack). Overloading is helpful but not 100% necessary and operator overloading is just syntactic sugar. Virtual functions are just function pointers. There is of course the libraries too.

I've designed and developed an entire subsystem in C for a production real-time system as I would have done in C++. Constructors and destructors were just functions. I've also made allocators and deallocators (new and delete) functions which just called malloc() and free().

If you want to make your own map in C, you can do it. Just implement a balanced tree algorithm.

Or you could google for a C library implementation. But be warned, if you do this for a school project and they expect you to do it yourself, I'm pretty sure that this is probably too complex a method for it and your prof/teacher will squash you like a little bug for plagiarism. :)


Adrian

[gallerto]

C... C++, it is all the same :). The main differences are things like constructors and destructors, strong type casting, automatic passing of the object pointer and auto-destruction of automatic variables (variables allocated on the stack). Overloading is helpful but not 100% necessary and operator overloading is just syntactic sugar. Virtual functions are just function pointers. There is of course the libraries too.

I've designed and developed an entire subsystem in C for a production real-time system as I would have done in C++. Constructors and destructors were just functions. I've also made allocators and deallocators (new and delete) functions which just called malloc() and free().

If you want to make your own map in C, you can do it. Just implement a balanced tree algorithm.

Or you could google for a C library implementation. But be warned, if you do this for a school project and they expect you to do it yourself, I'm pretty sure that this is probably too complex a method for it and your prof/teacher will squash you like a little bug for plagiarism. :)


Adrian

Mmmmm I have to say that all your ideas sound like chinish to me. I don't know what is a map. That is way I thought that it was C++.

It is not a school exercise. It is my first program in C but it is quite big (arround 6000 lines and still growing) (but I have a lot of experience in programming FORTRAN 95). I am writing a research program in an important laboratory to calculate aerodinamic forces.

I really need to increase the memory efficiency but it has to be with pointers because I wrote a lot of functions that expect to receive that pointers. In fact I am working with "double *****ArryOfFiveDimensions".

It would be very good if I didn't have to change all that funtions. Just allocate memory in a more efficient way.


Thankyou very much.

[AdrianH]

Mmmmm I have to say that all your ideas sound like chinish to me. I don't know what is a map. That is way I thought that it was C++.

It is not a school exercise. It is my first program in C but it is quite big (arround 6000 lines and still growing) (but I have a lot of experience in programming FORTRAN 95). I am writing a research program in an important laboratory to calculate aerodinamic forces.

I really need to increase the memory efficiency but it has to be with pointers because I wrote a lot of functions that expect to receive that pointers. In fact I am working with "double *****ArryOfFiveDimensions".

It would be very good if I didn't have to change all that funtions. Just allocate memory in a more efficient way.


Thankyou very much.

Are you saying that I sound like I’m speaking Chinese? :) I take that you mean that you don’t understand what I am saying, right?

It is interesting that you are playing with 5 dimensional arrays. What exactly do you need that for? That is pretty crazy stuff. Do you actually have a 5 dimensional array? What are the bounds on each dimension?

If you don’t want to change the functions, then you are stuck. You’re option is to either get more memory or get a new computer with more memory.

If you are not using any of the incompatible new C99 standard, you could may be able to just rename all your .c files to .cpp and use C++ (pre C99 C standard, C was a subset of C++).

If you are using a 5 dimensional array and this is a sparse array, you will have to change the interfaces that take a “double *****” with a “map<size_t, map<size_t, map<size_t, map<size_t, map<size_t, double> > > > >”. You could make this a lot cleaner using “typedef map<size_t, map<size_t, map<size_t, map<size_t, map<size_t, double> > > > > double_p5;” and use “double_p5” to replace “double *****”.

Please note that your programme will be slower in some sense as each map has a O(lg n) access time. This means for a map that has n elements, it will take lg n (rounded up to an integer) times longer to access than if it were a O(1) access time which is the access time of an array.

However, in your situation, a sparse 5D array may consume a lot of memory, requiring a lot of swapping to and from disk which would be far slower than using a map.

I am a contractor, and for a small fee, I could help you migrate your code. Send me a PM if this is something you would be interested in.


Adrian

[gallerto]

Are you saying that I sound like I’m speaking Chinese? :)

Yes. Sorry for the ortography.

It is interesting that you are playing with 5 dimensional arrays. What exactly do you need that for? That is pretty crazy stuff. Do you actually have a 5 dimensional array? What are the bounds on each dimension?

Yes I do. My arrys are like this ARRY[ti][xi][yi][zi][vi]. They store the evolution of the velocity components inside a fluid domain. The first four indexes are the time and space coordinates of the points and the last one correspond to each one of the components of the vector of the velocity. It means that what my arrys contain is the evolution of a 3D vectorial field.

When I started the program I decided to do it like this because it is very easy and similar to the phisic plane. But now it I know that maybe it is not a good idea. I have to waste a lot of memory for the pointers. I did it because I used FORTRAN before C and in FORTRAN you don't have that problem. Multidimensional arrys work in a different way in fortran. But when I started using multidimensional arrys in C I didn't still undertand very well what I was doing.

Now it is to late to change it. My program has arround 7000 lines and my grant will finish soon. I don't have time to change all the program. Anyway the program currently works with any problem of memory at all. The problems could arrive years later when the technology improves and the number of points of the vectorial field increases.

Now I just have an arry of 10x100x100x10x3 elementes more or less.

I will just leave a report with recommendations for future improvement of the program.

If you are not using any of the incompatible new C99 standard, you could may be able to just rename all your .c files to .cpp and use C++ (pre C99 C standard, C was a subset of C++).

In fact all my files are .cpp and I compile them as cpp with Devc++. I think that the problem is that I don't have time to change all the code neither to lear how to do all that things you sugest.

I allways learnt to program on my own. I have some little lacks.


Thank you very much for all your sugestions.

[AdrianH]

Are you saying that I sound like I’m speaking Chinese? :)

Yes. Sorry for the ortography.

No prob. Once I looked up what orthography was, I understand what you are now saying.

Yes I do. My arrys are like this ARRY[ti][xi][yi][zi][vi]. They store the evolution of the velocity components inside a fluid domain. The first four indexes are the time and space coordinates of the points and the last one correspond to each one of the components of the vector of the velocity. It means that what my arrys contain is the evolution of a 3D vectorial field.

When I started the program I decided to do it like this because it is very easy and similar to the phisic plane. But now it I know that maybe it is not a good idea. I have to waste a lot of memory for the pointers. I did it because I used FORTRAN before C and in FORTRAN you don't have that problem. Multidimensional arrys work in a different way in fortran. But when I started using multidimensional arrys in C I didn't still undertand very well what I was doing.

Now it is to late to change it. My program has arround 7000 lines and my grant will finish soon. I don't have time to change all the program. Anyway the program currently works with any problem of memory at all. The problems could arrive years later when the technology improves and the number of points of the vectorial field increases.

Now I just have an arry of 10x100x100x10x3 elementes more or less.

I will just leave a report with recommendations for future improvement of the program.

Are these arrays static, meaning, they do not change in dimension? If this is true, then you are right about the pointers wasting space. However, if this is dynamic, then the vectors will do you more good than harm.

If they are static though, then you could allocate your array on the stack and pass these things around as arrays, but you would have to increase your base stack size to be > 23Mib (10*100*100*10*3*8). The pointer space saved would be (10+10*100+10*100*100+10*100*100*10)*4 which is just over 4.2Mib. I'm not sure if it is worth it though.

If you are not using any of the incompatible new C99 standard, you could may be able to just rename all your .c files to .cpp and use C++ (pre C99 C standard, C was a subset of C++).

In fact all my files are .cpp and I compile them as cpp with Devc++. I think that the problem is that I don't have time to change all the code neither to lear how to do all that things you sugest.

What you described sounds like it is not all that sparse of an array. I don't know if what I suggested would have helped you actually.

I allways learnt to program on my own. I have some little lacks.


Thank you very much for all your sugestions.

No prob. We all have those (lacks and suggestions ;)).


Adrian

[gallerto]

Are these arrays static, meaning, they do not change in dimension? If this is true, then you are right about the pointers wasting space. However, if this is dynamic, then the vectors will do you more good than harm.

They are dinamic, of course.


What you described sounds like it is not all that sparse of an array. I don't know if what I suggested would have helped you actually.

Not the arry I descirbed but in the middle of the program i work with sparse arrys. For instace when i calculate the pressure I only need it in the first and last values of the indexes xi,yi and zi.

No prob. We all have those (lacks and suggestions ;)).

Thank you anyway for the interest that you showed