Fast access dynamic list [SOLVED]
-
On 01/09/2014 at 11:11, xxxxxxxx wrote:
User Information:
Cinema 4D Version: 14
Platform: Mac OSX ;
Language(s) : C++ ;---------
I created a plugin that reads two sets of values from a file.
Since I can't know in advance how many values are in the file, I implemented the storage of those values as two linked lists structures.
It is working fine but the lists can easily contain thousands of values.
I have to access item X of list #1 and use that value to serve as index to access item Y of list #2.
Since they are both linked lists, I have to access them sequentially, with code that looks like this:LONG Get_Index(LONG n) { store_index* cur=store_index_list; while (cur) { if (n==0) return cur->index; cur=cur->next; n--; } return NULL; }Is there any way to store values dynamically (since I don't know the size of the list in advance) that I can access in a very fast way?
-
On 01/09/2014 at 11:19, xxxxxxxx wrote:
Would a BaseContainer be efficient for this?
-
On 01/09/2014 at 12:15, xxxxxxxx wrote:
Ok, it worked PERFECTLY. I love BaseContainers
Had to change a lot of code, but it is FAST, very FAST now
-
On 01/09/2014 at 13:56, xxxxxxxx wrote:
While you have your solution, it should be noted that there are much better algorithms for indexing into data sets. Hashes and key/value are some of the better ways quickly to get to one piece of data in a list using some other criteria (from another list, possibly). Linked lists are useful but as you can see even with using C4DAtoms, they require a linear search using GetNext() or GetPrev(). Very slow and O(n) for getting from the beginning to the nth item on criteria. Model your data storage type for the best performance on that type of data and not just use the easiest implementable storage solution.
-
On 01/09/2014 at 15:30, xxxxxxxx wrote:
I agree completely.
In this case, I needed a method that was fast but also dynamic and I can't predict the size of the list.
Otherwise I could create lists that I could sort and search with binary search methods, for instance. -
On 01/09/2014 at 17:51, xxxxxxxx wrote:
why not using std::vector? "you can avoid the linked list"
-
On 02/09/2014 at 03:10, xxxxxxxx wrote:
How does it work?
Will it store the vectors in a list and I can access them directly?
Is it dynamic?
I also need a dynamic list of LONG values that I can append values to and access randomly.(I already solved it using BaseContainers but I would like to know different solutions)
-
On 02/09/2014 at 04:25, xxxxxxxx wrote:
Maxon does not suggest using the std library. Use the BaseArray template class instead. It even
seems to be faster than the std classes, Frank made some benchmarks a while ago and posted them
here.BaseContainers are implemented like a list, not a hash map and are therefore quite slow when
it comes to accessing items in the containers with the Get~() methods (they re-iterate from the
start of the container until a matching ID is found).Best,
-Niklas -
On 02/09/2014 at 04:33, xxxxxxxx wrote:
Well, changing from linked lists to BaseContainers speeded up things a few hundred times.
Would it be faster using BaseArrays?
Are they dynamic? I mean, can I add values to them without knowing in advance how many values will I read? -
On 02/09/2014 at 04:38, xxxxxxxx wrote:
For what my non-programmers knowledge is worth, I use std library objects quite a bit in my plugins, if for the reason just because they're standard. I've particularly used the std::vector a bit, and haven't had any problems with them.
Not sure what your programming skill level is so parden my igrnorance if you already know, but an example of using a std::vector container could be something like:
// need the vector header file somewhere in your code #include <vector> // create a vector container std::vector< LONG > MyLongContainer; // the container does not come 'sized' automatically, // you will need to do this somewhere in your code MyLongContainer.resize(5); // fill container indexed values (note that index values start at 0) MyLongContainer[0] = 27; // random number MyLongContainer[1] = 65; // random number MyLongContainer[2] = 196; // random number MyLongContainer[3] = 6; // random number MyLongContainer[4] = 13; // random number // print container values for(int i = 0; i <= MyLongContainer.size()-1;) { GePrint("MyLongContainer[" + LongToString(i)+ "] = " + LongToString(MyLongContainer[i])); i++; }That will probably work straight as it is in a function if you want to try it. Here's also an example that takes the std::vector a little further:
\\ lets create a container array made of a std:pair object to our \\ vector container. The pair object is made up of two variable \\ types that you can assign (hence pair) - so it's a container of pairs std::vector< std::pair< LONG,String > > MyLongContainer; MyLongContainer.resize(5); MyLongContainer[0].first = 27; // pair number MyLongContainer[0].second = "Pair 1"; // pair name MyLongContainer[1].first = 65; // pair number MyLongContainer[1].second = "Pair 2; // pair name MyLongContainer[2].first = 196; // pair number MyLongContainer[2].second = "Pair 3"; // pair name MyLongContainer[3].first = 6; // pair number MyLongContainer[3].second = "Pair 4; // pair name MyLongContainer[4].first = 13; // pair number MyLongContainer[4].second = "Pair 5"; // pair name for(int i = 0; i <= MyLongContainer.size()-1;) { GePrint("MyLongContainer[" + LongToString(i)+ "] = " + LongToString(MyLongContainer[i].first) + ": " + MyLongContainer[i].second); i++; }Barring any mistakes in the code, the above should also work as is. Hope that is of some help. Cheers,
WP.
-
On 02/09/2014 at 05:28, xxxxxxxx wrote:
Yes, BaseArrays are dynamic. Very similar interface to std::vector, but conforms the Maxon naming
conventions and does not use C++ exceptions, unlike the std libraries.@WickedP: You do not necessarily need to use resize(), you can just use std::vector::push_back()
if you don't know the number of elements already. If you think you know how many elements you
need at least, you can use std::vector::reserve() to suggest an initial capacity of the vector, it's size
will still be 0 after calling it though.The BaseArray class has the same functions, Resize() and EnsureCapacity().
Simple example for triangulating a Polygon object.
Int32 polygonCount = op->GetPolygonCount(); const CPolygon* polygons = op->GetPolygonR(); maxon::BaseArray<CPolygon> triangles; triangles.EnsureCapacity(polygonCount); for (Int32 index=0; index < polygonCount; ++index) { const CPolygon& poly = polygons[index]; triangles.Append(CPolygon(poly.a, poly.b, poly.c)); if (poly.c != poly.d) triangles.Append(CPolygon(poly.c, poly.d, poly.a)); }Best,
-Niklas -
On 02/09/2014 at 06:09, xxxxxxxx wrote:
Howdy,
Originally posted by xxxxxxxx
...Maxon does not suggest using the std library...
I've heard that many times, but what is the reason for not using std library?
Adios,
Cactus Dan -
On 02/09/2014 at 07:21, xxxxxxxx wrote:
In your example, Niklas, you used triangles.EnsureCapacity(polygonCount);
But I really don't know in advance how many elements I will be storing.
Can I simply Append items to the end and the array will grow?Is it really faster that using BaseContainers? Because as it is now, it is working fast (but not very, very fast when dealing with hundreds of thousands of values, or more).
-
On 02/09/2014 at 13:55, xxxxxxxx wrote:
@Rui
Arrays can use either a known size value. Or not use a known size value.
This is in R13 code. But I'm guessing the R14++ BaseArrays have the same option.LONG arrsize = 3; GeDynamicArray<LONG>myarray(arrsize); //With known array size GeDynamicArray<LONG>myarray; //Without known array size@Dan
I asked the same question a long time ago and one of the devs said that the reason the std library is not supported is due to the debugging.
I don't remember his exact words. But it was something along the lines of the debugging errors are not always compatible or reliable in relation to the C4D SDK. So they can't be held responsible for it, or support it.
And I think he also mentioned possible problems when using things like try & catch too.I use it as well as Boost and Win32 stuff all of the time. And never have any problems.
But I also know that when I do that I'm on my own. And Maxon can't offer any help if I have a problem.-ScottA
-
On 03/09/2014 at 01:43, xxxxxxxx wrote:
The GeDynamicArray class is extremely inefficient and very slow, I do not recommend to use it.
@Rui: Yes, EnsureCapacity() is just a hint to the array, but you can leave it out as well.
@Dan: What Scott said is right, but I don't remember either what exactly I was told about it.
You could get problems using the std library and not enabling exception handling. And in the end,
I just think they don't want to support it because that would mean additional work.Best,
-Niklas -
On 03/09/2014 at 07:15, xxxxxxxx wrote:
I'm still using R13 Niklas. So I can't use the new BaseArray stuff. That's why I'm still not very familiar with them.
If I need speedy arrays for something. I have to go off the support grid and use a vector array.I've been told there's a hack to make BaseArrays in R13. But I could never get it to work.
-ScottA
-
On 03/09/2014 at 16:24, xxxxxxxx wrote:
Howdy,
Originally posted by xxxxxxxx
...You could get problems using the std library and not enabling exception handling...
Ah, OK I see. Yes, I got that warning in Visual Studio, and enabling exception handling did get rid of that.
Adios,
Cactus Dan -
On 07/09/2014 at 09:38, xxxxxxxx wrote:
I am completely relying on the STL and Effex runs as stable as it can get.
I am only using C4D structures when I directly modify C4D data. -
On 07/09/2014 at 10:45, xxxxxxxx wrote:
Well, it's the official Maxon side. I never experienced anything bad that I could pinpoint on using
the standard library, either. -
On 07/09/2014 at 11:07, xxxxxxxx wrote:
Yep, I think it is as you said, posing an additional support criteria. Well, it's understandable I guess