std :: queue <T, list<T>> :: size() chậm trong O (n)?

Question

Tôi gặp phải hành vi không mong muốn về hiệu suất của mã sử dụng hàng đợi. Tôi nhận ra rằng hiệu suất bị suy giảm khi có nhiều phần tử hơn trong hàng đợi. Hóa ra việc sử dụng phương pháp size() là lý do. Dưới đây là một số mã cho thấy sự cố:

#include <queue> 
#include <list> 
#include <iostream> 

#include "Stopwatch.h" 

using namespace std; 

struct BigStruct 
{ 
    int x[100]; 
}; 
int main() 
{ 
    CStopwatch queueTestSw; 

    typedef BigStruct QueueElementType; 
    typedef std::queue<QueueElementType, std::list<QueueElementType> > QueueType; 
    //typedef std::queue<QueueElementType > QueueType; //no surprise, this queue is fast and constant 
    QueueType m_queue; 

    for (int i=0;i<22000;i++) 
     m_queue.push(QueueElementType()); 
    CStopwatch sw; 
    sw.Start(); 
    int dummy; 
    while (!m_queue.empty()) 
    { 
     //remove 1000 elements: 
     for (int i=0;i<1000;i++) 
     { 
      m_queue.pop(); 
     } 
     //call size() 1000 times and see how long it takes 
     sw = CStopwatch(); 
     sw.Start(); 
     for (int i=0;i<1000;i++) 
     { 
      if (m_queue.size() == 123456) 
      { 
       dummy++; 
      } 
     } 
     std::cout << m_queue.size() << " items left. time: " << sw.GetElapsedTimeInSeconds() << std::endl; 
    } 
    return dummy; 


} 

Trường hợp CStopwatch là một lớp sử dụng clock_gettime(CLOCK_REALTIME, ..). Kết quả là:

21000 items left. time: 1.08725 
20000 items left. time: 0.968897 
19000 items left. time: 0.818259 
18000 items left. time: 0.71495 
17000 items left. time: 0.583725 
16000 items left. time: 0.497451 
15000 items left. time: 0.422712 
14000 items left. time: 0.352949 
13000 items left. time: 0.30133 
12000 items left. time: 0.227588 
11000 items left. time: 0.178617 
10000 items left. time: 0.124512 
9000 items left. time: 0.0893425 
8000 items left. time: 0.0639174 
7000 items left. time: 0.0476441 
6000 items left. time: 0.033177 
5000 items left. time: 0.0276136 
4000 items left. time: 0.022112 
3000 items left. time: 0.0163013 
2000 items left. time: 0.0101932 
1000 items left. time: 0.00506138 

Điều này có vẻ như mâu thuẫn với http://www.cplusplus.com/reference/stl/queue/size/:

phức tạp: Constant.

Vấn đề còn tệ hơn nếu cấu trúc lớn hơn. Tôi đang sử dụng GCC 4.3.2.

Bạn có thể giải thích điều này không? Có cách nào để giải quyết điều này bằng cách sử dụng danh sách?

(. Xin lưu ý rằng tôi cần phải sử dụng danh sách như container nằm bên dưới của hàng đợi bởi vì tôi cần liên tục phức tạp chèn thời gian)

Answer 1

queue là bộ chứa bộ điều hợp, vì vậy bạn phải hiểu rằng mô tả phức tạp chỉ có thể tham chiếu đến công việc.

Ví dụ: see this reference: size() gọi hàm chứa bên dưới là hàm size(). Đối với một số list, điều này có độ phức tạp O (n) trong C++ 98/03 và O (1) trong C++ 11.

Answer 2

Bạn của bạn queue sử dụng một container list, thay vì mặc định deque:

typedef std::queue<QueueElementType, std::list<QueueElementType> > QueueType; 

Bạn không nên ngạc nhiên khi kích thước mất O (n), vì đó là việc triển khai hoàn toàn hợp lệ gói tiền mặt list trước C++ 11. Phiên bản trước của tiêu chuẩn không đảm bảo tính phức tạp của chức năng thành viên size cho danh sách.

Nếu bạn thay đổi mã của bạn để:

typedef std::queue<QueueElementType, std::deque<QueueElementType> > QueueType; 

Bạn sẽ thấy hành vi mà bạn muốn (O (1) kích thước phức tạp).

Answer 3

Thêm vào câu trả lời của Michael: Bạn đang sử dụng std::list làm vùng chứa hàng đợi của mình, do đó, phương thức size() phụ thuộc vào tiêu chuẩn của bạn :: danh sách kích thước. Nếu bạn tìm kiếm trên cùng một trang web, bạn tìm thấy http://www.cplusplus.com/reference/stl/list/size/ và sự phức tạp là không đổi trên một số triển khai và tuyến tính trên những người khác. Nếu bạn cần chèn và kích thước liên tục, thì bạn cần cấu trúc dữ liệu khác hoặc thực hiện tốt hơn std::list.