Números feios - IV

Muito bem, sabemos que os números feios podem ser gerados diretamente, sem precisar usar o processo "gerar e testar", como acontece nos números primos.

qfeios = 1:[ x*y| x <- qfeios, y<-[2,3,5]]

e vejamos uma avaliação, acessando alguns feios:

>take 52 qfeios
[1,2,3,5,4,6,10,6,9,15,10,15,25,8,12,20,12,18,30,20,30,50,12,18,30,
18,27,45,30,45,75,20,30,50,30,45,75,50,75,125,16,24,40,24,36,60,40,
60,100,24,36,60]
(1584 reductions, 2636 cells)

Três aspectos desta lista merecem atenção:
a) ela é formada por sublista, cada uma associada com um dos fatores;
b) a lista possui elementos repetidos;
c) a lista está desordenada;

Os fatos b e c, inviabilizam a determinação do i-ésimo número feio. Entretanto o fato a no traz uma solução. Podemos gerar as três listas isoladamente.

m2 = [x*2| x <- feios]
m3 = [x*3| x <- feios]
m5 = [x*5| x <- feios]

e o truque final :

feios = 1: merge (merge m2 m3) m5

podemos agora, como em qualquer lista infinita, obter sublistas finitas.

> take 10 feios
[1,2,3,4,5,6,8,9,10,12]

> drop 90 (take 100 feios)
[1200,1215,1250,1280,1296,1350,1440,1458,1500,1536]

e agora voltemos a nossa questão inicial: Determinar o feio de ordem 1500.

> head (drop 1499(take 1500 feios))
859963392
(48017 reductions, 60032 cells)

bom, parece que esta descrição está um pouco difícil de entender. :-)

que tal essa:

> last(take 1500 feios)
859963392
(25534 reductions, 31551 cells)

mas essa parece melhor: o feio de ordem 1500 é o elemento de indíce 1499 na lista lfeios.

> feios!!1499
859963392
(28518 reductions, 36032 cells)

Nada impede que se tenha uma definição específica para determinar o feio de ordem k.


feio k = feios!!(k - 1)

e que assim possamos pedir a avaliação:

> feio 1500
859963392
(90641 reductions, 146337 cells)

Podemos voltar a falar sobre desempenho. Relembremos do que tinhamos antes usando "gerar e testar".

ordem	resultado	gerar e testar	geração direta
0	1	(283 reductions, 525 cells)	(40 reductions, 60 cells)
10	15	(5582 reductions, 8081 cells)	(498 reductions, 776 cells)
100	1.600	(662585 reductions, 962977 cells)	(5122 reductions, 7970 cells)
200	16.384	(6168873 reductions, 8984262 cells, 9 garbage collections)	(7724 reductions, 11584 cells)
500	944.784	(387151581 reductions, 568449819 cells, 577 garbage collections)	(21802 reductions, 3717 cells)
1.499	859 x 10 6		(71025 reductions, 111917 cells)
14.999	123 x 10 18		(285018 reductions, 372993 cells)
30.000	32 x 10 24		(1916481 reductions, 3385960 cells, 5 garbage collections)

A diferença entre o número de reduções e a quantidade de células utilizadas pelas duas versões do descrição da função nos fornece um bom entendimento da diferença no desempenho do Interpretador na avaliação das duas. Vejamos o caso do feio de ordem 500.

reduções : 387.151.581 versus 21.802, um ganho da ordem de 10 ⁴
células: 568.449.819 versus 3.717 um ganho da ordem de 10 ⁵
garbage: 577 versus 0