Come velocizzare il loop python

Question

Ho dato un'occhiata a diverse dicussioni su diversi siti e nessuno di loro mi ha dato una soluzione. Questo pezzo di codice richiede più di 5 secondi per eseguire:

for i in xrange(100000000): 
    pass 

sto lavorando su un problema di ottimizzazione intero e devo usare un O (n log n) algoritmo edit: un O (n²/4) algoritmo, dove n sta per tutti gli elementi della matrice, cioè, nel seguente codice, n * m = 10000. Quindi, per una matrice 100 * 100 con 10000 elementi, il risultato sarà quasi 25000000 iterazioni.. Il suo codice può essere riassunta in questo modo:

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] 

Devo rinunciare con Python e tornare a Java o C?

Io lavoro con Python 2.7 e Psyco non è disponibile. PyPy non supporta Tkinter out of the box e sto usando Tkinter.

Quindi, migliorerebbero la velocità di loop? Ci sono altre soluzioni?

Answer 1

Mi dispiace dirtelo, ma non si tratta di ottimizzazione. Indipendentemente dalla lingua o dall'implementazione scelta, questo algoritmo non è O(n*log n) nel caso peggiore e medio. Si consiglia di leggere su how the Big-O notation works e sviluppare un algoritmo migliore.

Answer 2

È ancora possibile utilizzare la notazione Python e avere la velocità di C, utilizzando il progetto Cython. Un primo passo sarebbe quello di convertire il ciclo in ciclo C: è fatta automaticamente digitando tutte le variabili utilizzate nel ciclo:

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): 

Per La parte successiva, sarebbe ancora meglio se che myarray sarebbe pura Array C, quindi nessun comparaison ricco in Python né accesso ad array. Con l'array di pitone, è possibile rimuovere la ricca comparaison facendo comparaison nativo (se avete letto nella propria matrice):

 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] 

Si può vedere come l'ottimizzazione stanno eseguendo cython -a yourfile.pyx, quindi aprire il yourfile.html generare. Vedrai come Cython ha ottimizzato il tuo codice e rimosso il sovraccarico di Python.

Answer 3

Non è lo stile di codifica più grazioso, ma i tempi disperati richiedono una codifica disperata. Provare a girare i vostri cicli annidati annidati in un unico grande generatore di espressione:

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

dispiace l'espr generatore non ha funzionato. Ecco uno schema diverso che prima collima tutti i valori come, e poi cerca i gruppi rettangolari:

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

ho guardato più volte attraverso il vostro codice e se ho capito bene, la vostra marcatura vostri rettangoli con due diversi angoli marcatori . Mi dispiace se la mia risposta è più un commento per chiarire la tua posizione quindi una risposta davvero.

Answer-Part:: Se si sta cercando un algoritmo appropriato, prendere in considerazione un algoritmo della linea di scansione. Ho trovato un esempio here @SO per una "soluzione rettangolo più grande".

La mia domanda per te è, cosa stai veramente cercando?

1. modo migliore per risolvere il ciclo for dilemma
2. migliore lingua per il vostro algoritmo
3. un algoritmo più veloce per trovare i rettangoli

Devo anche sottolineare, che Paolo e il vostro prodotto soluzione risultati diversi, perché Pauls presuppone che gli angoli siano contrassegnati da stessi valori e si assume che gli angoli siano contrassegnati da due valori diversi!

ho preso il tempo e la libertà di illustrare con un c & sceneggiatura brutta p: Esso mette a confronto sia algoritmo creando un 2D-campo e la riempie di caratteri string.lowercase e si rivolge agli angoli in maiuscolo-caratteri.

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()