Est-ce que ce vecteur est survenu avant

Question

J'ai beaucoup de vecteurs (de l'ordre de 10^4, et même plus!) Et j'obtiendrai plus de vecteurs en entrée du flux. Ainsi, par exemple, je

• v1 = 1 0 4 1 1
• v2 = 1 1 2 5 3 6 2
• v3 = 0 1 1 5 0

je 10^4 ces vecteurs Maintenant, je reçois en entrée un vecteur v4 = 0 1 1 5 0, et je veux vérifiez s'il est apparu avant ou non, comment me suggérez-vous de faire cela?

Je vais énumérer les techniques que j'ai pensé, et les erreurs qui les accompagnent:

• Pour utiliser std::map ou std::set pour la même. Mais, std::map std::set ne supporte pas le vecteur comme argument.
• Pour convertir chaque nombre entier en vecteur en type de chaîne, ajoutez-les dans l'ordre et stockez la chaîne dans la carte. Erreur: Le cas de v5 = 11 1 1 1 et v6 = 1 1 1 1 1 sera affiché comme identique.
• Similaire à ci-dessus, juste pour ajouter un délimiteur après chaque entier. Erreur: Trop fastidieux pour coder?

Je voulais savoir si vous pouvez penser à une méthode pour y parvenir?

Modifier: pour 10^4, c'est réalisable. Ma nouvelle tâche m'oblige à stocker jusqu'à 10^9. Personnellement, je ne pense pas que STL a autant d'espace, ils ont jeté SIGABRT erreur. Connaissez-vous une autre méthode de hachage efficace qui peut fonctionner dans ce cas?

Answer 1

La méthode simple de faire cela est stockez vos vecteurs dans un autre vecteur, et maintenez un ordre de ceux-ci avec la famille de fonctions std :: sort(), en utilisant std :: lexigraphical_compare comme prédicat de tri. Cela permettrait binaire de recherche la liste O (log (n)) amorti le temps, à la coûteuse d'une opération de tri semi-coûteuse, qui peut probablement être réduit en jouant des jeux avec heapifying ou le partitionnement de votre liste-des-vecteurs comme vous le chargez. Cependant, plus efficace que ceci, est de stocker vos vecteurs sous forme de trie (https://en.wikipedia.org/wiki/Trie), où chaque chemin du trie stocke une séquence unique à partir de vos vecteurs. En fonction de la variance de vos données, cela peut être beaucoup plus efficace en termes d'espace, et à la fois l'addition et la recherche sont des opérations O (log (n)).

Prenez mes conseils avec un grain de sel, cependant, 10^4 éléments est en fait un tout petit nombre. Mon expérience est que les différences dans l'efficacité du tri & algorithmes à la recherche commencent vraiment qu'à se montrer sur le matériel moderne quand vous êtes dans la gamme 10^6-10^7 pour votre ensemble de données. Au-dessous de cette échelle, l'algorithme le plus simple et le plus convivial en termes de cache l'emporte souvent. Une autre alternative si vous ne faites que de la vitesse brute, et que votre liste de vecteurs à scanner est bien connue et statique, est d'utiliser une machine à états finis pour accepter/rejeter votre entrée. Des outils comme Ragel peuvent faire un travail rapide de ces problèmes.

Answer 2

Cette approche est très begineer mais je suis en train d'utiliser ce que je l'ai appris de pliage et stl

Explication de l'approche:

1.Created une liste de vecteur (à des fins d'entrée peut être de toute façon environ)

2.Kept un vecteur principal v qui permet de stocker le vecteur principal plié

3.used stl comprend de garder le contrôle avant de plier si la séquence est présente

ensemble d'entrées

std::vector<int> x ={1,2,3}; 
std::vector<int> y ={7,8,9}; 
std::vector<int> z ={1,2,3}; 
std::vector<int> a ={1,2,3}; 
std::vector<int> v5 = {11,1,1,1}; //as mentioned in question 
std::vector<int> v6 = {1,1,1,1}; //as mentioned in question 

approche

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <list> 

template <typename T> 
void Concat(std::vector<T>& v, const std::vector<T>& v2) 
{ 
    v.insert(v.end(), v2.begin(), v2.end()); 
} 

template <typename T> 
void Concat(std::vector<T>& v, const T& value) 
{ 
    v.push_back(value); 
} 

template<typename T, typename... Args> 
void push_back_vec(std::vector<T>& v, Args&&... args) 
{ 
    (Concat(v, args), ...); 
} 
int main() 
{ 
    std::vector<int> v; 
    std::list<std::vector<int> > m ; 
    std::vector<int> x ={1,2,3}; 
    std::vector<int> y ={7,8,9}; 
    std::vector<int> z ={1,2,3}; 
    std::vector<int> a ={1,2,3}; 
    std::vector<int> v5 = {11,1,1,1}; 
    std::vector<int> v6 = {1,1,1,1}; 
    m.push_back(x); 
    m.push_back(y); 
    m.push_back(z); 
    m.push_back(a); 
    m.push_back(v5); 
    m.push_back(v6); 

    for (std::list<std::vector<int> >::iterator it1 = m.begin(); it1 != m.end(); ++it1) 
    { 


     if (std::includes(v.begin(), v.end(), (*it1).begin(), (*it1).end())) 
     { 
      std::cout<<"Already present"<<std::endl; 
      } 
     else 
      { 
      push_back_vec(v,(*it1)); 

      } 
    } 

    for (int i : v) std::cout << i << ' '; 

} 

Sortie

Already present 
Already present 
1 2 3 7 8 9 11 1 1 1 1 1 1 1 Program ended with exit code: 0 

Je sais qu'il peut y avoir beaucoup d'amélioration et il peut échouer dans certains cas, d'angle.Ceci est juste un de la tentative Sentez-vous libre de critiquer et me aider à améliorer

Answer 3

Si vous définissez une commande complète sur vos vecteurs, vous pouvez faire une recherche raisonnablement efficace de deux façons:

• magasin les vecteurs existants dans std::set ou std::map. Ce sont des classes de conteneur ordonnées, avec des méthodes d'adhésion/recherche raisonnablement efficaces.
• magasin les vecteurs existants dans l'ordre de tri dans un std::vector et utiliser std::binary_search

Le choix par défaut pour commander vos vecteurs est l'ordre lexicographique. Ceci est fourni par le operator< fourni par l'implémentation std::vector; ce qu'il fait est quelque chose comme ceci:

bool operator<(const std::vector<int> &a, const std::vector<int> &b) { 
    auto a_it = a.cbegin(); 
    auto b_it = b.cbegin(); 
    while(a_it < a.cend() && b_it < b.cend()) { 
    if(*a_it < *b_it) { 
     return true; 
    } 
    if(*b_it < *a_it) { 
     return false; 
    } 
    ++a_it; 
    ++b_it; 
    } 
    if(a_it == a.cend() && b_it < b.cend()) { 
    return true; 
    } 
    return false; 
} 

Notez que ce code peut quitter tôt: si les premiers éléments des vecteurs d'entrée sont différents, il n'a pas besoin de vérifier plus loin. Seulement s'il y a un long préfixe commun (ou si les vecteurs sont réellement identiques) a-t-il besoin de vérifier tous les éléments.

---

Comme mentionné dans les commentaires, vous pouvez également résoudre ce problème avec:

• une carte de hachage (std::unordered_map) - vous oblige à définir un hachage pour votre std::vector<int>
• une structure arborescente - qui AFAIK n'a pas une implémentation std::, vous devez suivre une bibliothèque ou rouler votre propre