Najdłuższy wspólny prefiks za pomocą bufora?

Question

Jeśli mam ciąg wejściowy i tablicy:

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

próbuję znaleźć najdłuższy wspólny przedrostek między kolejnymi elementami tablicy pos odwołującego oryginalny s. Próbuję uzyskać następujące dane wyjściowe:

longest = [3,1] 

Sposób, w jaki uzyskuje się to poprzez obliczenie najdłuższy wspólny przedrostek z następujących parach:

• s[15:] który jest _be i s[2:] który jest _be_or_not_to_be dając 3 (_be)
• s[2:] który _be_or_not_to_be i s[8:] który _not_to_be daje 1 (_)

Jednak, jeśli s jest ogromny, nie chcę tworzyć wielu kopii, gdy robię coś takiego jak s[x:]. Po wielu godzinach wyszukiwania znalazłem funkcję buffer, która zachowuje tylko jedną kopię ciągu wejściowego, ale nie byłem pewien, jaki jest najskuteczniejszy sposób wykorzystania go tutaj w tym kontekście. Wszelkie sugestie, jak to osiągnąć?

Answer 1

Oto metoda bez buffer który nie kopiuje, jak to wygląda tylko na jednym znaku naraz:

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 

używam islice, izip i xrange w przypadku, gdy mówimy o potencjalnie samych długich ciągów.

ja również nie mógł się oprzeć ten "jeden liner", który nawet nie wymaga żadnej indeksowania:

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

One ostateczną metodę, używając os.path.commonprefix:

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

Answer 2

Myślę, że twoje obawy dotyczące kopii są bezpodstawne. Zobacz poniżej:

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

Jeśli nie skopiujesz plasterków i nie pozostawisz odniesień do wiszących na nich kopii, nie sądzę, że może to spowodować problemy.

---

edit: Istnieją dane techniczne z internowanie łańcuchów i rzeczy, które tak naprawdę nie jestem jasne na siebie. Ale jestem pewien, że kawałek ciąg nie jest zawsze kopia:

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

Chyba odpowiedź Staram się dać to po prostu niech pyton zarządzać samą pamięć, na początek, można w razie potrzeby przejrzyj bufory pamięci i widoki później. A jeśli to już jest prawdziwy problem, zaktualizuj swoje pytanie, podając szczegóły rzeczywistego problemu.

Answer 3

Jednym ze sposobów korzystania z buffer jest to poniżej. Jednak może być znacznie szybciej.

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 zarządzać pamięci dla Ciebie. Nie optymalizuj przedwcześnie.

Aby uzyskać dokładne dane wyjściowe można zrobić (jak @agf suggested):

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