Calculando determinante de uma matriz pelo Teorema de Laplace - Parte III

Nos posts anteriores, implementamos o teorema de Laplace para calcular o determinante de uma matriz quadrada. Na Parte I construímos a função recursiva e, na Parte II, a função iterativa. Neste post, vamos comparar a eficiência das duas funções que criamos e com a função det embutida no R.

Para isso, vamos utilizar o pacote rbenchmark. Vamos testar nossas funções com uma matriz de ordem 5:

set.seed(7)
M = matrix(sample(1:100,size = 25,replace = F),ncol=5,byrow = T)

> M
     [,1] [,2] [,3] [,4] [,5]
[1,]   42   83   31   92   66
[2,]   15   90    8   67   88
[3,]   40   22   47   93   59
[4,]   12   51   20   94   98
[5,]   79    6   16   89   86

Vamos utilizar a função benchmark e fazer 1000 replicações. Vejamos:

> benchmark(det(M),calc_det(M),calc_det_laplace(M),replications = 1000,
+           columns = c("test", "replications", "elapsed","relative"))
                 test replications elapsed relative
2         calc_det(M)         1000    0.19    6.333
3 calc_det_laplace(M)         1000    0.25    8.333
1              det(M)         1000    0.03    1.000

Veja que a função det é muito mais eficiente que as nossas, o que era esperado, pois as funções do R já são otimizadas.

Agora perceba algo interessante: a função recursiva foi executada mais rápida que a iterativa. Isso ocorreu, provavelmente, pelo fato de construirmos e armazenamos a árvore de matrizes. Se fizermos a conta, o tempo de execução da função iterativa é 1,32 vezes o tempo da função recursiva.

Quanto maior a dimensão da matriz, mais custoso será para calcularmos seu determinante e será mais pesado para nossas funções. Por exemplo, considere a matriz de ordem 10 abaixo:

set.seed(7)
M = matrix(sample(1:100,size = 100,replace = F),ncol=10,byrow = T)

> M
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
 [1,]   42   83   31   92   66   15   90    8   67    88
 [2,]   40   22   47   93   59   12   51   20   94    98
 [3,]   79    6   16   89   86   21    4   11   26     2
 [4,]   38   43   36    3   53   41   96   77   87    45
 [5,]   91   65   81   34   32   85   75   62   24    10
 [6,]   46   82   48   23    5   56   70   97   76    78
 [7,]   64   28  100   18   29   84   30   63   55    80
 [8,]   74   44   17   73   13   61   60   52   37     1
 [9,]   39   54   25   27   68   71    9   35   19    49
[10,]   14   72   58   57   99   69    7   33   95    50

Para essa matriz, temos os seguintes tempos de execução:

> t1 = Sys.time()
> det(M)
[1] 1.197026e+18
> t2 = Sys.time()
> calc_det_laplace(M)
[1] 1.197026e+18
> t3 = Sys.time()
> calc_det(M)
[1] 1.197026e+18
> t4 = Sys.time()

> t2-t1
Time difference of 0.002995014 secs
> t3-t2
Time difference of 10.98335 secs
> t4-t3
Time difference of 6.374352 secs

Perceba que todas as funções apresentaram o mesmo resultado, como era de se esperar. Mas observe o tempo de execução. A função det não chegou a 0,1 segundo de execução, ao passo que nossas funções apresentam tempos bem maiores.

Isso nos mostra que é preferível utilizar as funções já otimizadas do R ao invés de implementá-las. É claro, nossa estratégia de pegar sempre a primeira linha da matriz é ingênua e o código não está otimizado, mas é fato que vale a pena implementar esse tipo de função se for melhor do que o R já disponibiliza.

O intuito com o exercício dessa série foi praticar a programação e utilizamos vários conceitos para isso. Logo, nossa missão foi cumprida.

Espero que tenha gostado da aula.

Até a próxima aula!