-
Notifications
You must be signed in to change notification settings - Fork 25
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Lithium should not try reductions which have already been tested. #52
Comments
For the following, I assume A long time ago, it was supposed to work as the following:
Some years ago, the optimization was dropped:
Thus, it is not a matter of a duplicated rounds, it is that we lost the ability to detect duplicated tries of certain particular reduction instances, and hence not needing to test them. |
Yep, you're right. The safest way is to introduce (or re-introduce?) a cache of what has been tried already. This would solve other redundant work issues like #57 too, although that's been fixed another way already. |
I can confirm that adding a cache is what is typically done for these types of algorithms. The DD algorithm has similar duplication and is therefore in practice always implemented with a minchunk (e.g. line) based cache. |
If we have a testcase containing
abc
, andbc
is the reduced result (--char
mode, strategy=minimize), the run will look like this:This final round of chunk size 1 will always be unneeded as long as the reduction in the previous round was only at the beginning. I think this will be true for all atom types (line/char/symbol) and strategies.
The text was updated successfully, but these errors were encountered: