Produto externo em Python

De tempos a tempos aparece um problema onde dá jeito usar um pouco de força bruta para o resolver.

Desta vez o problema foi ter um conjunto de pontos aleatórios, onde precisava de verificar se os vectores formados por eles faziam um ângulo de 90º entre si.

A forma mais rápida que eu encontrei para o fazer, foi testar todas as combinações de pontos. Funciona, mas consome muito CPU!!... por isso procurei perceber se em Python existia alguma forma de poupar-me de fazer vários loops...

Neste post vou testar as soluções de produto externo em Python que encontrei.

Problema: Tendo a lista X, calcular o produto externo.

 sample_list = range(100)     #[0,1,2,3,4,5,6,7,8, ... 99 ]  

A primeira solução:  Looooooops

 for i in sample_list:  
      for j in sample_list:  
           for k in sample_list:  
                print i, j, k  

A segunda solução: itertools

 import itertools  
 product = itertools.product( samples, samples, samples )  
 for i, j, k in product:  
      print i, j, k  

Qual destas soluções é mais rápida? 

Depois de tirar uma amostragem de 100 execuções da duração destas soluções obtive os seguintes resultados:

Média do tempo de processamento da primeira solução:  2.19596658707 segundos.
Média do tempo de processamento da segunda solução:  2.19485656738 segundos.

Código usado no teste

 import time  
 import itertools  
 from numpy import *  
 N_SAMPLES = 50  
 N_TRIALS = 100  
 samples = range(N_SAMPLES)  
 processing_times = [[],[]]  
 for trial in range(N_TRIALS):  
      time.sleep(1)  
      start_time = time.time()  
      for i in samples:  
           for j in samples:  
                for k in samples:  
                     print i, j, k  
      processed_time = time.time() - start_time  
      processing_times[0].append(processed_time)  
      time.sleep(1)  
      start_time = time.time()  
      product = itertools.product( samples, samples, samples )  
      for i, j, k in product:  
           print i, j, k  
      processed_time = time.time() - start_time  
      processing_times[1].append(processed_time)  
 first_mean = mean( array(processing_times[0]) )  
 second_mean = mean( array(processing_times[1]) )  
 print "First method - running time average: ", first_mean  
 print "Second method - running time average: ", second_mean  
 import matplotlib.pyplot as plt  
 trials = range(N_TRIALS)  
 plt.plot(processing_times[0], label='First solution', color='b')  
 plt.plot( processing_times[1], color='r', label='Second solution')  
 plt.xlabel('Trial')  
 plt.ylabel('Processing time')  
 plt.title('Results')  
 plt.legend()  
 plt.show()