Effacement d'un élément vectoriel C++ par rapport à la création d'un nouveau vecteur

Question

Je travaille avec un vecteur d'éléments qui doivent être sélectionnés au hasard et effectivement supprimés jusqu'à ce qu'une condition soit remplie, ou jusqu'à ce que tous les éléments aient été sélectionnés. Cependant, ils ne seront pas réellement supprimés avant un certain temps dans l'exécution du code, donc j'ai besoin de maintenir une liste d'éléments valides et disponibles. Je peux effacer des éléments de ce second vecteur, ou je peux le recréer à chaque fois. S'il vous plaît voir une version minimale de mon code ci-dessous montrant l'exemple de l'endroit où le vecteur est créé à chaque fois dans une boucle while:

Random mRandom; // Pseudo-random number generator 
    std::vector< Element* > mElements; 
    for(unsigned index = 0; index < ARBITRARY_VALUE; index++) 
     mElements.push_back(new Element()); 

    std::vector<bool> removedElements; 
    bool condition = true; 

    while(condition == true) { 
     std::vector<unsigned> availableIndices; 

     for(unsigned index = 0; index < mElements.size(); index++) { 
     if(removedElements[ index ] == false) 
      availableIndices.push_back(index); 
     } 

     if(availableIndices.size() > 0) { 
     unsigned maximum = availableIndices.size() - 1; 
     unsigned randomIndex = mRandom.GetUniformInt(maximum); // Zero to max 
     removedElements[ availableIndices[ randomIndex ] ] = true; 
     Element* element = mElements[ availableIndices[ randomIndex ] ]; 
     condition = element->DoStuff(); // May change condition and exit while 
     } else 
     break; 
    } 

Il est clair que l'effacement d'un élément au milieu d'un vecteur nécessite le système sous-jacent à itérer à travers les éléments restants et les 'déplacer' vers leur nouvelle position valide. Évidemment cela signifie moins d'itérations si les éléments effacés sont proches de la fin d'un vecteur.

J'ai lu quelques articles concernant les coûts associés à l'effacement des éléments vectoriels, mais je n'ai rien vu qui réponde directement à ma question. Est-ce que le processus de «déplacement» des éléments suite à un effacement introduit des frais généraux qui pourraient rendre moins cher l'itération de tous les éléments à chaque fois en créant un nouveau vecteur qui pointe vers les éléments valides? Comme dans mon exemple de code ci-dessus.

Cheers, Phil

Answer 1

Je ne peux pas commenter sur la meilleure façon de résoudre votre problème parce que je ne suis pas encore sûr de ce que l'exigence réelle de la fonction ou de l'algorithme est (c.-à-éléments doivent conserver l'ordre? Est-éléments non disponibles nouveau disponibles Si oui, sera la commande affaire alors et ainsi de suite)

Cependant, en ce qui concerne la dernière question:?

le processus de « déplacement » des éléments suivants un effacement introduire des frais généraux qui pourraient faire il est moins cher d'itérer à travers tous les e éléments à chaque fois en créant un nouveau vecteur qui pointe vers les valides?

Cela dépend complètement de ce qui est impliqué dans le déplacement d'un élément. Si c'est un pointeur, comme ci-dessus, vous pouvez déplacer beaucoup d'éléments avant même d'approcher le coût d'allocation de la mémoire dans un nouveau vecteur. Et par «beaucoup», je pense à des centaines, voire des milliers.

Dans le code ci-dessus, il semble que le vecteur de disponibilité soit redondant. Un pointeur Element est disponible s'il est dans le vecteur availableIndicies.

Si je comprends l'intention correctement, je pense que je pourrais factoriser le long des lignes suivantes:

#include <vector> 
#include <random> 

struct Element 
{ 
    bool doStuff(); 
}; 


struct ElementAvailability 
{ 
    ElementAvailability(std::vector<Element*> const& storage) 
    : storage_(storage) 
    {} 

    void resync() 
    { 
    // will requre an allocation at most once if storage_ does not grow 
    available_ = storage_; 
    } 

    std::size_t availableCount() const { 
    return available_.size(); 
    } 

    Element* removeAvailable(std::size_t index) { 
    auto pe = available_[index]; 
    available_.erase(std::begin(available_) + index); 
    return pe; 
    } 

    void makeUnavailable(std::size_t available_i) 
    { 
    available_.erase(std::next(std::begin(available_), available_i)); 
    } 

private: 
    std::vector<Element*> const& storage_; 
    std::vector<Element*> available_; 
}; 

// I have used a std random engine because I don't know your library 
auto eng = std::default_random_engine(std::random_device()()); 

void test(std::vector<Element*>const& elems) 
{ 
    auto available = ElementAvailability(elems); 

    bool condition = true; 
    auto getCount =[&condition, &available]() -> std::size_t 
    { 
    if (condition) { 
     available.resync(); 
     auto count = available.availableCount(); 
     return count; 
    } 
    else { 
     return 0; 
    } 
    }; 

    while (auto count = getCount()) { 
    auto range = std::uniform_int_distribution<std::size_t>(0, count - 1); 
    auto index = range(eng); 
    auto candidate = available.removeAvailable(index); 
    condition = candidate->doStuff(); 
    } 
} 

Answer 2

Le problème de l'élimination aléatoire des éléments présentés par vous me semble solvable que dans O(n^2) temps et O(n) complexité de l'espace . Parce que vous devez passer tous les éléments une fois et à chaque passage, vous devez trouver un index aléatoire dans une séquence d'éléments encore existants et maintenir cette séquence. Il pourrait y avoir quelques approches avec différentes primitives algorithmiques. Ci-dessous, je présente ma solution qui archive cet objectif tout en faisant cela dans un fonctionnement CPU/mémoire convivial.

void runRandomTasks() { 
    Random mRandom; // Pseudo-random number generator 
    std::vector<Element*> mElements; 
    for (unsigned index = 0; index < ARBITRARY_VALUE; ++index) { 
    mElements.push_back(new Element); 
    } 
    size_t current_size = mElements.size(); 
    if (!current_size) 
    return; 
    std::vector<Element*> current_elements(current_size, nullptr); 
    for (unsigned index = 0; index < current_size; ++index) { 
    current_elements[index] = mElements[index]; 
    } 
    Element** last_ptr = &current_elements[0] + current_size - 1; 

    bool condition = true; 

    while (condition && current_size) { 
    unsigned random_size = mRandom.GetUniformInt(current_size - 1) + 1; // Zero to max 
    Element** ptr = last_ptr; 
    while (true) { 
     random_size -= (bool)(*ptr); 
     if (random_size) { 
     --ptr; 
     } else { 
     break; 
     } 
    } 

    condition = (*ptr)->DoStuff(); // May change condition and exit while 
    *ptr = nullptr; 
    --current_size; 
    } 
} 

En ce qui concerne votre question d'effacement de l'élément vectoriel, vous pouvez trouver dans ma solution qu'il ya une boucle de trouver un indice aléatoire, qui équivaut à l'effacement de l'élément dans un vecteur de complexité de temps, mais avec une plus petite constante depuis le décalage de l'élément est omis, la valeur de l'élément est vérifiée à 0 ou non.Faire n'importe quelle allocation de mémoire dans une boucle est toujours coûteux, alors évitez cela.