solver-ginsberg: Faster dictionary lookup
Context
Implements #53 (closed).
Small improvements related to trie lookup and dictionary cache management.
Also, I looked at Apache Commons Trie implementation: It seems to only offer to filter on prefixes, not on more complex patterns. Maybe there is a way to extend it for our use case but I haven't found it. So, I'm not using for now.
Overall, gain is x2 in raw assignment speed. Which is still way slower than xwords-rs.
There are still areas to improve notably the prober: It's a shame the probe result is not reused.
What has changed?
Main Changes
croiseur-solver-ginsberg
- Improved trie lookup: Basically, avoid exploring children nodes when we know that they won't match pattern.
- Implemented deletion of non matching patterns in trie and checked if it was faster than iterating on the initial trie when probing candidates: It's not. Kept it though, it might be a basis for a faster implementation later.
- Improved cache management: Filter word cache on assignment.
- Avoided useless probes.
Edited by Antoine Belvire