C++ sprawdzić ile same elementy w jednym rzędzie są w wektorze

Question

Mam wielki wektor z 24.000 elementów, takich jak:

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

i chcę, aby sprawdzić, ile same elementy są w jednym rzędzie tak: 4 -6-3..etc używam tego kodu:

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; 
    } 
} 

jest jakiś algorytm, który robi to samo szybciej;

Answer 1

@rhalbersma w zasadzie dała ci właściwą odpowiedź. Jako dodatek, w przypadku, gdy chcesz przerobić swój algorytm w bardziej standardowy sposób:

#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); 
    } 
} 

Oto live example.

Ponadto, gdy wektor jest posortowana, to daje lepsze najlepiej przypadek Złożoność:

#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; 
    } 
} 

Oto live example.

Answer 2

Twój algorytm ma wartość O(N) i wydaje mi się to optymalne, ponieważ musisz odwiedzić każdy unikalny element w celu porównania. Nadal możesz zgasić kilka cykli tu i tam, np. przez eliminując warunek wewnątrz else() lub włączając niektóre ustawienia kompilatora, ale algorytmicznie jesteś w dobrej formie.

Jeśli wejście było już posortowane, można zrobić serię wyszukiwań binarnych. To dałoby ci najgorszy przypadek, ale średni przypadek może być znacznie mniejszy w zależności od średniej długości równych sekwencji elementów.

BTW, jak @AndyProwl pokazuje w swojej odpowiedzi: Biblioteka standardowa to naprawdę świetna, aby robić nawet tego rodzaju algorytmy o niskim poziomie. Algorytmy adjacent_find i mają dobrze udokumentowaną złożoność, a konwencje iteracyjne chronią Cię przed przypadkami skrajnymi, które występują w twoim własnym kodzie. Gdy nauczysz się tego słownictwa, możesz z łatwością używać ich w swoich własnych procedurach (i gdy zakresy przychodzą do C++, miejmy nadzieję, że łatwiej je skomponować).

Answer 3

Istnieją pewne litle optymalizacji, które mogą dać ci kilka 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!! 

basicaly:

• uniemożliwić dostęp do wektora przez ID: numery [n] oznacza, że ​​komputer musi pomnożyć n * sizeof (int) i dodaj ten wynik do liczb. Szybsze jest używanie wskaźnika i zwiększanie go, co oznacza tylko dodanie.