Massima profondità di ricorsione mediante Pickle/cPickle

Question

Lo sfondo: sto costruendo un trie per rappresentare un dizionario, utilizzando un algoritmo di costruzione minimo. L'elenco di input è 4,3 M corde utf-8, ordinate lessicograficamente. Il grafico risultante è aciclico e ha una profondità massima di 638 nodi. La prima riga del mio script imposta il limite di ricorsione su 1100 tramite sys.setrecursionlimit().

Il problema: mi piacerebbe essere in grado di serializzare il mio trie su disco, così posso caricarlo in memoria senza dover ricostruire da zero (circa 22 minuti). Ho provato sia pickle.dump() e cPickle.dump(), con entrambi i protocolli di testo e binari. Ogni volta, ottengo uno stack-traccia che è simile al seguente:

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 

mie strutture di dati sono relativamente semplici: trie contiene un riferimento a uno stato di avvio, e definisce alcuni metodi. dfa_state contiene un campo booleano, un campo stringa e un dizionario che esegue il mapping dall'etichetta allo stato.

Non ho molta familiarità con il funzionamento interno di pickle - la mia profondità massima di ricorsione deve essere maggiore/uguale n volte la profondità del trie per alcuni n? O potrebbe essere causato da qualcos'altro di cui non sono a conoscenza?

Aggiornamento: L'impostazione della profondità di ricorsione a 3000 non ha aiutato, quindi questa strada non sembra promettente.

Aggiornamento 2: Voi ragazzi avete ragione; Ero miope nell'assumere che il pickle usasse una piccola profondità di annidamento a causa dei limiti di ricorsione predefiniti. 10.000 hanno fatto il trucco.

Answer 1

Da the docs:

Cercando decapare una struttura dati altamente ricorsiva può superare la profondità massima di ricorsione, un RuntimeError sarà esaltato in questo caso. È possibile aumentare con attenzione questo limite con sys.setrecursionlimit().

Sebbene l'implementazione del Trie possa essere semplice, utilizza la ricorsione e può causare problemi durante la conversione in una struttura di dati persistente.

La mia raccomandazione sarebbe continuare ad aumentare il limite di ricorsione per vedere se esiste un limite superiore per i dati con cui si sta lavorando e l'implementazione trie che si sta utilizzando.

A parte ciò, si può provare a cambiare l'implementazione albero per essere "meno ricorsiva", se possibile, o scrivere un'implementazione ulteriore che ha la persistenza dei dati integrata (uso sottaceti e shelves nell'implementazione). Spero che questo aiuti

Answer 2

Controlla che la tua struttura sia effettivamente aciclica.

Si potrebbe provare ad aumentare ulteriormente il limite. C'è un limite massimo che dipende dalla piattaforma, ma provare 50000 sarebbe ragionevole.

Prova anche a decapare una versione insignificante del tuo trie. Se decapita muore anche se memorizza solo un paio di parole di tre lettere, allora sai che c'è un problema fondamentale con il tuo trie e non il sottaceto. Ma se capita solo quando si tenta di memorizzare 10k parole, allora potrebbe essere colpa di una limitazione della piattaforma in pickle.

Answer 3

Pickle ha bisogno di ricorsivamente camminare il tuo trie. Se Pickle usa solo 5 livelli di chiamate di funzione per eseguire il lavoro, il tuo 639 livello di profondità richiederà il livello impostato su più di 3000.

Prova un numero molto più grande, il limite di ricorsione è davvero lì solo per proteggere gli utenti da dover aspettare troppo a lungo se la ricorsione cade in un buco infinito.

Pickle gestisce cicli ok, quindi non importa anche se il trie ha avuto un ciclo in là

Answer 4

dimensioni Stack deve essere aumentata con resource.setrlimit per evitare segfault

Se si utilizza solo sys.setrecursionlimit , puoi ancora segfault se raggiungi la dimensione massima dello stack consentita dal kernel di Linux.

Questo valore può essere aumentato con resource.setrlimit come accennato: 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) 

Vedi anche: valore massimo What is the maximum recursion depth in Python, and how to increase it?

L'impostazione predefinita per me è 8Mb.

Testato su Ubuntu 16.10, Python 2.7.12.

Answer 5

Le mie esigenze erano piuttosto immediate quindi ho risolto questo problema salvando il mio dizionario in formato .txt. L'unica cosa è che quando carichi di nuovo il tuo file devi trasformarlo di nuovo in un dizionario.

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

Se ciò non funziona, provare a esportare il dizionario utilizzando il formato json.