Skip to content

solver-ginsberg: Faster dictionary lookup

Antoine Belvire requested to merge feature/53_faster_dictionary_lookup into master

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

Merge request reports