• Advertisement
Sign in to follow this  

List.Sort() lag

This topic is 732 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement

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.

Edited by Nanoha

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Edited by SpikeViper

Share this post


Link to post
Share on other sites

 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.

Share this post


Link to post
Share on other sites
So, instead of checking each chunk for if its close to the player, check groups of chunks, to reduce the amount of sorting?
Edited by SpikeViper

Share this post


Link to post
Share on other sites

 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.

Share this post


Link to post
Share on other sites

 

 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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement