Thực hiện phân đoạn cây bằng Python

Question

Tôi giải quyết this vấn đề sử dụng segment tree nhưng tôi gặp lỗi giới hạn thời gian. Dưới đây là mã thô của tôi cho truy vấn tối thiểu trong phạm vi và bằng cách thay đổi min thành max trong mã của tôi, vấn đề trên có thể được giải quyết. Tôi không biết làm thế nào tôi có thể cải thiện hiệu suất của mã của tôi. Bạn có thể giúp tôi với các vấn đề hiệu suất của nó?

t = [None] * 2 * 7  # n is length of list 


def build(a, v, start, end): 
    ''' 
    A recursive function that constructs Segment Tree for list a. 
    v is the starting node 
    start and end are the index of array 
    ''' 

    n = len(a) 
    if start == end: 
     t[v] = a[start] 
    else: 
     mid = (start + end)/2 
     build(a, v * 2, start, mid)  # v*2 is left child of parent v 
     # v*2+1 is the right child of parent v 
     build(a, v * 2 + 1, mid + 1, end) 
     t[v] = min(t[2 * v], t[2 * v + 1]) 
    return t 

print build([18, 17, 13, 19, 15, 11, 20], 1, 0, 6) 

inf = 10**9 + 7 


def range_minimum_query(node, segx, segy, qx, qy): 
    ''' 
    returns the minimum number in range(qx,qy) 
    segx and segy represent the segment index 

    ''' 
    if qx > segy or qy < segx:  # query out of range 
     return inf 
    elif segx >= qx and segy <= qy: # query range inside segment range 
     return t[node] 
    else: 
     return min(range_minimum_query(node * 2, segx, (segx + segy)/2, qx, qy), range_minimum_query(node * 2 + 1, ((segx + segy)/2) + 1, segy, qx, qy)) 

print range_minimum_query(1, 1, 7, 1, 3) 

# returns 13 

Điều này có thể được triển khai lặp lại không?

Answer 1

Lựa chọn ngôn ngữ

Đầu tiên, có thể bạn sẽ không bao giờ vượt qua nếu bạn học sinh lớp sử dụng python. Nếu bạn nhìn vào trạng thái của tất cả các giải pháp trong quá khứ ở đây, http://www.spoj.com/status/GSS1/start=0, bạn sẽ thấy rằng mọi giải pháp được chấp nhận gần như đã được viết bằng C++. Tôi không nghĩ rằng bạn có một sự lựa chọn, nhưng để sử dụng C + +. Chú ý cách giới hạn thời gian là 0.115s-0.230s. Đó là giới hạn thời gian "chỉ dành cho C/C++". Đối với các vấn đề sẽ chấp nhận các giải pháp bằng các ngôn ngữ khác, thời hạn sẽ là một số "tròn" như 1 giây. Python chậm hơn khoảng 2-4x so với C++ trong loại môi trường này.

Sự cố triển khai phân đoạn cây ...?

Thứ hai, tôi không chắc liệu mã của bạn có thực sự đang xây dựng một cây phân khúc hay không. Cụ thể, tôi không hiểu tại sao dòng này lại có:

t[v]=min(t[2*v],t[2*v+1]) 

Tôi chắc rằng một nút trong cây phân đoạn lưu trữ tổng số con của nó, vì vậy nếu việc triển khai của bạn gần đúng, tôi nghĩ rằng thay vào đó nên đọc

t[v] = t[2*v] + t[2*v+1] 

Nếu mã của bạn là "đúng", sau đó tôi sẽ đặt câu hỏi làm thế nào bạn đang tìm tổng khoảng cách tối đa trong phạm vi [x_i, y_i] nếu bạn thậm chí không lưu trữ các khoản tiền khoảng.

Cây phân đoạn lặp lại

Thứ ba, một đoạn cây có thể được thực hiện lặp lại. Đây là hướng dẫn trong C++: http://codeforces.com/blog/entry/18051.

cây bộ phận được không cho là đủ nhanh cho điều này ...

Cuối cùng, tôi không hiểu tại sao một cây phân khúc sẽ giúp bạn đối với vấn đề này. Cây phân khúc cho phép bạn truy vấn tổng của một phạm vi trong log(n). Vấn đề này yêu cầu số tiền tối đa có thể có của bất kỳ phạm vi nào. Tôi chưa nghe nói về cây phân đoạn cho phép "truy vấn tối thiểu phạm vi" hoặc "truy vấn tối đa phạm vi."

Một giải pháp ngây thơ sẽ là O (n^3) (thử tất cả n^2 điểm bắt đầu và kết thúc có thể và tính tổng trong các hoạt động O (n)) cho 1 truy vấn. Và, nếu bạn sử dụng cây phân đoạn , bạn có thể lấy tổng trong O (log (n)) thay vì O (n) .Chỉ tăng tốc độ bạn lên O (n^2 log (n)), không thể làm việc cho N = 50000.

thay thế thuật toán

tôi nghĩ bạn nên nhìn vào thay vì này, chạy trong thời gian O (n) cho mỗi truy vấn:. http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/ Viết nó trong C/C++ và có hiệu quả với IO là một commenter đề nghị

Answer 2

Bạn có thể thử máy phát điện vì bạn có thể gặp nhiều hạn chế. Tuy nhiên, bạn đã không cung cấp tập dữ liệu cho thấy các vấn đề về hiệu suất của bạn rõ ràng - bạn có thể cung cấp tập dữ liệu có vấn đề không?

Ở đây bạn có thể thử:

t=[None]*2*7 
inf=10**9+7 

def build_generator(a, v, start, end): 
    n = len(a) 

    if start == end: 
     t[v] = a[start] 
    else: 
     mid = (start + end)/2 
     next(build_generator(a, v * 2, start, mid)) 
     next(build_generator(a, v * 2 + 1, mid + 1, end)) 
     t[v] = min(t[2 * v], t[2 * v + 1]) 
    yield t 



def range_minimum_query_generator(node,segx,segy,qx,qy): 
    if qx > segy or qy < segx: 
     yield inf 
    elif segx >= qx and segy <= qy: 
     yield t[node] 
    else: 
     min_ = min(
      next(range_minimum_query_generator(node*2,segx,(segx+segy)/2,qx,qy)), 
      next(range_minimum_query_generator(node*2+1,((segx+segy)/2)+1,segy,qx,qy)) 
     ) 
     yield min_ 

next(build_generator([18,17,13,19,15,11,20],1,0,6)) 
value = next(range_minimum_query_generator(1, 1, 7, 1, 3)) 
print(value) 

EDIT

Trong thực tế có thể không giải quyết được vấn đề của bạn. Có một cách khác để workaround bất kỳ giới hạn đệ quy (như mô tả của D. Beazley trong hướng dẫn của nó đối với máy phát điện - https://www.youtube.com/watch?v=D1twn9kLmYg&t=9588s quanh timecode 2h00)