Skip to main content
5 de 6
se eliminaron 24 caracteres en el cuerpo
FJSevilla
  • 62.1k
  • 7
  • 43
  • 68

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 natriz 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 para evitar superar 1000 llamadas recursiva, usar vectorización o hacer el algoritmo iterativo.

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 eficiente 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,10000

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.

FJSevilla
  • 62.1k
  • 7
  • 43
  • 68