¿El prefijo común más largo usa el búfer?

Question

Si tengo una cadena de entrada y una matriz:

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

Estoy tratando de encontrar el prefijo común más largo entre los elementos consecutivos de la matriz pos referencia al original s. Estoy tratando de obtener el siguiente resultado:

longest = [3,1] 

La forma obtuve esto es calculando el prefijo común más largo de los siguientes pares:

• s[15:] que es _be y s[2:] cuales es _be_or_not_to_be dar 3 (_be)
• s[2:] que es _be_or_not_to_be y s[8:] que se _not_to_be dando 1 (_)

Sin embargo, si s es enorme, no quiero crear copias múltiples cuando hago algo como s[x:]. Después de horas de búsqueda, encontré la función buffer que mantiene solo una copia de la cadena de entrada, pero no estaba seguro de cuál es la forma más eficiente de utilizarla aquí en este contexto. ¿Alguna sugerencia sobre cómo lograr esto?

Answer 1

Aquí es un método sin buffer, que no sea copia, ya que sólo se basa en un carácter a la vez:

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 

utilizo islice, izip y xrange en el caso que estamos hablando potencialmente muy cadenas largas.

tampoco podía resistir esta "un trazador de líneas", que ni siquiera requiere ninguna indexación:

[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 método final, utilizando os.path.commonprefix:

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

Answer 2

Creo que su preocupación por las copias no tiene fundamento. Ver más abajo:

>>> 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 menos que vaya a copiar las rebanadas y dejando las referencias a las copias dando vueltas, no me creo que podría causar ningún problema.

---

edición: Hay detalles técnicos con cadena de internar y otras cosas que no estoy muy claro en mi mismo. Pero estoy seguro de que una rebanada cadena no es siempre una copia:

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

supongo que la respuesta que estoy tratando de dar es dejar que pitón gestionar su propia memoria, para empezar, se puede mira los búferes de memoria y las vistas más adelante si es necesario. Y si esto ya es un problema real que ocurre para usted, actualice su pregunta con detalles de cuál es el problema real.

Answer 3

Una forma de hacerlo usando buffer esto es dar a continuación. Sin embargo, podría haber formas mucho más rápidas.

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 para gestionar la memoria para usted. No optimice prematuramente.

para obtener la salida exacta que podría hacer (como @agf suggested):

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