Iterate liste triée et compte des nombres distincts

Question

Je veux parcourir une liste triée pour obtenir le nombre de nombres distincts.

S'il vous plaît trouver ma tentative de mettre en œuvre ci-dessous. La taille de la liste est k*k. Lorsque la liste est triée, je compare les éléments consécutifs pour identifier les doublons.

int count_distinct(list<int> v) 
{ 
    int num = k*k; 
    std::list<int>::iterator it; 
    it = v.begin(); 
    for (int a=0; a<k*k-1; a++) 
    { 
     if(*it == *it+1) 
      num--; 
     it++; 
    } 

    return num; 
} 

Je ne peux pas changer la liste, std::list::unique() est pas une option. Faire une copie de la liste ou des éléments uniques est trop lent pour que cela soit utile pour moi.

Answer 1

Votre code a des problèmes suivants:

1. Vous passez conteneur en valeur à la fonction. Vous devriez le transmettre par référence const pour minimiser la vitesse et la perte de mémoire.
2. Votre condition *it == *it+1 est toujours fausse (vous comparez n et n+1). Probablement que vous vouliez écrire *it == *(it+1) mais std::list a bidirectional iterators et vous ne pouvez pas +1 eux.

Le code devrait ressembler à ceci:

size_t count_distinct(const std::list<int>& l) { 
    if (l.empty()) return 0; 

    size_t distinct = l.size(); 
    auto prev = l.begin(); 

    for (auto cur = std::next(prev); cur != l.end(); ++cur, ++prev) { 
     if (*cur == *prev) 
      --distinct; 
    } 

    return distinct; 
} 

Ou vous pouvez écrire votre version modifiée de std::unique algorithme:

template<class ForwardIt> 
size_t unique_cnt(ForwardIt first, ForwardIt last) { 
    if (first == last) 
     return 0; 

    size_t distinct = 1;  
    ForwardIt prev = first; 

    while (++first != last) { 
     if (!(*prev == *first)) { 
      ++distinct; 
     } 
     prev = first; 
    } 
    return distinct; 
} 

Et puis utilisez simplement

size_t distinct = unique_cnt(l.begin(), l.end());   

Il y a aussi un std::unique_copy + approche de l'itérateur personnalisé, mais il ne semble pas assez élégant.

Answer 2

Comment utiliser std::set pour saisir des éléments uniques?

size_t count_distinct(const list<int>& v) 
{  
    std::set<int> temp (v.begin(), v.end()); 

    return temp.size(); 
} 

Answer 3

En supposant que vous voulez trouver le nombre d'entiers uniques dans cette liste et la liste ne sont pas triées, vous pouvez utiliser un ensemble temporaire ou unordered_set comme ceci:

size_t count_distinct(list<int> v) 
{ 
    std::unordered_set<int> distinct; 
    for(auto &x : v) 
    { 
     distinct.insert(x); 
    } 
    return distinct.size(); 
} 

Answer 4

Voici une solution pour extraire un conteneur de toutes les valeurs uniques (puisque vous avez dit que vous vouliez les utiliser par la suite):

une méthode pour nombre valeurs uniques:

template < typename T > 
size_t count_unique(const std::list<T> & input) 
{ 
    std::set<T> unique(input.begin(), input.end()); 
    return unique.size(); 
} 

Une méthode pour extrait une liste de valeurs uniques:

template < typename T > 
void unique(const std::list<T> & input, std::list<T> & output) 
{ 
    std::set<T> unique(input.begin(), input.end()); 
    std::copy(unique.begin(), unique.end(), std::back_inserter(output)); 
} 

Un exemple de programme:

int main(int argc, char** argv) 
{ 
    std::list<int> list = { 1, 3, 4, 10, 3, 1, 6, 7 }; 
    std::list<int> out; 

    std::cout << count_unique(list) << std::endl; 

    unique(list, out); 
    for (auto & x : out) 
     std::cout << x << std::endl; 
} 

Answer 5

Vous pouvez utiliser std::list<int>::unique() pour obtenir tous les éléments distincts v et size() compter leur. v doit être trié. Vérifiez si v est trié en utilisant la fonction std :: is_sorted(). Si non, triez-le. Cela signifie également que count_distinct ne fonctionne pas pour les objets de liste const.

size_t count_distinct(list<int>& v) 
{ 
    if (!is_sorted(v.begin(), v.end())) 
    { 
     v.sort(); 
    } 
    v.unique(); 
    return v.size(); 
} 

Answer 6

Pour les données triées, vous n'obtiendrez probablement pas beaucoup plus efficace que l'approche directe que vous avez tenté d'implémenter.

Je préférerais avoir quelque chose le long des lignes de cela, que je trouve plus intuitive compter vers le haut au lieu de descendre:

std::size_t count_unique_sorted(std::list<int> const& l) { 
    if (l.empty()) return 0; 
    std::size_t count = 1; 
    auto previous_value = l.front(); 
    // TODO: hope that the compiler fixes that redundant first comparison... 
    for (auto next_value : l) { 
     if (next_value != previous_value) { 
      // the value changed! increment count and update previous_value 
      ++count; 
      previous_value = next_value; 
     } 
    } 
    return count; 
} 

Vous pouvez faire l'algorithme std::unique_copy() à compter au lieu de copier, en fournissant un OutputIterator personnalisé. Mais cela aura peu d'avantages sur le plan de la performance par rapport à l'approche présentée ci-dessus. Peut-être que cela vaudra la peine d'être revisité, quand le parallel implementations des algorithmes de C++ 17 deviendra disponible.

Voici un exemple:

template <typename T> 
struct counter : public std::iterator<std::output_iterator_tag, T> { 
    explicit counter(std::size_t& count) : count(count) {} 
    counter& operator*() { return *this; } 
    counter& operator++() { return *this; } 
    void operator=(T const&) { ++count; } 
private: 
    std::size_t& count; 
}; 

std::size_t count_unique_sorted2(std::list<int> const& l) { 
    std::size_t count = 0; 
    std::unique_copy(l.begin(), l.end(), counter<int>(count)); 
    return count; 
} 

Notez que dans les deux cas, vous voulez passer la liste comme référence const et non comme une copie dans la fonction.

Si vous pensez que cela doit encore ralentir, n'hésitez pas à explorer les joies de la parallélisation. Les avantages de cela dépendront probablement du volume et de la distribution des données. Vous devriez donc commencer un profilage systématique d'ici là.

À moins d'avoir à réordonner les valeurs, pensez à vider vos données dans un std::vector<int> en premier lieu. Avoir un accès aléatoire itérateurs simplifie les choses et avoir une meilleure localité peut également accélérer les choses ...