Python - confronto degli elementi della lista con elementi "vicini"

Question

Questo può essere più di un "approccio" o una domanda concettuale.

Fondamentalmente, ho un pitone un elenco multidimensionale modo:

my_list = [[0,1,1,1,0,1], [1,1,1,0,0,1], [1,1,0,0,0,1], [1,1,1,1,1,1]] 

Quello che devo fare è scorrere la matrice e confronta ciascun elemento con quelli direttamente circondano come se la lista era Layed fuori come una matrice.

Ad esempio, dato il primo elemento della prima fila, my_list[0][0], devo sapere conosce il valore my_list[0][1], my_list[1][0] e my_list[1][1]. Il valore degli elementi "circostanti" determinerà come deve essere utilizzato l'elemento corrente. Ovviamente per un elemento nel cuore dell'array, saranno necessari 8 confronti.

Ora so che potrei semplicemente scorrere l'array e confrontarlo con i valori indicizzati, come sopra. Ero curioso di sapere se esistesse un modo più efficiente che limitasse la quantità di iterazione richiesta? Devo scorrere l'array così com'è o iterare e confrontare solo i valori su entrambi i lati, quindi trasporre l'array ed eseguirlo di nuovo. Questo, tuttavia, ignorerebbe quei valori nella diagonale. E dovrei memorizzare i risultati delle ricerche degli elementi, quindi non continuo a determinare il valore dello stesso elemento più volte?

Sospetto che questo possa avere un approccio fondamentale in Informatica e sono desideroso di ottenere un feedback sull'approccio migliore usando Python anziché cercare una risposta specifica al mio problema.

Qualsiasi aiuto molto apprezzato.

Answer 1

È possibile ottenere codice più veloce, e possibilmente ancora più semplice, utilizzando numpy o altre alternative (vedere sotto per i dettagli). Ma da un punto di vista teorico, in termini di complessità algoritmica, il meglio che puoi ottenere è O (N * M), e puoi farlo con il tuo disegno (se ho capito bene). Per esempio:

def neighbors(matrix, row, col): 
    for i in row-1, row, row+1: 
     if i < 0 or i == len(matrix): continue 
     for j in col-1, col, col+1: 
      if j < 0 or j == len(matrix[i]): continue 
      if i == row and j == col: continue 
      yield matrix[i][j] 

matrix = [[0,1,1,1,0,1], [1,1,1,0,0,1], [1,1,0,0,0,1], [1,1,1,1,1,1]] 

for i, row in enumerate(matrix): 
    for j, cell in enumerate(cell): 
     for neighbor in neighbors(matrix, i, j): 
      do_stuff(cell, neighbor) 

Questo ha prende N * M * 8 passi (in realtà, un po 'meno di quello, perché molte cellule avranno meno di 8 vicini di casa). E algoritmicamente, non c'è modo di fare meglio di O (N * M). Quindi, hai finito.

---

(In alcuni casi, è possibile rendere le cose più semplici, con nessun cambiamento significativo in entrambi i casi in termini di prestazioni, pensando in termini di trasformazioni iteratore. Ad esempio, è possibile creare facilmente una cernia su terzine adiacenti da una lista a zippando correttamente a, a[1:] e a[2:], ed è possibile estenderlo ai nonet bidimensionali adiacenti.Ma penso che in questo caso, renderebbe più complicato il codice che scrivendo un iteratore esplicito neighbors e cicli espliciti for sopra matrice)

---

Tuttavia, praticamente, è possibile ottenere molto più velocemente, in vari modi. Ad esempio:

• Utilizzando numpy, è possibile ottenere un ordine di grandezza o così più veloce. Quando stai ripetendo un ciclo stretto e eseguendo semplici operazioni aritmetiche, è una delle cose a cui Python è particolarmente lento, e numpy può farlo in C (o Fortran).
• Utilizzando la libreria GPGPU preferita, è possibile vettorizzare esplicitamente le operazioni.
• Utilizzando multiprocessing, è possibile suddividere la matrice in pezzi ed eseguire più pezzi in parallelo su core separati (o anche su macchine separate).

Naturalmente per un'unica matrice 4x6, nessuno di questi sono la pena di fare ... tranne forse per numpy, che può rendere il codice più semplice come pure più veloce, fino a quando si può esprimere le vostre operazioni naturalmente nella matrice/broadcast termini.

In realtà, anche se non si può esprimere facilmente le cose in questo modo, usando solo numpy-negozio la matrice può rendere le cose un po 'più semplice (e risparmiare un po' di memoria, se quello che conta). Ad esempio, numpy può consentire l'accesso a una singola colonna da una matrice in modo naturale, mentre in Python puro, è necessario scrivere qualcosa come [row[col] for row in matrix].

---

Quindi, come si affronterà questo con numpy?

In primo luogo, si dovrebbe leggere oltre numpy.matrix e ufunc (o, meglio, un po 'di esercitazione di livello superiore, ma io non ho uno a raccomandare) prima di andare troppo oltre.

In ogni caso, dipende da cosa si sta facendo con ogni gruppo di vicini, ma ci sono tre idee di base.

Innanzitutto, se è possibile convertire l'operazione in matematica a matrice semplice, è sempre più semplice.

In caso contrario, è possibile creare 8 "matrici adiacenti" semplicemente spostando la matrice in ogni direzione, quindi eseguire semplici operazioni contro ciascun vicino. Per alcuni casi, potrebbe essere più facile iniziare con una matrice N + 2 x N + 2 con valori "vuoti" adatti (solitamente 0 o nan) nel bordo esterno. In alternativa, puoi spostare la matrice sopra e riempire i valori vuoti. Oppure, per alcune operazioni, non hai bisogno di una matrice di dimensioni identiche, quindi puoi semplicemente ritagliare la matrice per creare un vicino. Dipende davvero dalle operazioni che vuoi fare.

Ad esempio, prendendo l'input come una tavola 6x4 fissato per l'Game of Life:

def neighbors(matrix): 
    for i in -1, 0, 1: 
     for j in -1, 0, 1: 
      if i == 0 and j == 0: continue 
      yield np.roll(np.roll(matrix, i, 0), j, 1) 

matrix = np.matrix([[0,0,0,0,0,0,0,0], 
        [0,0,1,1,1,0,1,0], 
        [0,1,1,1,0,0,1,0], 
        [0,1,1,0,0,0,1,0], 
        [0,1,1,1,1,1,1,0], 
        [0,0,0,0,0,0,0,0]]) 
while True: 
    livecount = sum(neighbors(matrix)) 
    matrix = (matrix & (livecount==2)) | (livecount==3) 

(Si noti che questo non è il modo migliore per risolvere questo problema, ma penso che sia relativamente facile da capire, e probabilmente per illuminare qualunque sia il tuo problema reale.)