3

Gostaria de saber se alguém tem alguma sugestão para que eu possa otimizar o código abaixo.

A ideia eu retirei desse site. Você tem uma permutação de n cartas, por exemplo [2, 4, 1, 3] (onde o 2 é a carta que está no topo). Em cada rodada, a pessoa deve reverter as m primeiras cartas, onde m é a carta do topo. As rodadas são repetidas até que a permutação final seja [1, 2, 3, ..., n].

Exemplificando:

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

Utilizei a função perm da biblioteca Deducer para obter todas as permutações possíveis de um determinado vetor.

#retorna a quantidade de mudanças necessárias para obter o vetor de 1 até n
topswops <- function(x){ 
  i <- 0
  while(x[1] != 1){
    primeira <- x[1]
    if(primeira == length(x)){
       x <- rev(x)
    } else{
      x <- c(x[primeira:1], x[(primeira+1):length(x)])
    }
    i <- i + 1
  }
  return(i)
}

library(Deducer)

inicio <- Sys.time()
resultado <- NULL
for(i in 1:10){
  A <- perm(1:i)
  A <- data.frame(A)
  A$flips <- apply(A, 1, topswops)
  resultado <- rbind(resultado, c(i, max(A$flips)))
}
fim <- Sys.time()
fim - inicio

O tempo de processamento foi 3,74 minutos. Suspeito que a parte das permutações A <- perm(1:i) seja a que mais leva tempo, mas não consegui pensar em nenhuma outra forma.

1 Resposta 1

2

Pelo que analisei do teu código, a tua suspeita está correta: a função perm é o que está deixando o código lento. Eu cheguei a esta conclusão testando o tempo de execução da função topswops:

library(rbenchmark)
benchmark(topswops(sample(1:i, 10)), replications = 100000)
                       test replications elapsed relative user.self sys.self user.child sys.child
1 topswops(sample(1:i, 10))       100000   2.388        1     2.253    0.107          0         0

Repetir topswops cem mil vezes em vetores aleatórios de tamanho 10, com os elementos de 1 a 10, levou 2.388 segundos. Ou seja, o gargalo não é aqui.

Isto posto, procurei outras maneiras de gerar todas as permutações possíveis para uma sequência de números. Além do Deducer, os pacotes combinat e gtools também conseguem gerar todas as permutações de uma sequência de números. Os resultados do meu teste foram os seguintes:

library(Deducer)
inicio <- Sys.time()
resultado.Deducer <- NULL
for(i in 1:10){
  A <- perm(1:i)
  A <- data.frame(A)
  A$flips <- apply(A, 1, topswops)
  resultado.Deducer <- rbind(resultado.Deducer, c(i, max(A$flips)))
}
fim <- Sys.time()
fim - inicio
Time difference of 4.131159 mins

library(combinat)
inicio <- Sys.time()
resultado.combinat <- NULL
for(i in 1:10){
  A <- as.data.frame(matrix(unlist(permn(1:i)), ncol=i, byrow=TRUE))
  A$flips <- apply(A, 1, topswops)
  resultado.combinat <- rbind(resultado.combinat, c(i, max(A$flips)))
}
fim <- Sys.time()
fim - inicio
Time difference of 2.371664 mins

library(gtools)
inicio <- Sys.time()
resultado.gtools <- NULL
for(i in 1:10){
  A <- permutations(i, i, 1:i)
  A$flips <- apply(A, 1, topswops)
  resultado.gtools <- rbind(resultado.gtools, c(i, max(A$flips)))
}
Warning messages:
1: In A$flips <- apply(A, 1, topswops) : Coercing LHS to a list
2: In A$flips <- apply(A, 1, topswops) : Coercing LHS to a list
3: In A$flips <- apply(A, 1, topswops) : Coercing LHS to a list
4: In A$flips <- apply(A, 1, topswops) : Coercing LHS to a list
5: In A$flips <- apply(A, 1, topswops) : Coercing LHS to a list
6: In A$flips <- apply(A, 1, topswops) : Coercing LHS to a list
7: In A$flips <- apply(A, 1, topswops) : Coercing LHS to a list
8: In A$flips <- apply(A, 1, topswops) : Coercing LHS to a list
9: In A$flips <- apply(A, 1, topswops) : Coercing LHS to a list
10: In A$flips <- apply(A, 1, topswops) : Coercing LHS to a list
fim <- Sys.time()
fim - inicio
Time difference of 1.849558 mins

Portanto, uma maneira de otimizar o código é, justamente, melhorando a geração das permutações. Nos meu teste, a função que melhor se saiu foi gtools::permutations, levando 1.849558 minutos para rodar. Isto equivale a 44% do tempo utilizado pela função original.

Talvez seja possível melhorar ainda mais este desempenho otimizando a geração das permutações. Como são milhões de replicações, acredito que qualquer melhora na geração das permutações seja algo que conte muito no final.

Se a procura é pelo menor tempo de execução e não necessariamente o melhor algoritmo, também é possível diminuir o tempo de execução paralelizando o código. Mas aí eu deixo este exercício para o leitor : )

1
  • A ideia de paralelização é boa, mas como foi um código de brincadeira, nem vou me preocupar tanto com isso. Consegui achar um outro pacote que reduziu o tempo de execução para 1,58 minutos - iterpc. Rodei novamente meu código inicial e, o tempo gasto foi 3,25 minutos. Então, o ganho, foi mais de 50%. 14/09/2018 às 20:06

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .