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

Noctis
  • 11,507
  • 3
  • 43
  • 82
Smileynator
  • 677
  • 8
  • 24

1 Answers1

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.

Community
  • 1
  • 1
Noctis
  • 11,507
  • 3
  • 43
  • 82
  • This has the corollary that in case 1 and 2 that you can just focus on readability. – Chris Jun 01 '15 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 01 '15 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. – Smileynator Jun 01 '15 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 01 '15 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 – Smileynator Jun 01 '15 at 11:25
  • put that in the question, it makes a bit more sense with that data. Having said that, I'm still not sure about the best solution. It should be fairly easy to put the code that does it in an isolated method, copy paste & change the collection type, and compare. Maybe someone else can shed more light, but testing would be the easiest way to tell – Noctis Jun 01 '15 at 11:31
  • I was kind of hoping for a more educated solution instead of blindly trying every collection known to see what happens. Ah well. Thanks for the advice, should i mark yours as the correct answer? – Smileynator Jun 01 '15 at 11:33
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/79310/discussion-between-noctis-and-smileynator). – Noctis Jun 01 '15 at 11:37