search

fiveham / Sudoku_Solver

Solve sudoku puzzles by representing the puzzle as a bipartite graph of truth-claims about cells' values and rule-statements that have exactly one true neighbor and removing edges as information is added
MIT License
0 stars 0 forks source link

Traversing a BackedSet is O(universe size), which is inefficient for small sets #19

Closed fiveham closed 7 years ago

fiveham commented 8 years ago

Storing a collection of indices at which the BackedSet's internal mask has a set bit is faster but with a greater memory cost.

fiveham commented 8 years ago

Tracking a list of relevant indices also increases the time cost for single additions and single removals.

fiveham commented 7 years ago

The idea of maintaining a parallel collection of indices into the Universe/mask is developed on the branch fast-iteration.

While iteration performance is improved, non-lazy maintenance of the index-pool requires slowing bulk operations by iterating over the other collection passed as an argument to a BackedSet's method or iterating over the BackedSet itself, eliminating the mask-based improvement to bulk-operation methods' performance.

Slower iteration will be retained in order to maintain the speed of bulk operations, since having faster bulk operations is the reason for BackedSet to exist.