CONS e APPEND

Esses tempos postei uma rotina no forum autolisp que iterava uma lista de elemetos e retornava todas as combinações 2 a 2 possíveis nesta lista, sem repetir e não importando a ordem dos elementos, bom, ela funciona tranquilamente, mas se alguem já testou para um grande número de elementos, notou que ele é um tanto LENTA DEMAIS...

Mas por que será? a rotina é pequena, não faz rodeios... em fim... essa semana estive fazendo uns testes com as funções CONS e APPEND do autolisp, pra ver qual retornava resultados mais rápidos... fiz testes tambem entre o FOREACH e o REPEAT

Destes dois últimos, concluí que o FOREACH tem uma pequena vantagem, quase que imperceptível, mas isso deve ser porque para usar o REPEAT, preciso incrementar um índice manualmente... Bom, o caso mesmo é entre o CONS e o APPEND (ou a forma como escrevi os programas... não sei)

Os programas testados são estes:
clique para ver...
;devolve uma lista interada de uma função no estilo todos-contra-todos sem repetir combinações 
(defun todos-contra-todos (lst fun l c q r
  (
setq 
       
(length lst)) 
  (
repeat (1- q
    (
setq (1+ l)) 
    (
repeat (q c
      (
setq (append (list (fun (nth l lst) (nth c lst)))) 
           
(1+ c))) 
    (
setq (1+ l))) 
  
r

(
defun todos-contra-todos2 (lst fun a b lst3
  (
foreach a lst 
    
(foreach (setq lst (cdr lst)) 
      (
setq lst3 (append lst3 (list (fun a b)))))) 
  
lst3

(
defun todos-contra-todos3 (lst fun a b lst3
  (
foreach a lst 
    
(foreach (setq lst (cdr lst)) 
      (
setq lst3 (cons (fun a blst3)))) 
  (
reverse lst3)) 

;rotina para criar uma lista temporaria: 
(defun expandlist (el qtd lst
  (
repeat qtd (setq lst (cons el lst)))) 

;rotina para calcular o tempo de execução: 
(defun testtime (fun t1 t2
  (
setq t1  (getvar "date"
        
t1  (86400.0 (t1 (fix t1)))) 
  (
eval fun
  (
setq t2  (getvar "date"
        
t2  (86400.0 (t2 (fix t2)))) 
  (
t2 t1)) 


;|********************************TESTES***************************** 
;testem as opções: 
(todos-contra-todos3 '(1 2 3 4 5) (lambda (a b) (list a b))) 
   -> ((1 2) (1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 4) (3 5) (4 5)) 

(todos-contra-todos2 '(1 2 3 4 5) (lambda (a b) (list a b))) 
   -> ((1 2) (1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 4) (3 5) (4 5)) 

(todos-contra-todos '(1 2 3 4 5) (lambda (a b) (list a b))) 
   -> ((1 2) (1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 4) (3 5) (4 5)) 
;todas retornam o mesmo valor... o que é de se esperar 

;criar uma lista com 100 elementos: 
(setq aa (expandlist nil 100)) 

;AVALIAR O TEMPO DE EXECUÇÃO DE CADA UMA DAS SUBROTINAS: 
(testtime '(todos-contra-todos  aa (lambda (a b) nil))) ;2.60996 
(testtime '(todos-contra-todos2 aa (lambda (a b) nil))) ;2.57798 
(testtime '(todos-contra-todos3 aa (lambda (a b) nil))) ;0.0149667 !!!! 
;|

como podem ver nos programas e nos testes, o programa "todos-contra-todos3" obteve um tempo cerca de 200 vezes melhor!!! e detalhe: a lista precessada tinha apenas 100 elementos....

teste com uma lista de 500 elementos, "todos-contra-todos3" obteve um tempo de resposta de 1.07 segundos, já os outros.... ainda estão processando!!!

donde concluo que, usar o CONS é preferível ao APPEND, pois demora menos...
deve ser por que o append avalia a lista TODA ANTES, procura o seu final e aí acrescenta uma nova lista no fim... sei lá....

façam o teste, copiem a rotina e testem... o rogério ( do forum autolisp ) já fez o teste e chegou em valores próximos aos meus...

Nenhum comentário:

Postar um comentário