Tocando la máxima profundidad de recursión usando Pickle/cPickle

Question

El trasfondo: Estoy construyendo un trie para representar un diccionario, usando un algoritmo de construcción mínimo. La lista de entrada es de 4.3M utf-8 strings, ordenados lexicográficamente. El gráfico resultante es acíclico y tiene una profundidad máxima de 638 nodos. La primera línea de mi script establece el límite de recursión en 1100 a través de sys.setrecursionlimit().

El problema: me gustaría poder serializar mi trie en el disco, por lo que puedo cargarlo en la memoria sin tener que reconstruir desde cero (aproximadamente 22 minutos). He intentado ambos pickle.dump() y cPickle.dump(), con el texto y los protocolos binarios. Cada vez, me sale una pila-huella que tiene el siguiente aspecto:

File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 649, in save_dict 
    self._batch_setitems(obj.iteritems()) 
    File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 663, in _batch_setitems 
    save(v) 
    File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 286, in save 
    f(self, obj) # Call unbound method with explicit self 
    File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 725, in save_inst 
    save(stuff) 
    File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 286, in save 
    f(self, obj) # Call unbound method with explicit self 
    File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 648, in save_dict 
    self.memoize(obj) 
RuntimeError: maximum recursion depth exceeded 

Mis estructuras de datos son relativamente simples: trie contiene una referencia a un estado de inicio, y define algunos métodos. dfa_state contiene un campo booleano, un campo de cadena y una asignación de diccionario de etiqueta a estado.

No estoy muy familiarizado con el funcionamiento interno de pickle - ¿mi profundidad de recursión máxima debe ser mayor/igual n veces la profundidad del trie para algunos n? ¿O podría ser causado por algo más que desconozco?

Actualización: Establecer la profundidad de recursión en 3000 no ayudó, por lo que esta avenida no parece prometedora.

Actualización 2: Tenían razón; Estaba siendo miope al suponer que Pickle usaría una profundidad de anidamiento pequeña debido a las limitaciones de recursión predeterminadas. 10,000 hizo el truco.

Answer 1

De the docs:

Tratando de decapado de una estructura de datos altamente recursivo puede exceder el nivel de recursividad máximo, un RuntimeError serán levantados en este caso. Puede elevar cuidadosamente este límite con sys.setrecursionlimit().

Aunque su implementación de trie puede ser simple, utiliza la recursión y puede ocasionar problemas al convertir a una estructura de datos persistente.

Mi recomendación sería continuar aumentando el límite de recursión para ver si hay un límite superior para los datos con los que está trabajando y la implementación que está utilizando.

Aparte de eso, puede intentar cambiar su aplicación árbol para ser "menos recursivo", si es posible, o escribir una implementación adicional que tiene la persistencia de datos incorporado (encurtidos uso y shelves en su aplicación). Espero que ayude

Answer 2

Comprueba que tu estructura sea acíclica.

Puede intentar aumentar el límite aún más. Hay un máximo difícil que depende de la plataforma, pero intentar 50000 sería razonable.

También intente decapando una versión trivialmente pequeña de su trie. Si pickle muere a pesar de que solo almacena un par de palabras de tres letras, entonces sabes que hay un problema fundamental con tu trie y no con el pickle. Pero si solo ocurre cuando intenta almacenar 10k palabras, entonces podría ser la culpa de una limitación de la plataforma encurtido.

Answer 3

Pickle necesita caminar recursivamente por su trie. Si Pickle usa solo 5 niveles de llamadas de función para hacer el trabajo, su trie de profundidad 638 necesitará el nivel establecido en más de 3000.

Pruebe un número mucho mayor, el límite de recursión está realmente allí para proteger a los usuarios tener que esperar demasiado si la recursión cae en un agujero infinito.

salmuera maneja ciclos ok, por lo que no importa incluso si su trie tenía un ciclo en el que hay

Answer 4

Tamaño de la pila también debe incrementarse con resource.setrlimit para evitar violación de segmento

Si utiliza simplemente sys.setrecursionlimit , aún puede segfault si alcanza el tamaño máximo de pila permitido por el kernel de Linux.

Este valor puede incrementarse con resource.setrlimit como se mencionó en: Setting stacksize in a python script

import pickle 
import resource 
import sys 

print resource.getrlimit(resource.RLIMIT_STACK) 
print sys.getrecursionlimit() 

max_rec = 0x100000 

# May segfault without this line. 0x100 is a guess at the size of each stack frame. 
resource.setrlimit(resource.RLIMIT_STACK, [0x100 * max_rec, resource.RLIM_INFINITY]) 
sys.setrecursionlimit(max_rec) 

a = [] 
# 0x10 is to account for subfunctions called inside `pickle`. 
for i in xrange(max_rec/0x10): 
    a = [a] 
print pickle.dumps(a, -1) 

Ver también: valor máximo What is the maximum recursion depth in Python, and how to increase it?

El valor predeterminado para mí es de 8 Mb.

Probado en Ubuntu 16.10, Python 2.7.12.

Answer 5

Mis necesidades eran algo inmediatas, así que resolví este problema guardando mi diccionario en formato .txt. Lo único es que cuando cargas tu archivo de nuevo, tienes que volver a transformarlo en un diccionario.

import json 

# Saving the dictionary 
with open('filename.txt', 'w') as file_handle: 
    file_handle.write(str(dictionary)) 

# Importing the .txt file 
with open('filename.txt', 'r') as file_handle: 
    f = '"' + file_handle.read() + '"' 

# From .txt file to dictionary 
dictionary = eval(json.loads(f)) 

Si esto no funciona, puede intentar exportar el diccionario utilizando el formato json.