koobas.hobune.stream
The question is answered, right answer was accepted
What's more efficient - ordering a list, or finding the smallest value?
At the moment, my enemy regularly checks all buildings in the scene and puts them in a dictionary with their distance from the enemy. When it wants to find which target to attack, it orders the dictionary in ascending order of distance using LINQ and returns the first building in the list.
My question is this: is it more efficient to do it this way, or more efficient to iterate through the list and return the shortest distance? And if it's the latter, could you please give me an example of how I would implement it - is it just iteration?
Thanks!
AFAI$$anonymous$$, there isn't any sorting algorithm whose complexity is less than O(n) which is the complexity of the loop needed to find the smallest value, so obviously, finding the smallest value is the way to go I$$anonymous$$O.
If you still want to sort the buildings, then you should "do it" when inserting a new element (but I don't believe you can do it with a dictionary since elements are not ordered)
Thanks, finding the smallest value was my decision. It's just that I'm aware that iteration isn't very efficient so wondered how advanced C# LINQ ordering algorithm is. Thanks!
if you are after performance, in general avoid sorting things if you can, especially if you are doing it often. pre-sorted lists can help speed things up in some cases, but in your case, the order is dynamic.
Its quicker to traverse through your list of objects once and find the closest. just make a float closestDistance variable. and start with it initialized to an improbably huge value. and a currentClosest object variable (or list index)
Then just loop trough all elements in your array or list.. and whenever you find an object with closer range than current closest, replace both variables with the new object/index from your list, and closest range.
A few other optimizations... cache the result.. you only need to update it when character (or ai moves more than say a couple of meters) or if one of your buildings or Ai is destroyed.
Awesome, thanks. As for the optimisations, I'll make sure to do that :)
On an unsorted array finding the smallest element is O(n) if its sorted its O(1) (just look at the first or last item in the list)
So realistically you are going to sort it either way well, depending on the size of the collection. It's just easier to sort and take the first or last than faffing.
he asked for most efficient, not easiest. Granted...using a sort function would be easiest. Sorting would only be 'faster', if it could be pre-sorted, then not need sorted again. But as his environment may be changing from frame to frame (characters moving / dying)... he'd have to keep re-sorting the list all the time.... which would be much slower than just traversing an array or list. especially if using a library to do the sorting
scanning array/list visits each data point only once. Sorting a list will visit each data point multiple times. (some algorithms much worse than others) Based on each use-case you can probably add optimizations for how often you need to check the list or re-sort it.
And I answered about the time complexities of both and said that for the most part it shouldn't matter.
Either the list is sorted or it probably should be maintained as sorted to make your life easier.
If its a one time operation then yes just iterating over the collection in linear time would be the best but again, most of the time using modern computers on average sized sets it's not really even something you should worry about.
