Potential performance issue with 2D-array randomization #2
Description
I've been trying to compare PyVSC and constrainedrandom's performance when it comes to randomization of 2D-arrays. The test case is a "checkerboard randomization", where each field can be 0 or 1, but cannot have the same value as its neighbours.
Consider the following implementations
PyVSC
import vsc import timeit @vsc.randobj class Checkers(): def __init__(self, N): self.N = N self.board = [vsc.rand_list_t(vsc.rand_uint8_t(), self.N) for _ in range(self.N)] @vsc.constraint def con_values(self): for row in self.board: with vsc.foreach(row) as c: 0 <= c and c <= 1 @vsc.constraint def constraints(self): for i in range(1, self.N): with vsc.foreach(self.board[i], idx=True) as j: if j == 0: pass (self.board[i][j] != self.board[i-1][j]) and (self.board[i][j] != self.board[i][j-1]) def benchmark(): numRounds = 10 for N in (4, 8, 16, 32, 64, 128, 256): t = timeit.timeit(stmt='c.randomize()', setup=f'c = Checkers({N})', number=numRounds, globals=globals()) print(f"N={N:4d}: Runtime: {t/numRounds}") benchmark()constrainedrandom
from constrainedrandom import RandObj import timeit class Checkers(RandObj): def __init__(self, N): super().__init__(max_iterations=1000) self.N = N for i in range(self.N): self.add_rand_var(f"list{i}", domain=range(2), length=self.N, disable_naive_list_solver=True) for i in range(1, self.N): for j in range(1, self.N): self.add_constraint((lambda row1, row2: row1[j] != row2[j]), (f"list{i-1}", f"list{i}")) self.add_constraint((lambda row: row[j-1] != row[j]), (f"list{i}", )) def benchmark(): numRounds = 10 for N in (4, 8, 16, 32, 64, 128, 256): t = timeit.timeit(stmt='c.randomize()', setup=f'c = Checkers({N})', number=numRounds, globals=globals()) print(f"N={N:4d}: Runtime: {t/numRounds}") benchmark()The average runtimes reported for the two on my machine are as follows. The fields labeled "DNF" took so long that I didn't bother waiting for them to complete
| N | PyVSC | constrainedrandom |
|---|---|---|
| 4 | 0.008 | 0.001 |
| 8 | 0.029 | 1.265 |
| 16 | 0.112 | 45.786 |
| 32 | 0.305 | DNF |
| 64 | 1.208 | DNF |
| 128 | 5.371 | DNF |
| 256 | 22.421 | DNF |
As you can see, the performance of PyVSC seems vastly superior to the performance of constrainedrandom. However, I am unsure whether my implementation with constrainedrandom is optimal, but I haven't found a better way of implementing 2D-arrays and randomization thereof.
Is there a better way of constraining this problem that would lead to better performance with constrainedrandom?