Contents    Page-10    Prev    Next    Page+10    Index   

Finite Differencing for Set Operations

Finite differencing can be especially useful in optimizing set operations. Consider the following expression that is used in solving the ``k queens'' problem:[D.R. Smith, KIDS: A Semiautomatic Program Development System, IEEE Trans. Software Engineering, vol. 16, no. 9, Sept. 1990, pp. 1024-1043.] i ∈ range(part_sol) ∧ i ∈ { 1 .. k } This can be transformed to: i ∈ setdiff( { 1 .. k } , part_sol )

A variable unoccupied_rows can be introduced for this expression. Its initial value is the set { 1 .. k } .

An update to part_sol (by recursive call), part_sol = append( part_sol , i) leads to a corresponding change to unoccupied_rows unoccupied_rows = unoccupied_rows - {i} This incremental update may be much cheaper than doing the original range computation or set difference every time.