Tại sao tiêu chuẩn C++ yêu cầu std :: partition để đáp ứng các phức tạp khác nhau cho các loại trình lặp khác nhau?

Question

Tiêu chuẩn C++ yêu cầu std::partition để có số ứng dụng vị ngữ khác nhau giữa ForwardIterator và BidirectionalIterator. Đối với phiên bản ForwardIterator, số lượng các ứng dụng vị sẽ < = N, nơi N = std::distance(first, last), nhưng đối với các phiên bản BidirectionalIterator, số lượng các ứng dụng vị sẽ < = N/2. Rõ ràng, cả hai phiên bản đều có độ phức tạp thời gian O (N).

Câu hỏi của tôi là, tại sao nó lại cung cấp các yêu cầu khác nhau cho các loại trình lặp khác nhau? Yêu cầu đó buộc phải có nhiều trình biên dịch?

ví dụ: MSVC, triển khai chức năng std::partition theo hai cách để đáp ứng yêu cầu đó, có vẻ không quá thanh lịch.

Một câu hỏi nữa: Có bất kỳ thuật toán dựa trên hệ số này, sao cho khi N/2 trở thành N, sự phức tạp tiệm cận sẽ khác nhau? Đối với sự hiểu biết của tôi, nếu chúng tôi xem xét Master's Theorem, đối với biểu mẫu trong T(n) = aT(n/b) + f(n), hệ số trong f(n) không quan trọng nhiều.

C.f. Việc triển khai tương đương phân vùng của MSVC:

template<class BidirIt, class UnaryPred> 
BidirIt partition(BidirIt first, BidirIt last, UnaryPred pred, std::bidirectional_iterator_tag) 
{ 
    while (true) 
    { 
     while ((first != last) && pred(*first)) 
     { 
      ++first; 
     } 
     if (first == last) 
     { 
      break; 
     } 
     --last; 
     while ((first != last) && !pred(*last)) 
     { 
      --last; 
     } 
     if (first == last) 
     { 
      break; 
     } 
     std::iter_swap(first, last); 
     ++first; 
    } 
    return first; 
} 
template<class ForwardIt, class UnaryPred> 
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPred pred, std::forward_iterator_tag) 
{ 
    first = std::find_if_not(first, last, pred); 
    if (first == last) 
    { 
     return first; 
    } 

    for (ForwardIt src = std::next(first); src != last; ++src) 
    { 
     if (pred(*src)) 
     { 
      std::iter_swap(first, src); 
      ++src; 
     } 
    } 
    return first; 
} 
template<class ForwardIt, class UnaryPred> 
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPred pred) 
{ 
    return partition(first, last, pred, typename std::iterator_traits<ForwardIt>::iterator_category()); 
} 

Answer 1

Vị từ pred được thực thi chính xác N lần trong cả hai trường hợp - mỗi phần tử phải được kiểm tra một lần. Sự khác biệt giữa ForwardIterator và BidirectionalIterator là số tiền hoán đổi.

BidirectionalIterator có tối đa N/2 hoán đổi, vì nó quét phạm vi từ phía trước và từ phía sau cùng một lúc, khi nó đạt giá trị từ bên trái không hoàn thành vị từ và giá trị từ bên phải thực hiện nó, nó hoán đổi chúng. Vì vậy, trong trường hợp xấu nhất nó có thể làm công việc của nó trong N/2 hoán đổi.

ForwardIterator không có lợi thế đó và trong trường hợp xấu nhất có thể thực hiện hoán đổi cho mọi phần tử.

Tiêu chuẩn yêu cầu hai giới hạn khác nhau, vì chúng là cả hai giới hạn tốt nhất có thể nhận được. Vì vậy, các lập trình viên có thể tin tưởng rằng mọi thực thi thư viện chuẩn sẽ hành xử theo cách đó.

Answer 2

Đúng vậy, độ phức tạp của thời gian vẫn như cũ.

Điều quan trọng cần lưu ý là giao dịch hoán đổi thực sự khá tốn kém. Đặc biệt là đối tượng lớn. Hầu hết thời gian họ liên quan đến ba hoạt động di chuyển. Trong các tình huống như vậy, chúng ta nên giảm số lượng hoán đổi xuống mức tối thiểu. Bằng cách sử dụng các trình vòng lặp hai chiều, chúng tôi nhận được sự cải thiện đáng kể về hiệu quả, mặc dù độ phức tạp của thời gian là như nhau.

Hãy nhớ rằng, trong môi trường thực, nó có thể rất quan trọng cho các hoạt động đơn giản được thực hiện nhanh chóng. Bất cứ khi nào có khả năng làm như vậy, nó phải được thực hiện theo cách này. Khi làm việc với các thuật toán phức tạp (thường là đối với các biến thể của các vấn đề NP-complete) mất nhiều thời gian để tính toán nó có thể rất quan trọng để thực hiện thao tác trong thời gian ít hơn một nửa. Bạn có muốn có độ trễ từ 0,2 giây đến 0,1 giây không? Sự phức tạp thời gian là một loạt các lý thuyết tốt đẹp nhưng thế giới thực không phải là quá đẹp và mỗi phần của thứ hai là quan trọng.