Performances pour un identifiant de type « tuple » : tel quel VS agrégé
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:
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:
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:
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:]_]*
