## SICP – cap. 2 – Sequenze come interfacce convenzionali – 53 – esercizi

Continuo da qui, copio qui.

Exercise 2.43: Louis Reasoner is having a terrible time doing Exercise 2.42 [post precedente]. His queens procedure seems to work, but it runs extremely slowly. (Louis never does manage to wait long enough for it to solve even the 6 × 6 case.) When Louis asks Eva Lu Ator for help, she points out that he has interchanged the order of the nested mappings in the `flatmap`, writing it as

``````(flatmap
(lambda (new-row)
(map (lambda (rest-of-queens)
new-row k rest-of-queens))
(queen-cols (- k 1))))
(enumerate-interval 1 board-size))``````

Explain why this interchange makes the program run slowly. Estimate how long it will take Louis’s program to solve the eight-queens puzzle, assuming that the program in Exercise 2.42 solves the puzzle in time `T`.

Questa soluzione fa troppe chiamate, come dice Bill the Lizard:

In the original solution, `queen-cols` is called once for each column in the board. This is an expensive procedure to call, since it generates the sequence of all possible ways to place `k` queens in `k` columns. By moving `queen-cols` so it gets called by `flatmap`, we’re transforming a linear recursive process to a tree-recursive process. The `flatmap` procedure is called for each row of the kth column, so the new procedure is generating all the possible solutions for the first `k - 1` columns for each one of these rows.

We learned back that a tree-recursive process grows exponentially. If it takes time `T` to execute the original version of queens for a given board size, we can expect the new version to take roughly `Tboard-size` time to execute.

Molto più concisa la spiegazione di sicp-ex.
Per contro dettagliata (e verbosa) l’esposizione di Drewiki.

Annunci