C++ kiểm tra có bao nhiêu yếu tố tương tự trong một hàng đang ở trong một vector

Question

Tôi có một vector lớn với 24.000 các yếu tố như:

(1,1,1,1,3,3,3,3,3,3,5,5,5,...etc) 

và tôi muốn kiểm tra có bao nhiêu cùng yếu tố này trong một hàng như: 4 -6-3..etc Tôi sử dụng mã này:

static int counter=1; 
vector<int>numbers; 

for(int n=0;n<numbers.size()-1;n++) 
{ 
    if(numbers[n]==numbers[n+1]) 
    { 
    counter++; 
    } 
    else if(numbers[n]!=numbers[n+1]) 
    { 
    cout<<counter<<endl; 
    counter=1; 
    } 
} 

là có bất kỳ thuật toán nào tương tự nhanh hơn;

Answer 1

@rhalbersma về cơ bản đã cho bạn câu trả lời đúng. Là phụ lục, trong trường hợp bạn muốn viết lại thuật toán của mình theo cách tiêu chuẩn hơn:

#include <algorithm> 
#include <vector> 
#include <iterator> 
#include <functional> 
#include <iostream> 

int main() 
{ 
    std::vector<int> v { 1, 1, 2, 3, 3, 5, 5, 5 }; // or whatever... 

    auto i = begin(v); 
    while (i != end(v)) 
    { 
     auto j = adjacent_find(i, end(v), std::not_equal_to<int>()); 
     if (j == end(v)) { std::cout << distance(i, j); break; } 
     std::cout << distance(i, j) + 1 << std::endl; 
     i = next(j); 
    } 
} 

Đây là live example.

Ngoài ra, khi các vector được sắp xếp, điều này sẽ cung cấp cho bạn tốt hơn nhất trường hợp phức tạp:

#include <algorithm> 
#include <vector> 
#include <iterator> 
#include <iostream> 

int main() 
{ 
    std::vector<int> v { 1, 1, 2, 3, 3, 5, 5, 5 }; // must be sorted... 

    auto i = begin(v); 
    while (i != end(v)) 
    { 
     auto ub = upper_bound(i, end(v), *i); 
     std::cout << distance(i, ub) << std::endl; 
     i = ub; 
    } 
} 

Đây là một live example.

Answer 2

Thuật toán của bạn là O(N) trong thời gian và điều đó có vẻ khá tối ưu với tôi vì bạn phải truy cập từng yếu tố duy nhất để so sánh. Bạn có thể vẫn cạo một vài chu kỳ ở đây và ở đó, ví dụ: bằng cách loại bỏ điều kiện bên trong else() hoặc bằng cách bật một số cài đặt trình biên dịch, nhưng về mặt thuật toán bạn đang ở trạng thái tốt.

Nếu đầu vào đã là được sắp xếp, bạn có thể thực hiện chuỗi tìm kiếm nhị phân. Điều đó sẽ mang lại cho bạn sự phức tạp trường hợp xấu nhất O(N lg N) nhưng trường hợp trung bình có thể thấp hơn đáng kể tùy thuộc vào độ dài trung bình của chuỗi phần tử bằng nhau.

BTW, như @AndyProwl hiển thị trong câu trả lời của mình: Thư viện chuẩn là thực sự tuyệt vời để làm ngay cả loại công cụ thuật toán cấp thấp này. Các thuật toán adjacent_find và upper_bound có các tài liệu phức tạp và các quy ước lặp sẽ bảo vệ bạn đối với các trường hợp cạnh có trong mã của riêng bạn. Một khi bạn học từ vựng này, bạn có thể dễ dàng sử dụng chúng trong các thói quen của riêng bạn (và khi Ranges đến C++, hy vọng nó cũng sẽ dễ dàng hơn để soạn chúng).

Answer 3

Có một số tối ưu hóa litle có thể cung cấp cho bạn một vài ms:

int size = numbers.size()-1; 
static int counter=1; 
static int *num1 = &numbers[0]; 
static int *num2 = &numbers[1]; 
for(int n=0;n<size;n++) 
{ 
    if(*num1==*num2) counter++; 
    else 
    { 
    cout << counter << "\n"; 
    counter=1; 
    } 
    num1++; 
    num2++; 
} 
cout<<counter<<endl; //Caution, this line is missing in your code!! 

về cơ bản: Truy cập

• Tránh để vector bởi id: số [n] có nghĩa rằng máy tính phải nhân n * sizeof (int) và thêm kết quả này vào các số. Sử dụng con trỏ và tăng nó nhanh hơn, điều đó có nghĩa là chỉ cần thêm.