Skip to content
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

Cache list of nodes in LocalForbiddenSequence #51

Open
Whebon opened this issue May 6, 2024 · 0 comments
Open

Cache list of nodes in LocalForbiddenSequence #51

Whebon opened this issue May 6, 2024 · 0 comments

Comments

@Whebon
Copy link
Contributor

Whebon commented May 6, 2024

The propagate method of LocalForbiddenSequence starts by collecting a list of nodes:

function propagate!(solver::Solver, c::LocalForbiddenSequence)
    nodes = get_nodes_on_path(get_tree(solver), c.path)
    #...
end

This is the bottleneck of this propagate method. Furthermore, in a uniform tree, this list will always be the same. So re-computing the list is unnecessary.

Why is this not here yet?

In the GenericSolver, hole instances can be replaced during search. So references might become invalid. Additionally, constraints cannot be stateful in the GenericSolver because the constraints are shared by reference among different active solver states.

This optimization will only be valid in the UniformSolver. So it may require a new type of local constraint: StateLocalForbiddenSequence.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant