Superamento MemoryError/runtime Slow compito Ashton String

Question

Nel Ashton String task, l'obiettivo è quello di:

Disporre tutte le sottostringhe distinti di una determinata stringa in lessicografico e concatenare. Stampa il carattere Kth di la stringa concatenata. È assicurato che il valore dato di K sarà valido cioè ci sarà un carattere Kth.

Il Input Format:

prima riga contiene un numero T cioè numero di casi di test. Prima linea di ogni test conterrà una stringa contenente caratteri (a-z) e seconda riga contiene un numero K.

Il Output Format:

Print carattere Kth (la stringa è 1 indicizzati)

E il Constraints sono

1 ≤ T ≤ 5
1 ≤ lunghezza ≤ 105
K sarà un numero intero appropriato.

Ad esempio, dato l'input:

1 
dbac 
3 

Il risultato sarebbe: c

Ho tentato il compito con questo codice e funziona per relativamente brevi stringhe:

from itertools import chain 

def zipngram(text, n=2): 
    words = list(text) 
    return zip(*[words[i:] for i in range(n)]) 

for _ in input(): 
    t = input() 
    position = int(input())-1 # 0th indexing 
    chargrams = chain(*[zipngram(t,i) for i in range(1,len(t)+1)]) 
    concatstr = ''.join(sorted([''.join(s) for s in chargrams])) 
    print (concatstr[position]) 

Ma se il file di input è simile al seguente: http://pastebin.com/raw/WEi2p09H e l'output desiderato è:

l 
s 
y 
h 
s 

L'interprete lancerà una MemoryError:

Traceback (most recent call last): 
    File "solution.py", line 11, in <module> 
    chargrams = chain(*[zipngram(t,i) for i in range(1,len(t)+1)]) 
    File "solution.py", line 11, in <listcomp> 
    chargrams = chain(*[zipngram(t,i) for i in range(1,len(t)+1)]) 
    File "solution.py", line 6, in zipngram 
    return zip(*[words[i:] for i in range(n)]) 
    File "solution.py", line 6, in <listcomp> 
    return zip(*[words[i:] for i in range(n)]) 
MemoryError 

Come può la MemoryError essere risolto? È risolvibile in un altro modo usando Python2 o Python3 nativi?

ho cercato di risolvere il MemoryError potando stack utilizzando heapq ma ora va in un super lento runtime spingendo e iniziano mucchio invece di prendere troppa memoria.

from itertools import chain 
import heapq 

t = int(input()) 
s = list(input()) 
k = int(input()) 

stack = [] 
for n in range(1,len(s)+1): 
    for j in range(n): 
     ngram = (''.join(s[j:])) 
     ngram_len = len(ngram) 
     # Push the ngram into the heapq. 
     heapq.heappush(stack, ngram) 
     pruned_stack = [] 
     temp_k = 0 
     # Prune stack. 
     while stack != [] and temp_k < k: 
      x = heapq.heappop(stack) 
      pruned_stack.append(x) 
      temp_k+=len(x) 
     # Replace stack with pruend_stack. 
     stack = pruned_stack 

print (''.join(chain(*pruned_stack))[k]) 

C'è un modo per bilanciare tra non usare troppa memoria che porta a MemoryError e troppo lento runtime con heapq spingere e popping?

Answer 1

MemoryError significa che il programma ha consumato tutta la memoria disponibile e quindi si è bloccato.

Una possibile soluzione è l'utilizzo di iterabili (funzionano anche in Py2 ma Py3 supporta meglio con essi) che sono pigri (calcolano il valore solo su richiesta, non tutti in una volta).

Adattare il programma per i generatori dovrebbe aver bisogno solo piccole modifiche, per indicizzare un generatore senza l'utilizzo di un elenco (che sarebbe annullare il beneficio pigro) vedere: Get the nth item of a generator in Python

Answer 2

provare questo codice, funziona per il grande campione.

def ashton(string, k): 
    #We need all the substrings, and they have to be sorted 
    sortedSubstrings = sorted_substrings(string) 
    count = 0 
    currentSubstring = 0 
    #Loop through the substrings, until we reach the kth character 
    while (count < k): 
     substringLen = len(sortedSubstrings[currentSubstring]) 
     #add the number of characters of the substring to our counter 
     count += substringLen 
     #advance the current substring by one 
     currentSubstring += 1 
    #We have the correct substring now, and calculate to get the right char 
    diff = count - k 
    #Return answer, index 1 = substring, index 2 = char in substring 
    return(sortedSubstrings[currentSubstring][substringLen-diff-1]) 

#Determine the substrings in correct order 
#Input: 'dbac', returns: a, ac, b, ba, bac, c, d, db, dba, dbac 
def sorted_substrings(string): 
    a = set() 
    length = len(string) 
    #loop through the string to get the substrings 
    for i in range(length): 
     for j in range(i + 1, length + 1): 
      #add each substring to our set 
      a.add(string[i:j]) 
    #we need the set to be sorted 
    a = sorted(a) 
    return a 

t = int(input()) 
for i in range(t): 
    s = input() 
    k = int(input()) 
    print(ashton(s, k))