Lire à partir du fichier et ajouter des mots à l'arbre efficacement

Question

J'ai un fichier en entrée à partir des arguments de commande. Je lis chaque ligne de cette façon:

vector<string> filewords; 
    string line; 
    while(getline(cin, line){ 
     filewords.push_back(line); 
    } 

Je ne l'ai pas trouvé d'autre moyen d'obtenir les chaînes du fichier, si je pouvais obtenir tout le contenu dans un méga-chaîne qui serait génial, mais je havre de paix « t trouvé comment

ajouter les mots à cette façon Trie:

for(const auto &word : *filewords){ 
     if(word.length() >= 3 && word.length() <= 17){ 
     root->addString(word.c_str()); 
     } 
    } 

Je dois vérifier que chaque ligne a une certaine longueur avant de l'ajouter à la structure arborescente. addString est:

void Node::addString(const char* word) 
{ 
    if(!mChildren[*word - 'a']) mChildren[*word - 'a'] = new Node(word); 
    if(word[1]) mChildren[*word - 'a']->addString(word + 1); 
    else mChildren[*word - 'a']->setMarker(true); 
} 

les enfants sont classés par ordre alphabétique si 'a' est en position 0 et ainsi de suite.

Node est une classe avec le constructeur suivant:

Node::Node(const char* a) 
{ 
    mContent = *a; 
    mChildren.resize(26); 
} 

Il y aura max 26 enfants (26 lettres dans l'alphabet)

Je ne sais pas si les petites optimisations que j'ai fait (Faire mChildren de la taille 26, ajouter chaque ligne à un vecteur et ensuite itérer à travers ce vecteur ...) en valent vraiment la peine ou s'il y a un meilleur moyen.

Je suis supposé faire de cette partie du programme ~ 80ms, et maintenant il faut ~ 120ms avec un fichier de ~ 180.000 mots.

Des idées sur comment optimiser/réduire la complexité/améliorer le code? Merci!

Answer 1

Votre question ne mentionne pas que vous avez un autre usage pour ce vecteur, quel qu'il soit. Lire ~ 180 000 lignes dans un vecteur d'abord, puis itérer sur le vecteur par la suite, va perdre beaucoup de temps et de mémoire, sans valeur apparente apparente.

Vous devez simplement insérer vos mots dans le fichier, dans le cadre de leur lecture.

string word; 

while(getline(cin, word){ 
    if(word.length() >= 3 && word.length() <= 17){ 
    root->addString(word.c_str()); 
    } 
}