RecursionError on 1000x1000 matrix of the same element. Python

Question

RecursionError on 1000x1000 matrix of the same element. Python

Navigation

#1 by (2 votes)
#2 by (1 votes)

1

Good, I have a doubt, I'm doing unittest for a function that I have and the problem is that when generating a 40x40 matrix, 50x50 of the same element (for example 'A') onwards generates a recursion error, while that with a function of 1000x1000 random of A..Z does not generate any error to me.

The code is as follows.

Adjacent calculation function:

def calcular(matriz):
    matriz = [list(row) for row in matriz]
    m = len(matriz)  # filas
    n = len(matriz[0])  # columnas
    d = {}  # diccionario de manchas

    def busqueda(f, c, value, id):
        vecinos = ((i, j) for i, j in ((f - 1, c), (f, c - 1), (f, c + 1), (f + 1, c))
                   if i >= 0 and i < m and j >= 0 and j < n and matriz[i][j] == value)
        for i, j in vecinos:
            d[id].append((value, i, j))
            matriz[i][j] = False
            busqueda(i, j, value, id)
    for i in range(m):
        for j in range(n):
            if matriz[i][j]:
                id = matriz[i][j], i, j
                d[matriz[i][j], i, j] = []
                busqueda(i, j, matriz[i][j], id)

    max = 0
    kmax = 0
    for key, value in d.items():
        if len(value) > max:
            max = len(value)
            kmax = key[0]

    resultado = (kmax + ',' + str(max))

    return resultado

Function to fill 'A' matrix

import matriz
def matriz_a(filas, columnas):
    matriz = []
    cad = ""
    for i in range(columnas):
      matriz.append([cad.join('A') for _ in range(filas)])



    return matriz

var=matriz_a(40,40)
print(matriz.calcular(var))

Random function that does not generate an error.

import string
import random
import matriz

def matriz_random(filas,columnas, chars=string.ascii_uppercase):
    matriza=[]
    cad=""
    for i in range(columnas):
       cadena=cad.join(random.choice(chars) for _ in range(filas))
       matriza.append(cadena)

    return matriza

matrizb=matriz_random(100,100)
print(matriz.calcular(matrizb))

python python-3.x

asked by PCH 29.05.2017 в 19:53

source

2 answers

1

I understand that the recursion error should be giving you busqueda since it is the only one that is just recursive. Python has a limit in this respect that you can consult through getrecursionlimit that if I'm not wrong is 1000 and eventually modify it with setrecursionlimit , although in reality it would be optimal to do without of the recursion. Because it gives you error about a matrix with the same value and not with another that has random values, it is because busqueda justly activates the recursion when there are similar values ( vecinos ) and 40 x 40 is an important number ( 1600) would have to prove with a matrix of 30 x 30 that if my hypothesis is correct I should not give you error

answered by 29.05.2017 в 20:30

Rare characters in emails sent with PHP Save all matches of a group in Regex

score 2 · Accepted Answer

In Python, the recursive calls that a function can make are limited to 1000. In the cases that you pose this happens because all the elements of the matrix are the same, the 'spot' that the DFS algorithm must look for (Depth-first search ) is actually the complete matrix, so it ends up being called recursively more than 1000 times before finding all the elements that make up the 'stain'. This will happen to any 'spot' large enough to overcome the recursion limit. You can increase the limit using:

import sys
sys.setrecursionlimit(n) #donde 'n' es un entero representando límite máximo de recursiones

However, this is not a recommended solution in the vast majority of cases. It is always preferable, at these limits, to optimize the code, use vectorization or do the iterative algorithm to avoid overcoming 1000 recursive calls.

Guido van Rossum gives an explanation of why this is in Python if you are interested:

link

Edit:

One possible solution is to make the iterative algorithm as I mentioned, for this we can use a queue that makes adding and extracting elements at the ends much more efficient than using lists. You can replace your function busqueda with this:

from collections import deque #agregar al inicio del script

def busqueda(f, c, value, id):
    nodos  = deque()
    nodos.append((f,c))
    while nodos:
        f, c = nodos.pop()
        vecinos = ((i, j) for i, j in ((f - 1, c), (f, c - 1), (f, c + 1), (f + 1, c))
               if i >= 0 and i < m and j >= 0 and j < n and matriz[i][j] == value)
        for i, j in vecinos:
            d[id].append((value, i, j))
            matriz[i][j] = False
            nodos.append((i, j))

With this:

var=matriz_a(1000,1000)
print(matriz.calcular(var))

Exit:

A, 1000000

The execution time, in my case, is 3 seconds for the matrix of 1 million equal elements and 5 seconds for one of random elements of the same size. It can be done much more efficiently without a doubt, but it's a good idea to start with.