0

I have a search method in my custom A* algorithm. It uses a collection to keep track of what the search is doing. For a set path i know i am doing the following with the collection: Contains 860x (lookup) Remove 91x Add 270x

The order or sorting does not really matter unless i can find a way to specifically order it. It is possible to generate a unique ID for each node based on X and Y value. Making a dictionary lookup possible.

Is there any way to calculate based on my method, what would be the best collection to use in this specific case?

thanks in advance, Smiley

3

1 Answer 1

2

The general census says:

  1. If you don't run into performance issues, leave it alone.
  2. If you do , but you can get away with it, leave it alone.
  3. If you do, but you can't (or you just love your code to be tight), benchmark it, and you'll find.

(Clarification: I didn't use the "premature optimization is the root of evil" reference, because I do think that there is place for optimization. Here's a good article about the subject).

From what you're saying, I doubt it'll make much change, unless you're running on a device with next to no resources, but again, unless you need it, for the above numbers, i doubt you'll see any difference.

Edit:
as per the chat room continuation, I would suggest looking into hashtable and dictionary. To be more specific, a Sorted Dictionary :) .
For interesting read about hashtable vs dictionaries in c#, you can look at this question and at this one.

Good luck, and feel free to post your results for others to learn.

8
  • This has the corollary that in case 1 and 2 that you can just focus on readability.
    – Chris
    Jun 1, 2015 at 10:18
  • 1
    Always focus on readability ... and if you MUST tweak it for performance, leave comments explaining the why, the when, the by whom, and any other thing that will help (I'd also comment the actual speed benefits of the tweak. If this sound like too much work, you probably didn't need to tweak it to begin with :) )
    – Noctis
    Jun 1, 2015 at 10:25
  • Well the whole pathfinding thing centers on performance. It should be running on just about any mobile device back to Ipad 1 (though it is no longer supported by apple) The search method is used to find the shortest path quickly. Most of this time is spend with the collection stuff that is going on, so any optimization should be good. As to what collection you use, i doubt it will make an impact on readability in any way. Jun 1, 2015 at 11:15
  • you'll be surprised how a poor choice of collections can hurt you in the future. back to question, did you benchmark the time it takes to perform on a slow device? (i'm not trying to be negative, just giving the general advice about this kind of things).
    – Noctis
    Jun 1, 2015 at 11:17
  • With this current system, no not yet. But performance is already taking long on Pc in comparison. (150ms for an easy search) Seeing how most of that time goes to simply allocating and searching that 1 collection, i would prefer to use something more efficient instead. There is not much won in the rest of the calculation and reasoning of the pathfinding Jun 1, 2015 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.