3x3 Fonction déterminante de la matrice - la rendre plus rapide

Question

J'écris un programme plus grand et il est très important que les déterminants des matrices 3x3 soient aussi rapides que possible pour que cela fonctionne bien. J'ai lu que je pourrais utiliser numPy pour le faire, mais je pensais que peut-être écrire mon propre code serait plus instructif que je suis dans mon 3ème semestre de CompSci.

J'ai donc écrit deux fonctions et j'utilise time.clock() (je suis sur une machine win7) pour calculer le temps nécessaire pour que chaque fonction renvoie une valeur.

Ceci est la première fonction:

def dete(a): 
    x = (a[0][0] * a[1][1] * a[2][2]) + (a[1][0] * a[2][1] * a[3][2]) + (a[2][0] * a[3][1] * a[4][2]) 
    y = (a[0][2] * a[1][1] * a[2][0]) + (a[1][2] * a[2][1] * a[3][0]) + (a[2][2] * a[3][1] * a[4][0]) 
    return x - y 

Et ceci est la deuxième fonction:

def det(a): 
    a.append(a[0]); a.append(a[1]); 
    x = 0 
    for i in range(0, len(a)-2): 
     y=1;   
     for j in range(0, len(a)-2):  
      y *= a[i+j][j]  
     x += y 

    p = 0 
    for i in range(0, len(a)-2): 
     y=1; 
     z = 0; 
     for j in range(2, -1, -1): 
      y *= a[i+z][j] 
      z+=1   
     z += 1 
     p += y 
    return x - p 

Ils donnent tous deux les bonnes réponses, mais le premier semble être un peu plus rapide, ce qui rend Je pense que puisque les boucles sont plus élégantes à utiliser et généralement plus rapides, je fais quelque chose de mal - j'ai fait les boucles trop lentes et trop grosses. J'ai essayé de le réduire, mais il semble que les opérations * = et + = prennent trop de temps, il y en a trop. Je n'ai pas encore vérifié à quelle vitesse numPy s'occupe de ce problème, mais je veux devenir meilleur en écrivant du code efficace. Des idées pour rendre ces boucles plus rapides?

Answer 1

Les boucles sont - plus élégantes et plus génériques, mais elles ne sont pas "généralement plus rapides" que quelques multiplications en ligne dans une seule expression. Pour une personne, une boucle for en python doit assembler l'objet sur lequel vous allez interagir (l'appel à range), puis appeler une méthode sur cet itérateur pour chaque élément de la boucle. Donc, selon ce que vous faites, si la forme en ligne est assez rapide pour que vous la conserviez - si elle est encore trop lente (comme c'est le cas habituellement quand nous faisons un calcul numérique en Python), vous devriez utiliser une bibliothèque numérique (exemple numérique NumpY), qui peut calculer des déterminants en code natif. Dans le cas d'un code de manipulation numérique comme celui-ci, vous pouvez le faire fonctionner des centaines de fois plus vite en utilisant du code natif. Si vous avez besoin d'un calcul numérique qui ne peut pas être effectué par une bibliothèque déjà créée, si vous recherchez la vitesse (par exemple, pour la manipulation de pixels dans le traitement d'image), vous pouvez écrire une extension en code natif (en utilisant soit C, Cython, ou quelque chose d'autre) afin de l'avoir rapidement. D'autre part, si la vitesse n'est pas cruciale, et vous avez même noté que l'expression inline est juste "légèrement plus rapide", utilisez simplement la boucle complète - vous obtenez un code plus lisible et maintenable - qui sont les principales raisons d'utiliser Python après tout.

Sur l'exemple précis que vous avez donné, vous pouvez obtenir une augmentation de la vitesse dans le code de la boucle par hardcoding la « plage » appelle à tuples - par exemple, le changement: for i in range(0, len(a)-2):-for i in (0, 1, 2) - noter que, comme dans le cas en ligne, vous perdre la capacité de travailler avec des matrices de tailles différentes.

Answer 2

vous pouvez dérouler les boucles et profiter du fait que vous manipulez des matrices 3x3 et non des matrices nxn.

Avec cette optimisation, vous vous débarrassez de la détermination de la taille de la matrice. Vous échangez de la flexibilité avec un peu de vitesse. Vous pouvez simplement écrire les formules concrètes pour chaque cellule de la matrice de résultat. BTW: (C++) Les compilateurs font de telles choses d'optimisation.

Je vous suggérerais seulement de le faire, si vous êtes vraiment sûr qu'une telle petite optimisation vaut le code spécialisé. Pour vous assurer que vous optimisez la partie droite de votre code, utilisez par exemple les outils de profilage voir http://docs.python.org/library/profile.html ou durée.

Answer 3

D'abord permettez-moi de noter, que l'optimisation de la vitesse micro échelle devrait avoir lieu dans une autre langue. Il vaut donc mieux utiliser une bibliothèque qui utilise des fonctionnalités c-écrites. A propos de vos boucles for: Il est courant de dérouler de (petites) boucles pour accélérer, il n'est donc pas toujours plus rapide de laisser les boucles faire le travail. Habituellement, il est juste plus générique (et la plupart des algorithmes génériques sont en fait plus lents que les algorithmes spécialisés). Comme indiqué dans les commentaires, il n'augmentera pas la vitesse en python, en remplaçant - par * mais cela pourrait augmenter la vitesse si les opérations arithmétiques sont moins nombreuses. Par conséquent, je vais poster le terme refactorisée ici:

def dete(a): 
    return (a[0][0] * (a[1][1] * a[2][2] - a[2][1] * a[1][2]) 
      -a[1][0] * (a[0][1] * a[2][2] - a[2][1] * a[0][2]) 
      +a[2][0] * (a[0][1] * a[1][2] - a[1][1] * a[0][2])) 

Comme vous pouvez le voir, il y a 5 +/- et 9 * où, comme dans la version originale, il y a 5 +/- et 12 *. Notez également que cette version accède à a seulement 15 fois où l'original y a accédé 18 fois.

En résumé, ceci donne 3 opérations arithmétiques et 3 accès variables inférieures à la version entièrement multipliée.

Answer 4

Pendant que vous déroulage, comme proposé ci-dessus, vous pouvez également combiner les deux blocs en un seul, comme un rapide coup d'œil trouvé aucune dépendance entre les deux blocs (corrigez-moi si je me trompe)

Answer 5

Il est il est presque impossible que les boucles soient plus rapides que les expressions longues et explicites, donc pas étonnant que la première variante soit plus rapide. Je doute que vous puissiez trouver smt plus rapidement que la première fonction.