Bonsoir, j'aimerais savoir s'il existe un moyen en C++ de parcourir rapidement un tableau dynamique car je suis sur un projet consistant à lire des fichiers OSM. Pour faire simple, ces derniers contiennent une liste de points appelés "node" définis par des coordonnées GPS et des identifiants ainsi qu'une liste de lignes brisées appelées "way" représentant des contours de bâtiments ou bien des routes ou voies ferrées. Dans chaque way on trouve notamment une liste d'identifiants de noeuds permettant de reconstituer le tracé des routes ou la forme des bâtiments.

<way id="4352991" version="31" timestamp="2018-01-15T01:42:15Z" changeset="55447685" uid="2775946" user="M GM">
    <nd ref="3912196341"/>
    <nd ref="4299002963"/>
    <nd ref="2874430837"/>
    <nd ref="3911143253"/>
    ...
</way>

Cette route est constituée de 4 noeuds avec chacun sa référence.

<node id="9119111985" lat="43.2737530" lon="5.4003135" version="1" timestamp="2021-09-24T05:42:37Z" changeset="111628029" uid="443683" user="malko05"/>

Ce noeud est défini par son identifiant, sa latitude, sa longitude et d'autres paramètres encore.

Pour reconstituer le tracé des routes ou formes de bâtiments je me retrouve à faire des boucles dans des boucles et je me rends compte que cela décuple considérablement le temps de chargement du fichier au point que cela peut prendre plusieurs minutes. Pourtant le logiciel Blender lit le même fichier en quelques secondes à peine.

Voici mon code simplifié :

void Zone::InitWays(ifstream &fichier)
{
    cout << "Listing ways ..." << endl;

    string ligneLue;

    while(1)
    {
        getline(fichier,ligneLue);

        vector<glm::vec2> structure;

        if(ligneLue.find("<way ")!=-1)
        {
            string id;

            recupWay(ligneLue,id);		//Récupération id de way dans la ligne lue

            while(1)
            {
                getline(fichier,ligneLue);
                if(ligneLue.find("<nd ")!=-1)		//Liste des id de noeuds
                {
                    string refNoeud;

                    recupRefNoeud(ligneLue,refNoeud);	//Récupération id de noeud dans la ligne lue

                    const int indexNoeud=recupNoeudDansListe(refNoeud);		//Récupération du noeud dans la liste des 105000 noeuds, c'est ici que c'est long

                    structure.push_back(liste_nodes[indexNoeud].pos);
                }

                else
                if(ligneLue.find("</way>")!=-1)
                    break;		//Fin du parcours des 17000 ways
            }
        }

        else
        if(ligneLue.find("<relation ")!=-1)
			break;
    }
}

Le code de la fonction recupNoeudDansListe() :

Le code de la fonction recupNoeudDansListe() :

int Zone::recupNoeudDansListe(string ref)
{
    int compteur=0;

    while(1)
    {
        if(ref==liste_nodes[compteur].id)		//Tableau de 105000 noeuds parcouru jusqu'à ce que les ids correspondent
            break;

        compteur++;
        if(compteur==liste_nodes.size())
            break;
    }

    return compteur;
}

Il y a en tout 17383 x 105860 = 1 840 164 380 itérations donc ça explique certainement cette longue durée de chargement mais je ne comprends pourquoi Blender parvient à charger le même fichier en un rien de temps.

Si vous avez des solutions je suis preneur.

Plusieurs problèmes:

• N'utilise pas "using namespace std" raison + que faire
• La lecture du xml n'est pas basée sur le format xml, mais des recherches dans des lignes. Un fichier xml n'a besoin de saut de ligne, cette façon de faire est bancale. Il existe plein de lib pour lire des fichiers xml de manière efficace.
• Si ta lecture de fichier est en erreur ou que le format n'est pas comme celui que tu attends, les boucles ne s'arrêtent jamais. Les while(1) devraient au moins être transformées en while(std::getline(....)).
• std::string::find ne retourne pas -1 mais std::string::npos. D'ailleurs, c'est à mesurer, mais je pense que pour des recherches répétées souvent, std::boyer_moore_searcher / std::boyer_moore_horspool_searcher seront plus efficaces.
• La construction de std::string et std::vector à l'intérieur d'une boucle est très mauvais pour les performances. La mémoire sera constamment allouée puis libérée. Il vaut mieux déclarer les variables avant les boucles et utiliser clear() pour réduire la taille à 0 pour la prochaine itération.
• recupNoeudDansListe() devrait prendre une référence constante ou std::string_view. De plus, la forme de la boucle est particulièrement étrange. La forme usuelle est for(auto it = liste_nodes.begin(); it != liste_nodes.end(); ++it). Mais au vu du code, cela peut se faire simplement avec un algorithme:

const auto it = std::find_if(liste_nodes.begin(), liste_nodes.end(), [&](auto const& node) { return node.id == refNoeud });
if (it != liste_nodes.end()) {
  structure.push_back(it->pos);
}
else {
  // erreur, référence qui n'existe pas
}

Rien que la réduction de la copie de chaîne et des allocations devraient considérablement augmenter la vitesse d'exécution. Mais je pense qu'il est possible de gagner encore en remplaçant std::vector par std::unordered_map avec comme clef les référence de nœud.

L'efficacité se fera en chargeant l'intégralité du fichier en RAM et en y extrayant les info sous forme de string_view.

J'ai envie de dire que les parseurs efficaces devraient fonctionner ainsi. Après il existe(/ait?) généralement 2 approches de parsing SAX (?) et l'autre en mode visitation, parfois certains parseurs bindent vers des objets C++, et parfois ils savent valider. Je dirai bien de ne pas réinventer cette roue.

Merci pour vos réponses, je ne connaissais pas tout ça. Je me suis renseigné et j'ai découvert le concept de map avec apparemment un système de clé/valeur, pensez-vous qu'il serait intéressant d'utiliser cela ? Par exemple en utilisant la référence du noeud comme clé, ce qui permettrait de ne plus avoir de boucle à utiliser.

Édit : Je n'avais pas vu que tu en parlais justement à la fin de ton post jo_link_noir

Edit2 : Problème résolu ! En utilisant les maps ça fonctionne sans problème !

-
Edité par KevinGL 28 septembre 2021 à 18:39:22