Currently, I have a list that hits around 15,000 objects that is sorted using
toLoad.Sort(delegate (Vector4 first, Vector4 second) { return first.w.CompareTo(second.w); });
As expected, this generates a bit of lag. I was wondering if there are any better data types to store so much (that can still be sorted, of course). I was also wondering if the way I'm sorting it is part of the problem.
How are you adding those objects? Perhaps something that keeps the list ordered all the time will work better. I would think that if it is possible it's probably better to insert the item int he correct position as you add it than it is to add to the end and then sort. You'd need to use a container that supports insertion like a linked list.
How are you adding those objects? Perhaps something that keeps the list ordered all the time will work better. I would think that if it is possible it's probably better to insert the item int he correct position as you add it than it is to add to the end and then sort. You'd need to use a container that supports insertion like a linked list.
I'm adding them with this:
toLoad.Add(new Vector4(x, y, z, distanceSq));
I want the closest ones (ones with smallest distance) to load first, Problem with using something like a sorted dictionary is sometimes 2 objects are at the same distance, and you can't have 2 identical keys.
Yeah, if the list of objects is "temporally coherent", then you can speed up sorting by using a sorting algorithm that can take advantage of that (one that is faster with partially sorted list).
The data structure you mentioned is called "multimap" I believe, there doesnt seem to be one in C# by default, but Im sure you can find an implementation (or create one yourself). Assuming that is what you actually need.
Then of course you can just try to find a faster sorting algorithm, or use multithreading, if nothing else works.
Probably if you make your vectors smaller in terms of memory, and ensure there is not some weird C# garbage collection slowing you down, that might help.
There are sorted containers. In C# the built in sorted containers are SortedList or SortedDictionary, depending on what data you are storing.
You will still pay the cost of sorting, but the cost is paid at insertion time.
If possible, organize your containers so they can be kept around and don't need to be re-sorted.
As others mentioned there are also many different sorting algorithms. if you know certain useful properties of your objects there may be better sorting algorithms. For instance, if your list is mostly sorted already is probably to run the InsertionSort or similar algorithm. By default C#'s list Sort() uses insertion sort, heapsort, or quicksort depending on the size of the container.
Yeah, if the list of objects is "temporally coherent", then you can speed up sorting by using a sorting algorithm that can take advantage of that (one that is faster with partially sorted list).
The data structure you mentioned is called "multimap" I believe, there doesnt seem to be one in C# by default, but Im sure you can find an implementation (or create one yourself). Assuming that is what you actually need.
Then of course you can just try to find a faster sorting algorithm, or use multithreading, if nothing else works.
Probably if you make your vectors smaller in terms of memory, and ensure there is not some weird C# garbage collection slowing you down, that might help.
I tried a multimap implementation, and is was actually quite a bit slower than the list.
When I use the delegate to sort, is that delegate being thrown into the GC each time?
Frob, I'm using a loop to find all the chunks within range and adding them to the list. The problem is, since its a loop, if I don't sort it the planet will load row by row, rather than closest to the player.
around 15,000 objects ... I'm using a loop to find all the chunks within range and adding them to the list.
Good to know. So you cannot preserve the list and it is still a one-time use, so using a sorted container is probably not useful.
I don't sort it the planet will load row by row, rather than closest to the player.
That information would have been useful up front. Your data has natural properties that can be leveraged.
Then the next general advice is to use a spatial partitioning scheme (levels, zones, spatial hashes, bsp trees, quadtrees, octrees, etc) to reduce the problem set. Instead of going through all 15000 objects in your 'planet', contain them in a structural hierarchy or other divisions. This can reduce it to closer to the number actually needed rather than 15000 each time.
The problem is, since its a loop, if I don't sort it the planet will load row by row, rather than closest to the player.
You could also iterate through the planet chunks in an order that corresponds to distance from the player... This might be a more "algorithimically complicated" way to address your issue, but sorting won't be needed. Off the top of my head, I feel that the Bresenham's line algorithm (or a 3d equivalent) might work for this.
The problem is, since its a loop, if I don't sort it the planet will load row by row, rather than closest to the player.
You could also iterate through the planet chunks in an order that corresponds to distance from the player... This might be a more "algorithimically complicated" way to address your issue, but sorting won't be needed. Off the top of my head, I feel that the Bresenham's line algorithm (or a 3d equivalent) might work for this.
That sounds like the best way to do it, but I'm not exactly a math whiz.
