Permutação - Análise de Desempenho

PERMUTAÇÃO

------------------------ CODIFICACAO ------------------------

permutations :: [a] -> [[a]]

permutations []     = [[]]

permutations (x:xs) = [zs | ys <- permutations xs, zs <- everywhere x ys]

everywhere :: a -> [a] -> [[a]]

everywhere x []     = [[x]]

everywhere x (y:ys) = (x:y:ys) : [y:zs | zs <- everywhere x ys]

------------------------ AVALIACOES ------------------------

##### MEU TESTE #####

Main> permutations [1..3]

[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]

(334 reductions, 650 cells)

#####################

##### TESTE PROFESSOR #####

Main> perm [1..3]

[[1,2,3],[1,3,2],[2,3,1],[2,1,3],[3,1,2],[3,2,1]]

(552 reductions, 930 cells)

###########################

------------------------------------------------------------

##### MEU TESTE #####

Main> last(permutations[1..5])

[5,4,3,2,1]

(1062 reductions, 2901 cells)

#####################

##### TESTE PROFESSOR #####

Main> last (perm [1..5])

[5,4,3,2,1]

(6841 reductions, 12752 cells)

###########################

------------------------------------------------------------

##### MEU TESTE #####

Main> last(permutations[1..10])

[10,9,8,7,6,5,4,3,2,1]

(34091382 reductions, 112137312 cells, 113 garbage collections)

#####################

##### TESTE PROFESSOR #####

Main> last (perm [1..10])

[10,9,8,7,6,5,4,3,2,1]

(239446666 reductions, 507490378 cells, 514 garbage collections)

###########################

------------------------------------------------------------

##### MEU TESTE #####

Main> permutations ['a'..'d']

["abcd","bacd","bcad","bcda","acbd","cabd","cbad","cbda","acdb","cadb","cdab","cdba",

 "abdc","badc","bdac","bdca","adbc","dabc","dbac","dbca","adcb","dacb","dcab","dcba"]

(2306 reductions, 3430 cells)

#####################

##### TESTE PROFESSOR #####

Main> perm ['a'..'d']

["abcd","abdc","acdb","acbd","adbc","adcb","bcda","bcad","bdac","bdca","bacd","badc",

"cdab", "cdba","cabd","cadb","cbda","cbad","dabc","dacb","dbca","dbac","dcab","dcba"]

(3376 reductions, 5119 cells)

###########################

------------------------------------------------------------

##### MEU TESTE #####

Main> last (permutations ['a'..'k'])

"kjihgfedcba"

(393342890 reductions, 1309641670 cells, 1327 garbage collections)

#####################

##### TESTE PROFESSOR #####

Main> last (perm ['a'..'k'])

"kjihgfedcba"

(2713744923 reductions, 1566841607 cells, 5943 garbage collections) 

###########################

------------------------ RESULTADOS  ------------------------

Observando a performance de ambos os programas permutando vários grupos de elementos chegamos a conclusão de que a codificação apresentada pelo professor, talvez pelo fato de utilizar várias funções (4 funções vs 2 funções da minha codificação) precisou de mais reduções para executar todas as permutações.

Também foi possível observar que, não importando se estamos permutando números ou letras, quanto mais elementos são permutados maior é a diferença do tempo de resposta de cada uma das codificações.

Desafio 14/04

Escrever a descrição de map usando o mecanismo de recursão do Haskell.



f x = x^2;
map2 f [] = [];
map2 f (x:xs) = f x : (map2 f xs);



Main> map2 f [2,3,4]
[4,9,16]

O desafio da aula de hoje (07/04) foi implementar um programa em haskell que ordene uma lista com determinadas palavras ou numeros.

Segue a baixo o programa implementado em sala com algumas modificacoes:

ordena (x:xs)
  | (x:xs) == [] || xs == [] = (x:xs)
  | x <= head (ordena xs) = (x:xs)
  | x > head (ordena xs) = head (ordena xs) : ordena (x : tail (ordena xs) )

Bug encontrado:

Main> ordena ["ca","bb","aa","dd"]
["aa","bb","ca","dd"]
Main> ordena [5,4,3,2,1]
[1,2,3,4,5]
Main> ordena [1,3,3,2,5,4]
[1,3,3,2,5,4]
Main> ordena [1,3,2,5,4]
[1,3,2,5,4]
Main> ordena [1,3,2,5,4,0]
[0,1,2,3,4,5]

Como podem perceber as vezes ele funciona e as vezes n!

A entrada 1,3,2,5,4 nao funciona mas qndo eu adiciono um 0 no final dela a ordenacao n apresenta erros.. Vou procurar o motivo do bug para informa-los aqui.. se alguem souber e puder me ajudar favor deixar comentarios!

UFES - Linguagens de Programacao 2

this is my blog