Cómo acelerar el bucle de pitón

Question

tuve un vistazo a varias dicussions en varios sitios y ninguno de ellos me dio una solución. Esta pieza de código tarda más de 5 segundos para ejecutar:

for i in xrange(100000000): 
    pass 

Estoy trabajando en un problema de optimización número entero y tengo que utilizar un O (n log n) algoritmo edición: un O (n²/4) algoritmo, donde n representa todos los elementos de la matriz, es decir, en el siguiente código, n * m = 10000. Por lo tanto, para una matriz 100 * 100 con 10000 elementos, dará como resultado casi 25000000 iteraciones.. Su código se puede resumir así:

m = 100 
n = 100 
for i in xrange(m): 
    for j in xrange(n): 
    for i2 in xrange(i + 1, m): 
     for j2 in xrange(j + 1, n): 
     if myarray[i][j] == myarray[i2][j2] and myarray[i2][j] == myarray[i][j2]: 
      return [i, j], [i2, j2] 

¿Debo renunciar con Python y volver a Java o en C?

Trabajo con Python 2.7 y Psyco no está disponible. PyPy no admite Tkinter de forma inmediata y estoy usando Tkinter.

Entonces, ¿mejorarían la velocidad de bucle? ¿Hay otras soluciones?

Answer 1

sentimos que decirle, pero no es una cuestión de optimización. No importa qué idioma o implementación elijas, este algoritmo no es O(n*log n) en el peor caso y en el promedio. Es posible que desee leer en how the Big-O notation works y desarrollar un mejor algoritmo.

Answer 2

Aún puede utilizar la notación python y tener la velocidad de C, utilizando el proyecto Cython. Un primer paso sería convertir el bucle en el bucle C: se hace automáticamente si escribe todas las variables utilizadas en el bucle:

cdef int m = 100 
cdef int n = 100 
cdef int i, j, i2, j2 
for i in xrange(m): 
    for j in xrange(n): 
    for i2 in xrange(i + 1, m): 
     for j2 in xrange(j + 1, n): 

para la siguiente parte, sería aún mejor si eso myarray sería pura C array, luego no hay comparación de python ni acceso a matriz. Con su gama de pitón, puede quitar a los ricos comparaison haciendo comparaison nativo (si tiene doble en su conjunto):

 cdef double a, b, c, d 
     a = myarray[i][j] 
     b = myarray[i2][j2] 
     c = myarray[i2][j] 
     d = myarray[i][j2] 

     if a == b and c == d: 
      return [i, j], [i2, j2] 

Se puede ver cómo la optimización van ejecutando cython -a yourfile.pyx, a continuación, abra la yourfile.html generan. Verás cómo Cython ha optimizado tu código y eliminado la sobrecarga de Python.

Answer 3

No es el estilo de codificación más bonito, pero los tiempos desesperados requieren una codificación desesperada. Intente convertir sus bucles anidados anidados en una gran expresión de generador:

try: 
    i,j,i2,j2 = ((i,j,i2,j2) 
     for i in xrange(m) 
      for j in xrange(n) 
      for i2 in xrange(i + 1, m) 
       for j2 in xrange(j + 1, n) 
       if myarray[i][j] == myarray[i2][j2] and 
        myarray[i2][j] == myarray[i][j2]).next() 
    return [i,j],[i2,j2] 
except StopIteration: 
    return None 

Answer 4

Lo sentimos, el generador expr no funcionó. Aquí es un esquema diferente que la primera coincide todos los valores como, y luego mira a los grupos rectangulares:

from collections import defaultdict 
from itertools import permutations 
def f3(myarray): 
    tally = defaultdict(list) 
    for i,row in enumerate(myarray): 
     for j,n in enumerate(row): 
      tally[n].append((i,j)) 

    # look for rectangular quads in each list 
    for k,v in tally.items(): 
     for quad in permutations(v,4): 
      # sort quad so that we can get rectangle corners 
      quad = sorted(quad) 
      (i1,j1),(i2,j2) = quad[0], quad[-1] 

      # slice out opposite corners to see if we have a rectangle 
      others = quad[1:3] 

      if [(i1,j2),(i2,j1)] == others: 
       return [i1,j1],[i2,j2] 

Answer 5

miré varias veces a través de su código y si me sale bien, el marcar sus rectángulos con dos angulares marcadores diferentes . Lo siento si mi respuesta es más un comentario para aclarar tu posición y luego una respuesta real.

Parte de la respuesta:: Si está buscando un algoritmo apropiado, considere un algoritmo de línea de exploración. Encontré un ejemplo here @SO para una "solución rectangular más grande".

Mi pregunta para usted es, ¿qué es lo que realmente está buscando?

1. mejor manera de resolver el bucle for dilema
2. mejor lenguaje para su algoritmo de
3. un algoritmo más rápido para encontrar rectángulos

debo también señalar, que Pablo y sus productos solución resultados diferentes, porque Pauls asume que las esquinas están marcadas por los mismos valores y usted asume que las esquinas están marcadas a través de dos valores diferentes.

I se tomó el tiempo y la libertad para ilustrar con un c & guión p feo: Se compara tanto algoritmo mediante la creación de un campo de 2D y la llena de caracteres string.lowercase y gira las esquinas a mayúsculas-chars.

from random import choice 
from string import lowercase 
from collections import defaultdict 
from itertools import permutations 
from copy import deepcopy 

m,n = 20, 20 
myarray = [[choice(lowercase) for x in xrange(m)] for y in xrange(n)] 

def markcorners(i,j,i2,j2): 
    myarray[i][j] = myarray[i][j].upper() 
    myarray[i2][j] = myarray[i2][j].upper() 
    myarray[i2][j2] = myarray[i2][j2].upper() 
    myarray[i][j2] = myarray[i][j2].upper() 

def printrect(): 
    for row in myarray: 
     print ''.join(row) 
    print '*'*m 

def paul_algo(): 
    tally = defaultdict(list) 
    for i,row in enumerate(myarray): 
     for j,n in enumerate(row): 
      tally[n].append((i,j)) 

    # look for rectangular quads in each list 
    for k,v in tally.items(): 
     for quad in permutations(v,4): 
      # sort quad so that we can get rectangle corners 
      quad = sorted(quad) 
      (i1,j1),(i2,j2) = quad[0], quad[-1] 

      # slice out opposite corners to see if we have a rectangle 
      others = quad[1:3] 

      if [(i1,j2),(i2,j1)] == others: 
       markcorners(i1,j1,i2,j2) 

def xavier_algo(): 
    for i in xrange(m): 
     for j in xrange(n): 
      for i2 in xrange(i + 1, m): 
       for j2 in xrange(j + 1, n): 
        if myarray[i][j] == myarray[i2][j2] and myarray[i2][j] == myarray[i][j2]: 
         markcorners(i,j,i2,j2) 

savearray = deepcopy(myarray) 
printrect() 

xavier_algo() 
printrect() 

myarray = deepcopy(savearray) 
paul_algo() 
printrect()