4 ms·
> The fact that Board is immutable means we don't have to perform any cleanup when backtracking. What does it mean? When one of the branches is stuck in a dead
by kevinwang 8y ago
> The fact that Board is immutable means we don't have to perform any cleanup when backtracking. What does it mean? When one of the branches is stuck in a dead end, we must slowly go back, trying to take all other possible moves. Mutating Board would require cleaning it up. Immutable Board can be simply thrown away once it's no longer needed. Also immutability enables concurrent exploration (soon to come).
Someone correct me if I'm wrong, but I believe backtracking actually requires a mutable array and would be faster (since you wouldn't have to build 100x100 arrays all the time: you could just build the 100x100 array one time and mutate it.)
- taeric 8y agoBacktracking doesn't require a mutable anything, per se. Just the ability to get back to where you were. Now, it can be somewhat easily reasoned that a mutable board can more quickly let you go back to previous settings, since you could potentially lose the GC steps of the immutable version. Of course, the immutable is more easily reasoned for parallelizing, since you can just throw paths to different workers without them stepping on each other. So, tradeoffs.
- kevinwang 8y agoMy argument is that the version with a single mutable board would be 100x100=10000 times faster, since you won't need to make a new array for every move
- taeric 8y agoOh, in that, I agree. I would hope a more friendly datastructure would be used for the immutable version. Data sharing should be possible.