1

Buena, tengo una duda, estoy haciendo unittest para una función que tengo y el problema es que al generar una matriz de 40x40, 50x50 del mismo elemento(por ej. 'A')en adelante me genera un recursion error, mientras que con una funcion de 1000x1000 random de A..Z no me genera ningun error.

El codigo es el siguiente.

Funcion de calculo de adyacentes:

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

Funcion para llenar matriz de 'A'

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

Funcion random que no genera 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))

2 respuestas 2

2

En Python las llamadas recursivas que una función puede hacer están limitadas a 1000. En los casos que planteas esto ocurre porque todos los elementos de la matriz son iguales, la 'mancha' que debe buscar el algoritmo DFS(Depth-first search) es en realidad la matriz completa, por lo que termina llamandose recursivamente más de 1000 veces antes de encontrar todos los elemntos que componen la 'mancha'. Esto te ocurrirá con cualquier 'mancha' lo suficientemente grande como para superar el límite de recursión. Puedes aumentar el límite usando:

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

No obstante, esta no es una solución recomendada en la gran mayoría de los casos. Siempre es preferible, llegados a estos límites, optimizar el código, usar vectorización o hacer el algoritmo iterativo para evitar superar 1000 llamadas recursivas.

Guido van Rossum da una explicación del porqué de esto en Python por si te interesa:

Edición:

Una posible solución es hacer el algoritmo iterativo como ya comenté, para ello nos podemos valer de una cola que hace las operaciones de adición y extracción de elementos en los extremos mucho más eficientes que usando listas. Puedes sustituir tu función busqueda por esta:

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

Con esto:

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

Salida:

A,1000000

El tiempo de ejecución, en mi caso, es de 3 segundos para la matriz de 1 millón de elementos iguales y de 5 segundos aproximadamente para una de elementos aleatorios del mismo tamaño. Se puede hacer mucho más eficiente sin duda, pero es una buena idea para empezar.

5
  • Si, era lo que sospechaba, en una matriz de 1000x1000 del mismo elemento tendría que entrar en la recursion 1millon de veces. Gracias por aclarar las dudas.
    – PCH
    Commented el 29 may. 2017 a las 18:57
  • @FrancoPachue he agregado una variante iterativa de la función por si te interesa. Saludos.
    – FJSevilla
    Commented el 29 may. 2017 a las 19:16
  • muchas gracias, justo estaba haciendo eso, tratando de realizar la variante iterativa, si no me equivoco para trasformar el algoritmo a iterativo, en vez de realizar una recursion tenemos que agregar un cola para usarla de pila? Viendo que la recursion tiene esta clase de problemas, es optimo siempre ir por la variante iterativa?
    – PCH
    Commented el 29 may. 2017 a las 22:01
  • @FrancoPachue efectivamente, en vez de por cada vecino encontrado llamar recursivamente a la función lo que hacemos es usar una cola donde ponemos el vecino e iteramos sobre ella mientras queden nodos a procesar. Se puede usar una lista, un conjunto o cualquier otro iterable no inmutable pero las colas son mucho más eficiente. Eso es lo que hace collections.deque (de la biblioteca estandar), implementa una cola. Usando un set la eficiencia es menor pero varía poco, una lista o usar queue.Queue si que son más ineficientes significativamente. Saludos.
    – FJSevilla
    Commented el 29 may. 2017 a las 22:06
  • Muchas gracias! La verdad que me sirve un montón todo esto. Un saludo!
    – PCH
    Commented el 29 may. 2017 a las 22:15
1

Entiendo que el error de recursión te lo debiera estar dando busqueda ya que es la única que justamente es recursiva. Python tiene un límite al respecto que podés consultar mediante getrecursionlimit que si no me equivoco es de 1000 y eventualmente modificarlo con setrecursionlimit, aunque en realidad lo óptimo sería prescindir de la recursión. Por que te da error sobre una matriz con un mismo valor y no con otra que tiene valores al azar se debe a que busqueda justamente activa la recursión cuando hay valores similares (vecinos) y 40 x 40 es un número importante (1600) habría que probar con una matriz de 30 x 30 que si mi hipótesis es correcta no te debería dar error

2
  • Si con 30x30 funciona, aunque seria el limite de mi matriz, gracias por la respuesta, si tengo mas de 1000 vecinos, me va a tirar error de recursión.
    – PCH
    Commented el 29 may. 2017 a las 18:59
  • Podrías aumentarlo el límite un poco, pero lo ideal es manejarse sin recursividad en estos caso. Commented el 29 may. 2017 a las 19:00

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.