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)
          (adjoin-position 
           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.

:mrgreen:

Annunci
Post a comment or leave a trackback: Trackback URL.

Trackbacks

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: