Structure meilleure que map et lower_bound/upper_bound
6 réponses
Fabien LE LEZ
Bonjour,
J'ai une classe qui ressemble à :
struct Machin
{
int rouge;
int vert;
int bleu;
// quelques autres membres...
};
Je voudrais stocker un demi-million d'instances de cette classe dans
un tableau, de telle sorte que, étant donné un
Machin reference
je puisse trouver rapidement tous les élements x du tableau tels que :
reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4
&& reference.vert * 0.7 <= x.vert <= reference.vert * 1.4
&& reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
Pour l'instant, je n'ai rien trouvé de mieux que
map <int, map <int, map <int, vector<Machin> > > >
et des lower_bound et upper_bound.
Le point positif : ça marche :-)
Les points négatifs : le code de recherche est un peu tarabiscoté ; de
plus, changer le nombre de paramètres est compliqué -- et impossible
au moment de l'exécution.
Quelqu'un pourrait-il me proposer une structure plus adaptée ?
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Manuel Zaccaria
"Fabien LE LEZ" a écrit:
Bonjour,
Bonjour
J'ai une classe qui ressemble à :
struct Machin { int rouge; int vert; int bleu; // quelques autres membres... };
Je voudrais stocker un demi-million d'instances de cette classe dans un tableau, de telle sorte que, étant donné un Machin reference je puisse trouver rapidement tous les élements x du tableau tels que : reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4 && reference.vert * 0.7 <= x.vert <= reference.vert * 1.4 && reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
Pour l'instant, je n'ai rien trouvé de mieux que map <int, map <int, map <int, vector<Machin> > > > et des lower_bound et upper_bound.
Le point positif : ça marche :-)
Les points négatifs : le code de recherche est un peu tarabiscoté ; de plus, changer le nombre de paramètres est compliqué -- et impossible au moment de l'exécution.
Quelqu'un pourrait-il me proposer une structure plus adaptée ?
Je me demande si boost::multi_index_container<> ferait l'affaire...
Manuel
"Fabien LE LEZ" a écrit:
Bonjour,
Bonjour
J'ai une classe qui ressemble à :
struct Machin
{
int rouge;
int vert;
int bleu;
// quelques autres membres...
};
Je voudrais stocker un demi-million d'instances de cette classe dans
un tableau, de telle sorte que, étant donné un
Machin reference
je puisse trouver rapidement tous les élements x du tableau tels que :
reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4
&& reference.vert * 0.7 <= x.vert <= reference.vert * 1.4
&& reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
Pour l'instant, je n'ai rien trouvé de mieux que
map <int, map <int, map <int, vector<Machin> > > >
et des lower_bound et upper_bound.
Le point positif : ça marche :-)
Les points négatifs : le code de recherche est un peu tarabiscoté ; de
plus, changer le nombre de paramètres est compliqué -- et impossible
au moment de l'exécution.
Quelqu'un pourrait-il me proposer une structure plus adaptée ?
Je me demande si boost::multi_index_container<> ferait l'affaire...
struct Machin { int rouge; int vert; int bleu; // quelques autres membres... };
Je voudrais stocker un demi-million d'instances de cette classe dans un tableau, de telle sorte que, étant donné un Machin reference je puisse trouver rapidement tous les élements x du tableau tels que : reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4 && reference.vert * 0.7 <= x.vert <= reference.vert * 1.4 && reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
Pour l'instant, je n'ai rien trouvé de mieux que map <int, map <int, map <int, vector<Machin> > > > et des lower_bound et upper_bound.
Le point positif : ça marche :-)
Les points négatifs : le code de recherche est un peu tarabiscoté ; de plus, changer le nombre de paramètres est compliqué -- et impossible au moment de l'exécution.
Quelqu'un pourrait-il me proposer une structure plus adaptée ?
Je me demande si boost::multi_index_container<> ferait l'affaire...
Manuel
loufoque
J'ai une classe qui ressemble à :
struct Machin { int rouge; int vert; int bleu; // quelques autres membres... };
Je voudrais stocker un demi-million d'instances de cette classe dans un tableau, de telle sorte que, étant donné un Machin reference je puisse trouver rapidement tous les élements x du tableau tels que : reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4 && reference.vert * 0.7 <= x.vert <= reference.vert * 1.4 && reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
Qu'est-ce qui empêche de mettre ces instances dans un std::vector par exemple puis de parcourir ce conteneur pour trouver les instances voulues ?
J'ai une classe qui ressemble à :
struct Machin
{
int rouge;
int vert;
int bleu;
// quelques autres membres...
};
Je voudrais stocker un demi-million d'instances de cette classe dans
un tableau, de telle sorte que, étant donné un
Machin reference
je puisse trouver rapidement tous les élements x du tableau tels que :
reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4
&& reference.vert * 0.7 <= x.vert <= reference.vert * 1.4
&& reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
Qu'est-ce qui empêche de mettre ces instances dans un std::vector par
exemple puis de parcourir ce conteneur pour trouver les instances voulues ?
struct Machin { int rouge; int vert; int bleu; // quelques autres membres... };
Je voudrais stocker un demi-million d'instances de cette classe dans un tableau, de telle sorte que, étant donné un Machin reference je puisse trouver rapidement tous les élements x du tableau tels que : reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4 && reference.vert * 0.7 <= x.vert <= reference.vert * 1.4 && reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
Qu'est-ce qui empêche de mettre ces instances dans un std::vector par exemple puis de parcourir ce conteneur pour trouver les instances voulues ?
Loïc Joly
Bonjour,
J'ai une classe qui ressemble à :
struct Machin { int rouge; int vert; int bleu; // quelques autres membres... };
Je voudrais stocker un demi-million d'instances de cette classe dans un tableau, de telle sorte que, étant donné un Machin reference je puisse trouver rapidement tous les élements x du tableau tels que : reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4 && reference.vert * 0.7 <= x.vert <= reference.vert * 1.4 && reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
Une idée comme ça, à toi de creuser voir si elle tient debout ;)
Tu peux considérer ces valeurs comme des coordonnées de points dans un espace à dimension n (ici 3). Il y a des structures comme les Quadtrees (Q-Tree) ou les R-Tree (et sûrement d'autres encore) qui permettent alors d'avoir avec des bonnes perfs les points à proximité d'un autre.
-- Loïc
Bonjour,
J'ai une classe qui ressemble à :
struct Machin
{
int rouge;
int vert;
int bleu;
// quelques autres membres...
};
Je voudrais stocker un demi-million d'instances de cette classe dans
un tableau, de telle sorte que, étant donné un
Machin reference
je puisse trouver rapidement tous les élements x du tableau tels que :
reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4
&& reference.vert * 0.7 <= x.vert <= reference.vert * 1.4
&& reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
Une idée comme ça, à toi de creuser voir si elle tient debout ;)
Tu peux considérer ces valeurs comme des coordonnées de points dans un
espace à dimension n (ici 3). Il y a des structures comme les Quadtrees
(Q-Tree) ou les R-Tree (et sûrement d'autres encore) qui permettent
alors d'avoir avec des bonnes perfs les points à proximité d'un autre.
struct Machin { int rouge; int vert; int bleu; // quelques autres membres... };
Je voudrais stocker un demi-million d'instances de cette classe dans un tableau, de telle sorte que, étant donné un Machin reference je puisse trouver rapidement tous les élements x du tableau tels que : reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4 && reference.vert * 0.7 <= x.vert <= reference.vert * 1.4 && reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
Une idée comme ça, à toi de creuser voir si elle tient debout ;)
Tu peux considérer ces valeurs comme des coordonnées de points dans un espace à dimension n (ici 3). Il y a des structures comme les Quadtrees (Q-Tree) ou les R-Tree (et sûrement d'autres encore) qui permettent alors d'avoir avec des bonnes perfs les points à proximité d'un autre.
-- Loïc
Sylvain
Fabien LE LEZ wrote on 17/07/2006 22:07:
Je voudrais stocker un demi-million d'instances de cette classe dans un tableau, de telle sorte que, étant donné un Machin reference je puisse trouver rapidement tous les élements x du tableau tels que : reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4 && reference.vert * 0.7 <= x.vert <= reference.vert * 1.4 && reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
tu veux très rapidement trouver le premier et à cout variable, non nul, trouver le suivant; ou trouver le plus rapidement possible tous les élements (à itérer sans cout) ?
tu t'autorises quel cout mémoire par Machin stocké ? quel cout max pour des index dynamiques ?
Sylvain.
Fabien LE LEZ wrote on 17/07/2006 22:07:
Je voudrais stocker un demi-million d'instances de cette classe dans
un tableau, de telle sorte que, étant donné un
Machin reference
je puisse trouver rapidement tous les élements x du tableau tels que :
reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4
&& reference.vert * 0.7 <= x.vert <= reference.vert * 1.4
&& reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
tu veux très rapidement trouver le premier et à cout variable, non nul,
trouver le suivant; ou trouver le plus rapidement possible tous les
élements (à itérer sans cout) ?
tu t'autorises quel cout mémoire par Machin stocké ? quel cout max pour
des index dynamiques ?
Je voudrais stocker un demi-million d'instances de cette classe dans un tableau, de telle sorte que, étant donné un Machin reference je puisse trouver rapidement tous les élements x du tableau tels que : reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4 && reference.vert * 0.7 <= x.vert <= reference.vert * 1.4 && reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
tu veux très rapidement trouver le premier et à cout variable, non nul, trouver le suivant; ou trouver le plus rapidement possible tous les élements (à itérer sans cout) ?
tu t'autorises quel cout mémoire par Machin stocké ? quel cout max pour des index dynamiques ?
Sylvain.
Sylvain
Fabien LE LEZ wrote on 17/07/2006 22:07:
Je voudrais stocker un demi-million d'instances de cette classe dans un tableau, de telle sorte que, étant donné un Machin reference je puisse trouver rapidement tous les élements x du tableau tels que : reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4 && reference.vert * 0.7 <= x.vert <= reference.vert * 1.4 && reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
avec un vector redimensionnable par pas de 100.000 et qSortable, je génère 500.000 Machin en 156 ms avec r,g,b issu de rand() (donc 0 <= x < 32767)
avec un Machin reference arbitrairement choisi (rand() x 3), j'extrais 21571 références (192685 items après premier critère, 79696 après second) vérifiant les 3 inégalités en 735 ms sur un P4 2.8 GHz, ça doit pouvoir aller plus vite avec qlq options d'optim.; c'est trop lent pour ton usage ?
Sylvain.
Fabien LE LEZ wrote on 17/07/2006 22:07:
Je voudrais stocker un demi-million d'instances de cette classe dans
un tableau, de telle sorte que, étant donné un
Machin reference
je puisse trouver rapidement tous les élements x du tableau tels que :
reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4
&& reference.vert * 0.7 <= x.vert <= reference.vert * 1.4
&& reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
avec un vector redimensionnable par pas de 100.000 et qSortable, je
génère 500.000 Machin en 156 ms avec r,g,b issu de rand() (donc 0 <= x <
32767)
avec un Machin reference arbitrairement choisi (rand() x 3), j'extrais
21571 références (192685 items après premier critère, 79696 après
second) vérifiant les 3 inégalités en 735 ms sur un P4 2.8 GHz, ça doit
pouvoir aller plus vite avec qlq options d'optim.; c'est trop lent pour
ton usage ?
Je voudrais stocker un demi-million d'instances de cette classe dans un tableau, de telle sorte que, étant donné un Machin reference je puisse trouver rapidement tous les élements x du tableau tels que : reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4 && reference.vert * 0.7 <= x.vert <= reference.vert * 1.4 && reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
avec un vector redimensionnable par pas de 100.000 et qSortable, je génère 500.000 Machin en 156 ms avec r,g,b issu de rand() (donc 0 <= x < 32767)
avec un Machin reference arbitrairement choisi (rand() x 3), j'extrais 21571 références (192685 items après premier critère, 79696 après second) vérifiant les 3 inégalités en 735 ms sur un P4 2.8 GHz, ça doit pouvoir aller plus vite avec qlq options d'optim.; c'est trop lent pour ton usage ?
Sylvain.
kanze
Fabien LE LEZ wrote:
J'ai une classe qui ressemble à :
struct Machin { int rouge; int vert; int bleu; // quelques autres membres... };
Je voudrais stocker un demi-million d'instances de cette classe dans un tableau, de telle sorte que, étant donné un Machin reference je puisse trouver rapidement tous les élements x du tableau tels que : reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4 && reference.vert * 0.7 <= x.vert <= reference.vert * 1.4 && reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
Pour l'instant, je n'ai rien trouvé de mieux que map <int, map <int, map <int, vector<Machin> > > > et des lower_bound et upper_bound.
Le point positif : ça marche :-)
Les points négatifs : le code de recherche est un peu tarabiscoté ; de plus, changer le nombre de paramètres est compliqué -- et impossible au moment de l'exécution.
Autre point négatif, peut-être : ça bouffe un maximum de mémoire:-). Et risque d'avoir une localité assez mauvaise. (Pour des petits ensembles d'un démi-million d'éléments, je ne crois pas que ça pose réelement un problème.)
Quelqu'un pourrait-il me proposer une structure plus adaptée ?
Je ne sais pas, mais je crois que je serais parti d'un simple std::vector< Machin >, maintenu trié selon un critère de tri qui va bien. (C-à-d une utilisation de std::lower_bound lors de l'insertion.) Soit, éventuellement, un std::vector< Machin >, et trois std::vector< Machin* >, trié chacun sur un des couleurs. (Note bien qu'en tant que structure, il se peut que les quatre vecteurs ensemble utilise moins de mémoire que ton map.) Ensuite : c'est facile à trouver des itérateurs de bornes pour chacune des couleurs, et un petit coup de std::set_intersection doit faire la reste. (Note bien que pour que set_intersection soit utilisable, il faut créer des vecteurs intermédiaire trier sur le même critère. Ce qui est bien si chacun des critères éliminer la plupart des éléments, mais risque fort de poser un problème si par exemple 90% des éléments passe un des critères.)
-- James Kanze GABI Software Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Fabien LE LEZ wrote:
J'ai une classe qui ressemble à :
struct Machin
{
int rouge;
int vert;
int bleu;
// quelques autres membres...
};
Je voudrais stocker un demi-million d'instances de cette
classe dans un tableau, de telle sorte que, étant donné un
Machin reference
je puisse trouver rapidement tous les élements x du tableau tels que :
reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4
&& reference.vert * 0.7 <= x.vert <= reference.vert * 1.4
&& reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
Pour l'instant, je n'ai rien trouvé de mieux que
map <int, map <int, map <int, vector<Machin> > > >
et des lower_bound et upper_bound.
Le point positif : ça marche :-)
Les points négatifs : le code de recherche est un peu
tarabiscoté ; de plus, changer le nombre de paramètres est
compliqué -- et impossible au moment de l'exécution.
Autre point négatif, peut-être : ça bouffe un maximum de
mémoire:-). Et risque d'avoir une localité assez mauvaise. (Pour
des petits ensembles d'un démi-million d'éléments, je ne crois
pas que ça pose réelement un problème.)
Quelqu'un pourrait-il me proposer une structure plus adaptée ?
Je ne sais pas, mais je crois que je serais parti d'un simple
std::vector< Machin >, maintenu trié selon un critère de tri qui
va bien. (C-à-d une utilisation de std::lower_bound lors de
l'insertion.) Soit, éventuellement, un std::vector< Machin >, et
trois std::vector< Machin* >, trié chacun sur un des couleurs.
(Note bien qu'en tant que structure, il se peut que les quatre
vecteurs ensemble utilise moins de mémoire que ton map.)
Ensuite : c'est facile à trouver des itérateurs de bornes pour
chacune des couleurs, et un petit coup de std::set_intersection
doit faire la reste. (Note bien que pour que set_intersection
soit utilisable, il faut créer des vecteurs intermédiaire trier
sur le même critère. Ce qui est bien si chacun des critères
éliminer la plupart des éléments, mais risque fort de poser un
problème si par exemple 90% des éléments passe un des critères.)
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
struct Machin { int rouge; int vert; int bleu; // quelques autres membres... };
Je voudrais stocker un demi-million d'instances de cette classe dans un tableau, de telle sorte que, étant donné un Machin reference je puisse trouver rapidement tous les élements x du tableau tels que : reference.rouge * 0.7 <= x.rouge <= reference.rouge * 1.4 && reference.vert * 0.7 <= x.vert <= reference.vert * 1.4 && reference.bleu * 0.7 <= x.bleu <= reference.bleu * 1.4
Pour l'instant, je n'ai rien trouvé de mieux que map <int, map <int, map <int, vector<Machin> > > > et des lower_bound et upper_bound.
Le point positif : ça marche :-)
Les points négatifs : le code de recherche est un peu tarabiscoté ; de plus, changer le nombre de paramètres est compliqué -- et impossible au moment de l'exécution.
Autre point négatif, peut-être : ça bouffe un maximum de mémoire:-). Et risque d'avoir une localité assez mauvaise. (Pour des petits ensembles d'un démi-million d'éléments, je ne crois pas que ça pose réelement un problème.)
Quelqu'un pourrait-il me proposer une structure plus adaptée ?
Je ne sais pas, mais je crois que je serais parti d'un simple std::vector< Machin >, maintenu trié selon un critère de tri qui va bien. (C-à-d une utilisation de std::lower_bound lors de l'insertion.) Soit, éventuellement, un std::vector< Machin >, et trois std::vector< Machin* >, trié chacun sur un des couleurs. (Note bien qu'en tant que structure, il se peut que les quatre vecteurs ensemble utilise moins de mémoire que ton map.) Ensuite : c'est facile à trouver des itérateurs de bornes pour chacune des couleurs, et un petit coup de std::set_intersection doit faire la reste. (Note bien que pour que set_intersection soit utilisable, il faut créer des vecteurs intermédiaire trier sur le même critère. Ce qui est bien si chacun des critères éliminer la plupart des éléments, mais risque fort de poser un problème si par exemple 90% des éléments passe un des critères.)
-- James Kanze GABI Software Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
