solver-ginsberg: Faster dictionary lookup
What?
Improve performance of solver-ginsberg
on dictionary lookup. No impact on external interfaces.
Why?
Because this is where the solver spends most of its time, see flamegraph. This is 10x faster than previous solution but it's still slow.
How?
Ideas:
-
Optimise
Trie
. The currentTrieNodeIterator
is not optimal when using it with pattern (when character is not a wildcard it doesn't go directly to the node, it just iterates until it finds it, which is not great). -
Implement removal of non matching patterns in
Trie
and use aTrie
as the current cache instead of simpleArrayList
. This would allow to refine trie, upon assignment or assignment probe which should be faster than current solution (lookup for the matching patterns in the initial candidates trie, cache result into anArrayList
which is cleared every time). Although it can be slower upon backtrack when the trie must be rebuilt. Note that if idea 1 speeds up things a lot, it might become useless to cache result.
Also, check other Trie
implementations: Apache Commons Collections.
Edited by Antoine Belvire