Skip to main content
Correciones ortográficas
Origen Enlace
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 natrizmatriz 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, 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 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 eficienteeficientes 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,100001000000

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.

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.

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.

se eliminaron 24 caracteres en el cuerpo
Origen Enlace
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. Si no he metido la pata puedesPuedes 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.

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. Si no he metido la pata 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.

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.

se añadió 1 carácter en el cuerpo
Origen Enlace
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. Si no he metido la pata puedes sustituir tu función busqueda por esta:

from collections import queuedeque #agregar al inicio del script

def busqueda(f, c, value, id):
    nodos  = queue.Queuedeque()
    nodos.putappend((f,c))
    while not nodos.empty():
        f, c = nodos.getpop()
        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.putappend((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 103 segundos para la matriz de 1 millón de elementos iguales y de 255 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.

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. Si no he metido la pata puedes sustituir tu función busqueda por esta:

import queue #agregar al inicio del script

def busqueda(f, c, value, id):
    nodos  = queue.Queue()
    nodos.put((f,c))
    while not nodos.empty():
        f, c = nodos.get()
        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.put((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 10 segundos para la matriz de 1 millón de elementos iguales y de 25 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.

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. Si no he metido la pata 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.

se añadieron 188 caracteres en el cuerpo
Origen Enlace
FJSevilla
  • 62.1k
  • 7
  • 43
  • 68
Loading
se añadieron 1012 caracteres en el cuerpo
Origen Enlace
FJSevilla
  • 62.1k
  • 7
  • 43
  • 68
Loading
Origen Enlace
FJSevilla
  • 62.1k
  • 7
  • 43
  • 68
Loading