Discussion :

[Steph_ng8]

Bonjour.

Je dispose d'une paire constituée d'une chaîne de caractères et d'un entier pour identifier des objets dans un tableau associatif.
Lesdits objets sont créés à la lecture d'un fichier, et la paire correspond au plus petit discriminant.
Une fois le fichier lu et les objets stockés dans le tableau, la paire n'a plus d'utilité, et les objets sont référencés par leur adresses (directement ou indirectement).
Elle sert à éviter de créer plusieurs fois le même objet lors de la lecture, mais également pour y faire référence qu'il ait effectivement été créé ou pas.

Exemple de fichier :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
#hide foo/2. // Référence à l'instance « foo/2 », alors qu'elle n'existe pas encore
 
foo(X, Y) :- p(X), q(Y).       // Première rencontre avec « foo/2 » => création
bar(Y) :- foo(X, Y), not g(Y). // Deuxième rencontre avec « foo/2 » => réutilisation de l'objet créé précédemment

Ma question est la suivante :
D'un point de vue implémentation, question performances et espace mémoire, est-il plus intéressant d'utiliser les deux données en tant que paire, et donc d'avoir une comparaison lexicographique, ou de les agréger, ainsi ne plus avoir de comparaison que sur une donnée ?


Cela peut donner quelque chose comme ceci.
[Edit]
Cette classe donne une vision moins abstraite des choses, et elle n'est définie que si on n'agrège pas les données.
Autrement, le résultat de l'opérateur de conversion en std::string est directement utilisé.
[/Edit]
Sachant qu'il n'y a pas de meilleur ordre qu'un autre sur les paires, l'essentiel étant de les discriminer ; l'opérateur < sert juste pour les conteneurs triés.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class PredicateArity
{
 
    std::string m_name;
    int m_arity;
 
  public:
    PredicateArity(std::string const& name, int arity)
     : m_name(name), m_arity(arity)
    {}
 
    operator std::string () const
    {
        std::ostringstream oss;
        oss << m_name << '/' << m_arity;
        return oss.str();
    }
 
    friend
    bool operator == (PredicateArity const& x, PredicateArity const& y)
    {
        return ((x.m_arity == y.m_arity) && (x.m_name == y.m_name));
    }
 
    friend
    bool operator < (PredicateArity const& x, PredicateArity const& y)
    {
        if (x.m_arity < y.m_arity)
            return true;
        return ((x.m_arity == y.m_arity) && (x.m_name < y.m_name));
    }
 
}; // class PredicateArity

J'aimerais, autant que possible éviter les tables de hachage.
Non seulement parce que je ne pense pas pouvoir écrire de fonction de hachage suffisamment efficace pour correctement limiter les collisions, mais aussi parce je ne peux pas garantir qu'elles sont implémentées pour le compilateur cible.
Mais les avis les concernant sont tout de même les bienvenus.

Question performance, c'est sûr que la comparaison de chaînes de caractères est critique.
Quant à l'espace mémoire, il me semble qu'un int prend plus de place qu'un char, et il faut atteindre un nombre élevé (donc avec suffisamment de chiffres) avant de renverser la tendance.

Bon, il faut quand même savoir que l'entier de la paire est positif ou nul, et qu'il atteindra rarement 10.
Quant à la chaîne de caractères, sa taille moyenne doit être d'une quinzaine, voire une vingtaine de caractères.
Même si elle peut être arbitrairement longue.


Même question en rajoutant un booléen qui, conceptuellement, n'a pas de sens, mais permet de simplifier les choses d'un point de vue implémentation.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class PredicateArity
{
 
    std::string m_name;
    bool m_polarity;
    int m_arity;
 
  public:
    PredicateArity(std::string const& name, bool polarity, int arity)
     : m_name(name), m_polarity(polarity), m_arity(arity)
    {}
 
    operator std::string () const
    {
        std::ostringstream oss;
        if (!m_polarity)
            oss << '-';
        oss << m_name << '/' << m_arity;
        return oss.str();
    }
 
    friend
    bool operator == (PredicateArity const& x, PredicateArity const& y)
    {
        return ((x.m_arity == y.m_arity) && (x.m_polarity == y.m_polarity) && (x.m_name == y.m_name));
    }
 
    friend
    bool operator < (PredicateArity const& x, PredicateArity const& y)
    {
        if (x.m_arity != y.m_arity)
            return (x.m_arity < y.m_arity);
        if (x.m_polarity < y.m_polarity)
            return true;
        return ((x.m_polarity == y.m_polarity) && (x.m_name < y.m_name));
    }
 
}; // class PredicateArity

Pour info, la chaîne de caractères est restreinte à ce motif : [[:lower:]][[:alnum:]_]*

[koala01]

Salut,

Personnellement, je n'utiliserais pas l'agrégat, pour la simple et bonne raison que tu perd sur les deux tableaux : lors de la création de l'agrégat (la concaténation de nombres à une chaine nécessite de convertir la chaine et le nombre en stringstream, puis de reconvertir le tout en chaine de caractères), puis au moment de la comparaison...

j'"investirais" plutot dans la mise au point d'une fonction qui convertit la chaine de caractère en une valeur numérique, de manière à ne perdre que sur un tableau (quitte à convertir quelque chose ), mais à pouvoir avoir un opérateur < proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
return converted < other.converted ||
      converted == other converted && value < other.value;

car ce genre de comparaison ne prend quasiment pas de temps (étant entendu que converted et value sont des valeurs numériques )

Maintenant, la question à se poser reste quand meme "est ce que cette comparaison est vraiment critique au point de se casser la tete pour l'améliorer, alors qu'elle ne sera visiblement utilisée que... lors de la lecture "...

Toi seul pourra répondre

[Steph_ng8]

Merci koala01.
J'avais pensé convertir l'ensemble en une valeur numérique, mais pas convertir simplement la chaîne de caractères...
Ceci dit, et tu fais bien de le pointer, ce n'est probablement pas suffisamment critique pour se « casser la tête » dessus.

À moins qu'il existe un algorithme simple (en tout cas rapide) de conversion ?
Et qui me garantisse qu'il n'y aura pas trop de collisions...

D'ailleurs, je me demande si le problème des collisions n'est pas plus critique que celui de la comparaison...
C'est vrai que s'il y a ne serait-ce qu'une collision, la représentation en mémoire ne correspondra plus exactement au fichier d'entrée, et du coup le programme pourra être complètement incohérent...

Bon, à moins qu'il y ait d'autres propositions, ou des algorithmes de conversion efficaces, je vais conserver mon tuple tel quel.