Tiền tố chung dài nhất sử dụng bộ đệm?

Question

Nếu tôi có một chuỗi đầu vào và một mảng:

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

Tôi cố gắng để tìm ra tiền tố chung dài nhất giữa các yếu tố liên tiếp của mảng pos tham khảo bản gốc s. Tôi cố gắng để có được kết quả như sau:

longest = [3,1] 

Con đường tôi thu được điều này bằng cách tính toán tiền tố chung dài nhất của các cặp sau:

• s[15:] đó là _be và s[2:] đó là _be_or_not_to_be cho 3 (_be)
• s[2:] là _be_or_not_to_be và s[8:] là _not_to_be tặng 1 (_)

Tuy nhiên, nếu s là rất lớn, tôi không muốn tạo nhiều bản sao khi tôi làm điều gì đó như s[x:]. Sau nhiều giờ tìm kiếm, tôi tìm thấy hàm buffer chỉ duy trì một bản sao của chuỗi đầu vào nhưng tôi không chắc chắn cách hiệu quả nhất để sử dụng nó ở đây trong ngữ cảnh này là gì. Bất kỳ đề xuất về cách để đạt được điều này?

Answer 1

Dưới đây là một phương pháp mà không buffer mà không sao chép, vì nó chỉ nhìn vào một ký tự tại một thời điểm:

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 

tôi sử dụng islice, izip, và xrange trong trường hợp bạn đang nói về khả năng rất chuỗi dài.

Tôi cũng không thể cưỡng lại này "Một Liner" mà thậm chí không yêu cầu bất kỳ lập chỉ mục:

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

Một phương pháp cuối cùng, sử dụng os.path.commonprefix:

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

Answer 2

Tôi nghĩ rằng bạn lo lắng về các bản sao không có cơ sở. Xem bên dưới:

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

Trừ khi bạn sao chép các lát và để lại tham chiếu đến các bản sao treo xung quanh, tôi không nghĩ rằng nó có thể gây ra bất kỳ sự cố nào.

---

chỉnh sửa: Có những chi tiết kỹ thuật với chuỗi interning và thứ mà tôi không thực sự rõ ràng về bản thân mình. Nhưng tôi chắc chắn rằng một chuỗi lát không phải là luôn một bản sao:

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

Tôi đoán câu trả lời tôi đang cố gắng để đưa ra là chỉ để cho trăn quản lý bộ nhớ của nó chính nó, để bắt đầu với, bạn có thể xem bộ nhớ đệm và xem sau nếu cần. Và nếu điều này đã là một vấn đề thực sự xảy ra với bạn, hãy cập nhật câu hỏi của bạn với các chi tiết về vấn đề thực tế là gì.

Answer 3

Một cách để thực hiện việc sử dụng buffer tùy chọn này được cung cấp dưới đây. Tuy nhiên, có thể có nhiều cách nhanh hơn.

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]) 
'_' 

Hãy Python để quản lý bộ nhớ cho bạn. Đừng tối ưu hóa sớm.

Để có được kết quả chính xác mà bạn có thể làm (như @agf suggested):

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