Cấu trúc dữ liệu cho các khoảng thời gian xử lý

Question

Tôi có một chuỗi khoảng thời gian (t_start, t_end), không thể chồng lên nhau, tức là: t_end (i)> t_start (i + 1). Tôi muốn thực hiện các thao tác sau:

1) Thêm khoảng thời gian (Liên minh) mới [{(1,4), (8,10)} U (3,7) = {(1,7), (8,10)}]
2) Lấy khoảng thời gian ra [(1,7) - (3,5) = {(1,3), (5,7)}
3) Kiểm tra xem một điểm hoặc một khoảng chồng chéo với một khoảng thời gian trong chuỗi của tôi (giao lộ)
4) Tìm "khoảng không" đầu tiên có độ dài tối thiểu sau một số điểm [{(1,4), (7,8)}: có một "không khoảng "độ dài 3 từ 4 đến 7].

Tôi muốn biết cách thực hiện tốt điều này, với độ phức tạp thấp (nhật ký n cho tất cả các thao tác sẽ thực hiện).

câu hỏi liên quan: Data structure for quick time interval look up

Answer 1

Có vẻ như bạn chỉ có thể sử dụng cây nhị phân cân bằng của tất cả các thời gian biên.

Ví dụ, đại diện cho {(1,4), (8,10), (12,15)} như một cây có chứa 1, 4, 8, 10, 12, và 15.

Mỗi nút cần phải nói cho dù đó là sự bắt đầu hoặc kết thúc của một khoảng thời gian. Vì vậy:

      8 (start) 
         /  \ 
       1 (start)   12 (start) 
         \   / \ 
        4 (end) 10 (end) 15 (end) 

(Ở đây tất cả các "kết thúc" nút đã kết thúc ở phía dưới bằng cách trùng hợp ngẫu nhiên.)

Sau đó, tôi nghĩ bạn có thể có tất cả các hoạt động của bạn trong thời gian O (log n) thời gian. Để thêm khoảng thời gian:

• Tìm thời gian bắt đầu. Nếu nó đã có trong cây như là một thời gian bắt đầu, bạn có thể để nó ở đó. Nếu nó đã có trong cây như là một thời gian kết thúc, bạn sẽ muốn loại bỏ nó. Nếu nó không có trong cây và, nó không rơi trong khoảng thời gian hiện tại, bạn sẽ muốn thêm nó. Nếu không, bạn không muốn thêm nó.

• Tìm thời gian dừng, sử dụng cùng một phương pháp để tìm hiểu xem bạn có cần thêm nó, xóa hoặc không.

• Bây giờ bạn chỉ muốn thêm hoặc xóa các nút bắt đầu và dừng ở trên cùng, đồng thời xóa tất cả các nút hiện có ở giữa. Để làm điều này, bạn chỉ cần xây dựng lại các nút cây tại hoặc trực tiếp trên hai vị trí đó trong cây. Nếu chiều cao của cây là O (log n), mà bạn có thể đảm bảo bằng cách sử dụng một cây cân bằng, điều này có thời gian O (log n).

(Tuyên bố từ chối trách nhiệm: Nếu bạn đang dùng C++ và quản lý bộ nhớ rõ ràng, bạn có thể giải phóng nhiều hơn bộ nhớ O (log n) như bạn làm, nhưng thực sự mất thời gian một nút phải được lập hóa đơn cho bất cứ ai đã thêm nó, tôi nghĩ vậy.)

Xóa khoảng thời gian phần lớn là giống nhau.

Kiểm tra một điểm hoặc khoảng cách thật đơn giản.

Tìm khoảng cách đầu tiên của ít nhất một kích thước nhất định sau một thời gian nhất định thể được thực hiện trong thời gian O (log n) cũng vậy, nếu bạn cũng cất giữ thêm hai mẩu thông tin mỗi nút:

• Trong mỗi nút bắt đầu (ngoài nút ngoài cùng bên trái), kích thước của khoảng trống ngay lập tức ở bên trái.

• Trong mỗi nút, kích thước của khoảng cách lớn nhất xuất hiện trong cây con đó.

Để tìm khoảng trống đầu tiên của một kích thước nhất định xuất hiện sau một thời gian nhất định, trước tiên hãy tìm thời gian đó trong cây. Sau đó đi bộ lên cho đến khi bạn đạt đến một nút mà tuyên bố có chứa một khoảng cách đủ lớn. Nếu bạn đi lên từ bên phải, bạn biết khoảng cách này là bên trái, vì vậy bạn bỏ qua nó và tiếp tục đi lên. Nếu không, bạn đến từ bên trái. Nếu nút là nút bắt đầu, hãy kiểm tra xem khoảng trống bên trái của nó có đủ lớn không. Nếu vậy, bạn đã hoàn tất. Nếu không, khoảng cách đủ lớn phải ở đâu đó bên phải. Đi xuống bên phải và tiếp tục xuống cho đến khi bạn tìm thấy khoảng trống. Một lần nữa, bởi vì chiều cao của cây là O (log n), đi bộ ba lần (xuống, lên, và có thể xuống một lần nữa) là O (log n).

Answer 2

Mà không biết nữa chi tiết cụ thể, tôi muốn khuyên bạn nên đọc về Interval Trees. Cây khoảng thời gian là trường hợp 1 chiều đặc biệt của chung hơn kd-trees và có thời gian xây dựng O(n log n) và O(log n) thời gian hoạt động điển hình. Triển khai thuật toán chính xác bạn cần phải tìm chính mình, nhưng bạn có thể bắt đầu bằng cách xem CGAL.

Answer 3

Tôi biết bạn đã chấp nhận câu trả lời, nhưng vì bạn đã chỉ ra rằng bạn có thể sẽ thực hiện trong C++, bạn cũng có thể xem Thư viện vùng chứa tăng tốc (http://www.boost.org/doc/libs/1_46_1/libs/icl/doc/html/index.html).

Answer 4

Thực thi cây khoảng cách của tôi với cây AVL.

public class IntervalTreeAVL<T>{ 
    private static class TreeNode<T>{ 
     private T low; 
     private T high; 
     private TreeNode<T> left; 
     private TreeNode<T> right; 
     private T max; 
     private int height; 
     private TreeNode(T l, T h){ 
      this.low=l; 
      this.high=h; 
      this.max=high; 
      this.height=1; 
     } 
    } 
    private TreeNode<T> root; 
    public void insert(T l, T h){ 
     root=insert(root, l, h); 
    } 
    private TreeNode<T> insert(TreeNode<T> node, T l, T h){ 
     if(node==null){ 
      return new TreeNode<T>(l, h); 
     } 
     else{ 
      int k=((Comparable)node.low).compareTo(l); 
      if(k>0){ 
       node.left=insert(node.left, l, h); 
      } 
      else{ 
       node.right=insert(node.right, l, h); 
      } 
      node.height=Math.max(height(node.left), height(node.right))+1; 
      node.max=findMax(node); 
      int hd = heightDiff(node); 
      if(hd<-1){ 
       int kk=heightDiff(node.right); 
       if(kk>0){ 
        node.right=rightRotate(node.right); 
        return leftRotate(node); 
       } 
       else{ 
        return leftRotate(node); 
       } 
      } 
      else if(hd>1){ 
       if(heightDiff(node.left)<0){ 
        node.left = leftRotate(node.left); 
        return rightRotate(node); 
       } 
       else{ 
        return rightRotate(node); 
       } 
      } 
      else; 
     } 
     return node; 
    } 
    private TreeNode<T> leftRotate(TreeNode<T> n){ 
     TreeNode<T> r = n.right; 
     n.right = r.left; 
     r.left=n; 
     n.height=Math.max(height(n.left), height(n.right))+1; 
     r.height=Math.max(height(r.left), height(r.right))+1; 
     n.max=findMax(n); 
     r.max=findMax(r); 
     return r; 
    } 
    private TreeNode<T> rightRotate(TreeNode<T> n){ 
     TreeNode<T> r = n.left; 
     n.left = r.right; 
     r.right=n; 
     n.height=Math.max(height(n.left), height(n.right))+1; 
     r.height=Math.max(height(r.left), height(r.right))+1; 
     n.max=findMax(n); 
     r.max=findMax(r); 
     return r; 
    } 
    private int heightDiff(TreeNode<T> a){ 
     if(a==null){ 
      return 0; 
     } 
     return height(a.left)-height(a.right); 
    } 
    private int height(TreeNode<T> a){ 
     if(a==null){ 
      return 0; 
     } 
     return a.height; 
    } 
    private T findMax(TreeNode<T> n){ 
     if(n.left==null && n.right==null){ 
      return n.max; 
     } 
     if(n.left==null){ 
      if(((Comparable)n.right.max).compareTo(n.max)>0){ 
       return n.right.max; 
      } 
      else{ 
       return n.max; 
      } 
     } 
     if(n.right==null){ 
      if(((Comparable)n.left.max).compareTo(n.max)>0){ 
       return n.left.max; 
      } 
      else{ 
       return n.max; 
      } 
     } 
     Comparable c1 = (Comparable)n.left.max; 
     Comparable c2 = (Comparable)n.right.max; 
     Comparable c3 = (Comparable)n.max; 
     T max=null; 
     if(c1.compareTo(c2)<0){ 
      max=n.right.max; 
     } 
     else{ 
      max=n.left.max; 
     } 
     if(c3.compareTo((Comparable)max)>0){ 
      max=n.max; 
     } 
     return max; 
    } 


TreeNode intervalSearch(T t1){ 
     TreeNode<T> t = root; 
     while(t!=null && !isInside(t, t1)){ 
      if(t.left!=null){ 
        if(((Comparable)t.left.max).compareTo(t1)>0){ 
        t=t.left; 
       } 
       else{ 
        t=t.right; 
       } 
      } 
      else{ 
       t=t.right; 
      } 
     } 
     return t; 
    } 
    private boolean isInside(TreeNode<T> node, T t){ 
     Comparable cLow=(Comparable)node.low; 
     Comparable cHigh=(Comparable)node.high; 
     int i = cLow.compareTo(t); 
     int j = cHigh.compareTo(t); 
     if(i<=0 && j>=0){ 
      return true; 
     } 
     return false; 
    } 
} 

Answer 5

Tôi vừa tìm thấy Guava's Range và RangeSet làm chính xác điều đó.

Nó thực hiện tất cả các hoạt động được trích dẫn:

1. Liên minh

   RangeSet<Integer> intervals = TreeRangeSet.create(); 
   intervals.add(Range.closedOpen(1,4)); // stores {[1,4)} 
   intervals.add(Range.closedOpen(8,10)); // stores {[1,4), [8,10)} 
   // Now unite 3,7 
   intervals.add(Range.closedOpen(3,7)); // stores {[1,7), [8,10)} 
   

2. Subraction

   intervals.remove(Range.closedOpen(3,5)); //stores {[1,3), [5, 7), [8, 10)} 
   

3. Intersection

   0.123.

   intervals.contains(3); // returns false 
   intervals.contains(5); // returns true 
   intervals.encloses(Range.closedOpen(2,4)); //returns false 
   intervals.subRangeSet(Range.closedOpen(2,4)); // returns {[2,3)} (isEmpty returns false) 
   intervals.subRangeSet(Range.closedOpen(3,5)).isEmpty(); // returns true 
   

4. tìm khoảng trống (đây sẽ là sự phức tạp giống như một sự lặp lại thiết lập trong trường hợp xấu nhất):

   Range freeSpace(RangeSet<Integer> ranges, int size) { 
       RangeSet<Integer> frees = intervals.complement().subRangeSet(Range.atLeast(0)); 
       for (Range free : frees.asRanges()) { 
        if (!free.hasUpperBound()) { 
         return free; 
        } 
        if (free.upperEndpoint() - free.lowerEndpoint() >= size) { 
         return free; 
        } 
       }