Il prefisso più lungo comune utilizzando il buffer?

Question

Se ho una stringa di input e una serie:

s = "to_be_or_not_to_be" 
pos = [15, 2, 8] 

Sto cercando di trovare il più lungo prefisso comune tra gli elementi consecutivi della matrice pos riferimento all'originale s. Sto cercando di ottenere il seguente risultato:

longest = [3,1] 

Il modo in cui ho ottenuto questo calcolando il più lungo prefisso comune delle seguenti coppie:

• s[15:] che è _be e s[2:] quali è _be_or_not_to_be dando 3 (_be)
• s[2:] che è _be_or_not_to_be e s[8:] che è _not_to_be dando 1 (_)

Tuttavia, se s è enorme, non voglio creare più copie quando faccio qualcosa come s[x:]. Dopo ore di ricerche, ho trovato la funzione buffer che conserva solo una copia della stringa di input, ma non ero sicuro di quale sia il modo più efficiente di utilizzarlo qui in questo contesto. Qualche suggerimento su come ottenere questo?

Answer 1

Ecco un metodo senza buffer che non copia, come sembra solo un carattere alla volta:

from itertools import islice, izip 

s = "to_be_or_not_to_be" 
pos = [15, 2, 8] 


length = len(s)  

for start1, start2 in izip(pos, islice(pos, 1, None)): 
    pref = 0 
    for pos1, pos2 in izip(xrange(start1, length), xrange(start2, length)): 
     if s[pos1] == s[pos2]: 
      pref += 1 
     else: 
      break 
    print pref 
# prints 3 1 

io uso islice, izip, e xrange nel caso in cui si sta parlando, potenzialmente molto stringhe lunghe.

anche io non potevo resistere a questo "One Liner", che non ha nemmeno richiede alcuna indicizzazione:

[next((i for i, (a, b) in 
    enumerate(izip(islice(s, start1, None), islice(s, start2, None))) 
     if a != b), 
    length - max((start1, start2))) 
for start1, start2 in izip(pos, islice(pos, 1, None))] 

Un metodo finale, utilizzando os.path.commonprefix:

[len(commonprefix((buffer(s, n), buffer(s, m)))) for n, m in zip(pos, pos[1:])] 

Answer 2

Penso che la tua preoccupazione per le copie sia infondata. Vedi sotto:

>>> s = "how long is a piece of string...?" 
>>> t = s[12:] 
>>> print t 
a piece of string...? 
>>> id(t[0]) 
23295440 
>>> id(s[12]) 
23295440 
>>> id(t[2:20]) == id(s[14:32]) 
True 

A meno che non si sta copiando le fette e lasciando i riferimenti alle copie in giro, non vorrei pensare che potrebbe causare alcun problema.

---

edit: Non ci sono dettagli tecnici con stringa internato e cose che io non sono molto chiaro su me stesso. Ma sono sicuro che una fetta stringa non è sempre una copia:

>>> x = 'google.com' 
>>> y = x[:] 
>>> x is y 
True 

Credo che la risposta che sto cercando di dare è quello di lasciare che python gestire la sua stessa memoria, per cominciare, è possibile guarda i buffer di memoria e le viste in seguito, se necessario. E se questo è già un problema che si verifica per te, aggiorna la tua domanda con i dettagli di quale sia il vero problema.

Answer 3

Un modo di utilizzare buffer è fornito di seguito. Tuttavia, potrebbero esserci modi molto più veloci.

s = "to_be_or_not_to_be" 
pos = [15, 2, 8] 

lcp = [] 
length = len(pos) - 1 

for index in range(0, length): 
    pre = buffer(s, pos[index]) 
    cur = buffer(s, pos[index+1], pos[index+1]+len(pre)) 

    count = 0 

    shorter, longer = min(pre, cur), max(pre, cur) 

    for i, c in enumerate(shorter): 
     if c != longer[i]: 
      break 
     else: 
      count += 1 

    lcp.append(count) 
    print 

print lcp 

Answer 4

>>> import os 
>>> os.path.commonprefix([s[i:] for i in pos]) 
'_' 

Let Python di gestire la memoria per voi. Non ottimizzare in modo prematuro.

per ottenere il risultato esatto che si possa fare (come @agf suggested):

print [len(commonprefix([buffer(s, i) for i in adj_indexes])) 
     for adj_indexes in zip(pos, pos[1:])] 
# -> [3, 1]