mgrettondann/partridge-cpp
1
0
Fork 0
Code Issues 4 Pull Requests Activity

solver: evaluate failed-state memoization #9

New Issue
Open
opened 2026-07-30 16:23:34 +01:00 by mcp · 0 comments
mcp commented 2026-07-30 16:23:34 +01:00
Collaborator
Copy Link
Copy Source

Background

Different completed arrangements beneath the active frontier may lead to the same future subproblem: identical skyline, board dimensions and remaining multiplicities.

A transposition table could avoid re-solving such failed subproblems, but hashing and memory traffic may cost more than it saves.

Proposed work

  • Define a canonical state key containing skyline and remaining counts.
  • Instrument duplicate-state frequency before enabling a large cache.
  • Evaluate bounded per-worker and shared caches.
  • Consider reflection canonicalization where cheap.
  • Provide a configurable memory limit and deterministic disabled mode.

Acceptance criteria

  • Key equality is sufficient for equivalent future search.
  • Hash collision handling cannot cause false pruning.
  • Report hit rate, memory usage and elapsed-time effect.
  • Do not retain memoization by default unless it provides a measured net benefit.
## Background Different completed arrangements beneath the active frontier may lead to the same future subproblem: identical skyline, board dimensions and remaining multiplicities. A transposition table could avoid re-solving such failed subproblems, but hashing and memory traffic may cost more than it saves. ## Proposed work - Define a canonical state key containing skyline and remaining counts. - Instrument duplicate-state frequency before enabling a large cache. - Evaluate bounded per-worker and shared caches. - Consider reflection canonicalization where cheap. - Provide a configurable memory limit and deterministic disabled mode. ## Acceptance criteria - Key equality is sufficient for equivalent future search. - Hash collision handling cannot cause false pruning. - Report hit rate, memory usage and elapsed-time effect. - Do not retain memoization by default unless it provides a measured net benefit.
Sign in to join this conversation.
No Branch/Tag Specified
Branches Tags
Labels
No items
No labels
Milestone
No items
No Milestone
Assignees
Clear assignees
mcp mgrettondann (Matthew Gretton-Dann)
No Assignees
1 Participants
Notifications
Due Date
No due date set.
Dependencies

No dependencies set.

Reference: mgrettondann/partridge-cpp#9