Hiệu suất của phương thức STL bitset :: count() là gì?

Question

Tôi đã tìm kiếm xung quanh và không thể tìm thấy thông số thời gian hiệu suất cho bitset :: count(). Có ai biết nó là gì (O (n) hoặc tốt hơn) và nơi để tìm thấy nó?

EDIT Bởi STL tôi chỉ tham chiếu đến Thư viện mẫu chuẩn.

Answer 1

Tôi đọc tệp này (C: \ cygwin \ lib \ gcc \ i686-pc-cygwin \ 3.4.4 \ include \ C++ \ bitset) trên máy tính của tôi.
Xem những

/// Returns the number of bits which are set. 
size_t 
count() const { return this->_M_do_count(); }  

size_t 
_M_do_count() const 
{ 
    size_t __result = 0; 
    for (size_t __i = 0; __i < _Nw; __i++) 
    __result += __builtin_popcountl(_M_w[__i]); 
    return __result; 
} 

BTW, đây là nơi _Nw được quy định:

template<size_t _Nw> 
    struct _Base_bitset 

Vì vậy nó là O (n) trong việc thực hiện gcc. Chúng tôi kết luận đặc điểm kỹ thuật không yêu cầu nó tốt hơn O (n). Và không ai trong tâm trí của họ sẽ thực hiện nó theo cách tồi tệ hơn thế. Sau đó chúng ta có thể giả định rằng nó là tồi tệ nhất O (n). Có thể tốt hơn nhưng bạn không bao giờ có thể tin tưởng vào điều đó.

Answer 2

"thực hiện tham chiếu của SGI chạy trong thời gian tuyến tính đối với số byte cần thiết để lưu trữ các bit với. Nó làm điều này bằng cách tạo ra một mảng tĩnh 256 số nguyên. Giá trị bảo quản ở chỉ số thứ i trong mảng là số bit được đặt trong giá trị i. "

http://www.cplusplus.com/forum/general/12486/

Answer 3

Tôi không chắc chắn bạn sẽ tìm thấy một đặc điểm kỹ thuật cho rằng, kể từ khi STL không thường đòi hỏi một mức độ nhất định về hiệu suất. Tôi đã nhìn thấy gợi ý rằng nó "nhanh", khoảng 1 chu kỳ mỗi bit trong kích thước của bộ. Tất nhiên bạn có thể đọc mã thực hiện cụ thể của bạn để tìm hiểu những gì mong đợi.

Answer 4

Tôi không thể chắc chắn những gì bạn thực sự có nghĩa là "STL" ở đây, do lạm dụng phổ biến của thuật ngữ trong cộng đồng C++.

• C++ Standard (2003) làm cho không có nhiệm vụ để thực hiện các std::bitset::count() (hoặc, trên thực tế, bất kỳ thành viên của std::bitset như xa như tôi có thể nhìn thấy).

• Tôi không thể tìm thấy bất kỳ tham chiếu nào đề xuất ủy quyền cho hiệu suất của STL's bitset::count().

Tôi nghĩ rằng bất kỳ việc triển khai nào sẽ cung cấp điều này theo thời gian liên tục (hoặc ở thời điểm tồi tệ nhất). Tuy nhiên, đây chỉ là một cảm giác. Kiểm tra của bạn để tìm hiểu những gì bạn sẽ thực sự nhận được.