C++ verificare quante stessi elementi in fila sono in un vettore

Question

Ho un grosso vettore con 24.000 elementi come:

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

e voglio verificare quanti stessi elementi sono in fila come: 4 -6-3..etc io uso questo codice:

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

c'è qualche algoritmo che fa lo stesso più veloce;

Answer 1

@rhalbersma fondamentalmente ti ha dato la risposta giusta. Come un addendum, nel caso in cui si desidera riscrivere l'algoritmo in modo più standard:

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

Ecco un live example.

Inoltre, quando il vettore è ordinato, questo vi darà una migliore migliore dei casi la complessità:

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

Ecco un live example.

Answer 2

Il tuo algoritmo è O(N) nel tempo, e questo mi sembra piuttosto ottimale dal momento che devi visitare ogni elemento unico per il confronto. Potresti ancora radere alcuni cicli qua e là, ad es. per eliminando la condizione all'interno dello else() o attivando alcune impostazioni del compilatore, ma algoritmicamente si è in buona forma.

Se l'ingresso fosse già ordinato, si potrebbe fare una serie di ricerche binari. Questo ti darebbe la complessità nel caso peggiore di O(N lg N) ma il caso medio potrebbe essere notevolmente inferiore a seconda della lunghezza media delle sequenze di elementi uguali.

BTW, come @AndyProwl mostra nella sua risposta: la libreria standard è davvero impressionante per fare anche questo tipo di cose algoritmiche di basso livello. Gli algoritmi adjacent_find e upper_bound hanno complessità ben documentate e le convenzioni iteratore ti proteggeranno per casi limite presenti nel tuo codice. Una volta imparato questo vocabolario, puoi facilmente usarli nelle tue routine (e quando gli intervalli arrivano al C++, speriamo che sia anche più facile comporli).

Answer 3

V'è una certa ottimizzazione litle che possono dare alcuni 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: accesso

• Evitare al vettore da ID: numeri [n] significa che il computer deve moltiplicare n * sizeof (int) e aggiungi questo risultato ai numeri. È più veloce usare il puntatore e incrementarlo, il che significa solo un add.