Use a hash set for the closed state list#29
Conversation
|
Thanks for the PR, will need some time to review it and let you know |
|
Hi @btdubs thanks again for the PR. I reviewed it today. I have a couple of reservations:
However I think it's a valuable change because it's faster. I have also been considering moving to a more recent c++ standard and c++11 provides lambdas, auto, range iteration and various smart pointers that would improve the current code somewhat. I think the best solution for my users would be something like this:
I think it would be okay to provide a preprocess flag so that the use of the set instead of the list is opt-in and zero cost if you do not use it. I think the way you handled adding the Hash function is easy to use and I have no problem with it. Anyway just wanted to share my thinking with you. I have not decided the best way to move forward but would appreciate any ideas. |
| { | ||
| stream << tiles[i]; | ||
| } | ||
| size_t state_digits; |
There was a problem hiding this comment.
I may be misunderstanding but I think this should be more like:
return std::hashstd::string{}(stream.str());
There was a problem hiding this comment.
Each state is defined by an ordering of the tiles. Turning them into a number is a unique hash because it would be another state if it shared the same ordering of digits. The has of a size_t is just identity function I believe. Turning the string into a hash would also work but seemed less intuitive. I'm fine either way.
There was a problem hiding this comment.
You are right. I chose to refactor it a little but it is now somewhere between your solution and mine
|
Those seem like reasonable steps although I would say for 3 the burden of creating a hash is low because even with a high collision hash function, you are likely to see performance improvements. The lookup at collisions is a search along a list which is likely the same performance as reading the closed list as a vector. |
|
Thank you again for this contibution. I closed the PR rather than merging as I made some changes and merged it manually. |
|
Great, thank you. Glad I could contribute back. |
The A* library uses a closed list which is slow to look up if a state has been visited. I've changed to a hash set via the unordered_set which speeds up search.
In my use case, this took the mean search time from 0.0141 seconds to 0.0016 seconds and the max search time from ~2.8 seconds to ~0.34 seconds.
I updated the examples to also use the hash. If there is a better way to handle the hash function let me know. I had trouble using the hash template specialization with the other templating in the library, and this way became easier.