JKB a écrit :Que deviens edges[] apres l'initialisation du graphe ? Si tu ne le vide
pas, alors tu as deux copie des proprietes des aretes, une dans edges[],
et une dans le graphe (en interne). Ca peut etre une piste pour
economiser de la memoire.
La fonction appelante (C) fait un sauvage :
munmap((void *) edges, edges_size * size(edge_astar_t));
C'est un unmap() et non un malloc() parce que sous Solaris, free()
renvoie la mémoire à l'application et non au système.
no comment ;)Est-ce que tu peux donner la definition de ton typedef graph_t, et
l'invocation de l'algorithme ?
Le wrapper C++ que je modifie commence par :
<snip>Le wrapper complet est disponible à
<http://www.bertrand-lecarpentier.net/~bertrand/astar_boost_wrapper.cpp>
Je suppose que tu reecrit la fonction boost_astar ? Rien de choquant
a premiere vue, a part l'affreux graph_t statique et la gestion de
l'initialisation.
Si tu decoupe cette fonction en 3 parties (init,
calcul, recuperation des resultats) ca pourrait peut-etre marcher.
(et par curiosite, pourquoi astar plutot que dijkstra ?)
Parce que les graphes sont gros.
J'avais utilise dijkstra sur des graphes a plusieurs dizaines de
milliers de noeuds, ce que je trouvais gros, et ca allait suffisamment
vite (mais je crois qu'a l'epoque l'algo astar_search n'etait pas encore
dans Boost). Bref, les tiens doivent donc etre plus gros que ca ;)
JKB a écrit :
Que deviens edges[] apres l'initialisation du graphe ? Si tu ne le vide
pas, alors tu as deux copie des proprietes des aretes, une dans edges[],
et une dans le graphe (en interne). Ca peut etre une piste pour
economiser de la memoire.
La fonction appelante (C) fait un sauvage :
munmap((void *) edges, edges_size * size(edge_astar_t));
C'est un unmap() et non un malloc() parce que sous Solaris, free()
renvoie la mémoire à l'application et non au système.
no comment ;)
Est-ce que tu peux donner la definition de ton typedef graph_t, et
l'invocation de l'algorithme ?
Le wrapper C++ que je modifie commence par :
<snip>
Le wrapper complet est disponible à
<http://www.bertrand-lecarpentier.net/~bertrand/astar_boost_wrapper.cpp>
Je suppose que tu reecrit la fonction boost_astar ? Rien de choquant
a premiere vue, a part l'affreux graph_t statique et la gestion de
l'initialisation.
Si tu decoupe cette fonction en 3 parties (init,
calcul, recuperation des resultats) ca pourrait peut-etre marcher.
(et par curiosite, pourquoi astar plutot que dijkstra ?)
Parce que les graphes sont gros.
J'avais utilise dijkstra sur des graphes a plusieurs dizaines de
milliers de noeuds, ce que je trouvais gros, et ca allait suffisamment
vite (mais je crois qu'a l'epoque l'algo astar_search n'etait pas encore
dans Boost). Bref, les tiens doivent donc etre plus gros que ca ;)
JKB a écrit :Que deviens edges[] apres l'initialisation du graphe ? Si tu ne le vide
pas, alors tu as deux copie des proprietes des aretes, une dans edges[],
et une dans le graphe (en interne). Ca peut etre une piste pour
economiser de la memoire.
La fonction appelante (C) fait un sauvage :
munmap((void *) edges, edges_size * size(edge_astar_t));
C'est un unmap() et non un malloc() parce que sous Solaris, free()
renvoie la mémoire à l'application et non au système.
no comment ;)Est-ce que tu peux donner la definition de ton typedef graph_t, et
l'invocation de l'algorithme ?
Le wrapper C++ que je modifie commence par :
<snip>Le wrapper complet est disponible à
<http://www.bertrand-lecarpentier.net/~bertrand/astar_boost_wrapper.cpp>
Je suppose que tu reecrit la fonction boost_astar ? Rien de choquant
a premiere vue, a part l'affreux graph_t statique et la gestion de
l'initialisation.
Si tu decoupe cette fonction en 3 parties (init,
calcul, recuperation des resultats) ca pourrait peut-etre marcher.
(et par curiosite, pourquoi astar plutot que dijkstra ?)
Parce que les graphes sont gros.
J'avais utilise dijkstra sur des graphes a plusieurs dizaines de
milliers de noeuds, ce que je trouvais gros, et ca allait suffisamment
vite (mais je crois qu'a l'epoque l'algo astar_search n'etait pas encore
dans Boost). Bref, les tiens doivent donc etre plus gros que ca ;)
Le 02-12-2008, ? propos de
Re: Threads et boost,
Michel Decima ?crivait dans fr.comp.lang.c++ :JKB a écrit :Que deviens edges[] apres l'initialisation du graphe ? Si tu ne le vide
pas, alors tu as deux copie des proprietes des aretes, une dans edges[],
et une dans le graphe (en interne). Ca peut etre une piste pour
economiser de la memoire.
La fonction appelante (C) fait un sauvage :
munmap((void *) edges, edges_size * size(edge_astar_t));
C'est un unmap() et non un malloc() parce que sous Solaris, free()
renvoie la mémoire à l'application et non au système.
no comment ;)Est-ce que tu peux donner la definition de ton typedef graph_t, et
l'invocation de l'algorithme ?
Le wrapper C++ que je modifie commence par :
<snip>Le wrapper complet est disponible à
<http://www.bertrand-lecarpentier.net/~bertrand/astar_boost_wrapper.cpp>
Je suppose que tu reecrit la fonction boost_astar ? Rien de choquant
a premiere vue, a part l'affreux graph_t statique et la gestion de
l'initialisation.
C'est fait à la hussarde, mais il y a une raison. La routine de base
faisait l'initialisation à _chaque_ appel, et cette initialisation
bouffait 90% du temps passé dans la fonction (en plus, la version de
base récupérait ses données dans une base postgresql...).Si tu decoupe cette fonction en 3 parties (init,
calcul, recuperation des resultats) ca pourrait peut-etre marcher.
Là, j'ai un peu de mal à comprendre pourquoi en coupant la partie
calcul de la partie récupération, cela fonctionnerait mieux. Je ne vois
déjà pas trop comment séparer la partie initialisation de la partie
calcul sans refaire à chaque fois cette étape grouiguesque
d'initilisation...
(et par curiosite, pourquoi astar plutot que dijkstra ?)
Parce que les graphes sont gros.
J'avais utilise dijkstra sur des graphes a plusieurs dizaines de
milliers de noeuds, ce que je trouvais gros, et ca allait suffisamment
vite (mais je crois qu'a l'epoque l'algo astar_search n'etait pas encore
dans Boost). Bref, les tiens doivent donc etre plus gros que ca ;)
6,3 millions de points ;-)
Le 02-12-2008, ? propos de
Re: Threads et boost,
Michel Decima ?crivait dans fr.comp.lang.c++ :
JKB a écrit :
Que deviens edges[] apres l'initialisation du graphe ? Si tu ne le vide
pas, alors tu as deux copie des proprietes des aretes, une dans edges[],
et une dans le graphe (en interne). Ca peut etre une piste pour
economiser de la memoire.
La fonction appelante (C) fait un sauvage :
munmap((void *) edges, edges_size * size(edge_astar_t));
C'est un unmap() et non un malloc() parce que sous Solaris, free()
renvoie la mémoire à l'application et non au système.
no comment ;)
Est-ce que tu peux donner la definition de ton typedef graph_t, et
l'invocation de l'algorithme ?
Le wrapper C++ que je modifie commence par :
<snip>
Le wrapper complet est disponible à
<http://www.bertrand-lecarpentier.net/~bertrand/astar_boost_wrapper.cpp>
Je suppose que tu reecrit la fonction boost_astar ? Rien de choquant
a premiere vue, a part l'affreux graph_t statique et la gestion de
l'initialisation.
C'est fait à la hussarde, mais il y a une raison. La routine de base
faisait l'initialisation à _chaque_ appel, et cette initialisation
bouffait 90% du temps passé dans la fonction (en plus, la version de
base récupérait ses données dans une base postgresql...).
Si tu decoupe cette fonction en 3 parties (init,
calcul, recuperation des resultats) ca pourrait peut-etre marcher.
Là, j'ai un peu de mal à comprendre pourquoi en coupant la partie
calcul de la partie récupération, cela fonctionnerait mieux. Je ne vois
déjà pas trop comment séparer la partie initialisation de la partie
calcul sans refaire à chaque fois cette étape grouiguesque
d'initilisation...
(et par curiosite, pourquoi astar plutot que dijkstra ?)
Parce que les graphes sont gros.
J'avais utilise dijkstra sur des graphes a plusieurs dizaines de
milliers de noeuds, ce que je trouvais gros, et ca allait suffisamment
vite (mais je crois qu'a l'epoque l'algo astar_search n'etait pas encore
dans Boost). Bref, les tiens doivent donc etre plus gros que ca ;)
6,3 millions de points ;-)
Le 02-12-2008, ? propos de
Re: Threads et boost,
Michel Decima ?crivait dans fr.comp.lang.c++ :JKB a écrit :Que deviens edges[] apres l'initialisation du graphe ? Si tu ne le vide
pas, alors tu as deux copie des proprietes des aretes, une dans edges[],
et une dans le graphe (en interne). Ca peut etre une piste pour
economiser de la memoire.
La fonction appelante (C) fait un sauvage :
munmap((void *) edges, edges_size * size(edge_astar_t));
C'est un unmap() et non un malloc() parce que sous Solaris, free()
renvoie la mémoire à l'application et non au système.
no comment ;)Est-ce que tu peux donner la definition de ton typedef graph_t, et
l'invocation de l'algorithme ?
Le wrapper C++ que je modifie commence par :
<snip>Le wrapper complet est disponible à
<http://www.bertrand-lecarpentier.net/~bertrand/astar_boost_wrapper.cpp>
Je suppose que tu reecrit la fonction boost_astar ? Rien de choquant
a premiere vue, a part l'affreux graph_t statique et la gestion de
l'initialisation.
C'est fait à la hussarde, mais il y a une raison. La routine de base
faisait l'initialisation à _chaque_ appel, et cette initialisation
bouffait 90% du temps passé dans la fonction (en plus, la version de
base récupérait ses données dans une base postgresql...).Si tu decoupe cette fonction en 3 parties (init,
calcul, recuperation des resultats) ca pourrait peut-etre marcher.
Là, j'ai un peu de mal à comprendre pourquoi en coupant la partie
calcul de la partie récupération, cela fonctionnerait mieux. Je ne vois
déjà pas trop comment séparer la partie initialisation de la partie
calcul sans refaire à chaque fois cette étape grouiguesque
d'initilisation...
(et par curiosite, pourquoi astar plutot que dijkstra ?)
Parce que les graphes sont gros.
J'avais utilise dijkstra sur des graphes a plusieurs dizaines de
milliers de noeuds, ce que je trouvais gros, et ca allait suffisamment
vite (mais je crois qu'a l'epoque l'algo astar_search n'etait pas encore
dans Boost). Bref, les tiens doivent donc etre plus gros que ca ;)
6,3 millions de points ;-)
JKB a écrit :Là, j'ai un peu de mal à comprendre pourquoi en coupant la partie
calcul de la partie récupération, cela fonctionnerait mieux. Je ne vois
déjà pas trop comment séparer la partie initialisation de la partie
calcul sans refaire à chaque fois cette étape grouiguesque
d'initilisation...
Parce que l'initialisation est faite en fonction de la valeur de la
variable statique 'initialization', et que cette variable est lue et
modifiee sans protection, donc depuis plusieurs threads ca risque d'etre
pas beau a voir.
Je suppose que si tu passe par ce wrapper, c'est que le code appelant
est en C ? Dans ce cas tu pourrais envisager une interface comme ceci :
// type abstrait qui pointe vers une structure contenant le graphe
// (definie dans le .cpp)
//
typedef void* boost_astar_graph ;
// allocation de la structure, et remplissage du graphe avec les
// donnees d'entree. Sera appellee une seule fois dans le thread
// principal.
//
boost_astar_graph* boost_astar_create( edge_astar_t*, etc... ) ;
// encapsule l'appel a l'algorithme et l'extraction des resultats,
// sans modifier la structure g. Devrait pouvoir etre appelee par
// plusieurs threads simultanement.
//
int boost_astar_search( boost_astar_graph* g, source, target,
result, ... ) ;
// liberation des ressources
void boost_astar_destroy( boost_astar_graph* g ) ;
6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours de
celui qui a le plus gros, vainqueur: JKB).
Plus serieusement, l'algo utilise au moins 3 proprietes de travail
(distance_map, color_map et rank_map) qui doivent etre allouees
localement soit par l'algo lui-meme, soit par le wrapper. Si elles
portent sur les noeuds, ca veut dire allocation/liberation de 3
tableaux de 6 million d'entree a chaque appel, par thread. Si c'est
des proprietes sur les aretes, ca sera pire.
JKB a écrit :
Là, j'ai un peu de mal à comprendre pourquoi en coupant la partie
calcul de la partie récupération, cela fonctionnerait mieux. Je ne vois
déjà pas trop comment séparer la partie initialisation de la partie
calcul sans refaire à chaque fois cette étape grouiguesque
d'initilisation...
Parce que l'initialisation est faite en fonction de la valeur de la
variable statique 'initialization', et que cette variable est lue et
modifiee sans protection, donc depuis plusieurs threads ca risque d'etre
pas beau a voir.
Je suppose que si tu passe par ce wrapper, c'est que le code appelant
est en C ? Dans ce cas tu pourrais envisager une interface comme ceci :
// type abstrait qui pointe vers une structure contenant le graphe
// (definie dans le .cpp)
//
typedef void* boost_astar_graph ;
// allocation de la structure, et remplissage du graphe avec les
// donnees d'entree. Sera appellee une seule fois dans le thread
// principal.
//
boost_astar_graph* boost_astar_create( edge_astar_t*, etc... ) ;
// encapsule l'appel a l'algorithme et l'extraction des resultats,
// sans modifier la structure g. Devrait pouvoir etre appelee par
// plusieurs threads simultanement.
//
int boost_astar_search( boost_astar_graph* g, source, target,
result, ... ) ;
// liberation des ressources
void boost_astar_destroy( boost_astar_graph* g ) ;
6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours de
celui qui a le plus gros, vainqueur: JKB).
Plus serieusement, l'algo utilise au moins 3 proprietes de travail
(distance_map, color_map et rank_map) qui doivent etre allouees
localement soit par l'algo lui-meme, soit par le wrapper. Si elles
portent sur les noeuds, ca veut dire allocation/liberation de 3
tableaux de 6 million d'entree a chaque appel, par thread. Si c'est
des proprietes sur les aretes, ca sera pire.
JKB a écrit :Là, j'ai un peu de mal à comprendre pourquoi en coupant la partie
calcul de la partie récupération, cela fonctionnerait mieux. Je ne vois
déjà pas trop comment séparer la partie initialisation de la partie
calcul sans refaire à chaque fois cette étape grouiguesque
d'initilisation...
Parce que l'initialisation est faite en fonction de la valeur de la
variable statique 'initialization', et que cette variable est lue et
modifiee sans protection, donc depuis plusieurs threads ca risque d'etre
pas beau a voir.
Je suppose que si tu passe par ce wrapper, c'est que le code appelant
est en C ? Dans ce cas tu pourrais envisager une interface comme ceci :
// type abstrait qui pointe vers une structure contenant le graphe
// (definie dans le .cpp)
//
typedef void* boost_astar_graph ;
// allocation de la structure, et remplissage du graphe avec les
// donnees d'entree. Sera appellee une seule fois dans le thread
// principal.
//
boost_astar_graph* boost_astar_create( edge_astar_t*, etc... ) ;
// encapsule l'appel a l'algorithme et l'extraction des resultats,
// sans modifier la structure g. Devrait pouvoir etre appelee par
// plusieurs threads simultanement.
//
int boost_astar_search( boost_astar_graph* g, source, target,
result, ... ) ;
// liberation des ressources
void boost_astar_destroy( boost_astar_graph* g ) ;
6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours de
celui qui a le plus gros, vainqueur: JKB).
Plus serieusement, l'algo utilise au moins 3 proprietes de travail
(distance_map, color_map et rank_map) qui doivent etre allouees
localement soit par l'algo lui-meme, soit par le wrapper. Si elles
portent sur les noeuds, ca veut dire allocation/liberation de 3
tableaux de 6 million d'entree a chaque appel, par thread. Si c'est
des proprietes sur les aretes, ca sera pire.
6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours de
celui qui a le plus gros, vainqueur: JKB).
Franchement ? Il s'agit de la cartographie française (uniquement les
routes empruntables par un véhicule à moteur).
6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours de
celui qui a le plus gros, vainqueur: JKB).
Franchement ? Il s'agit de la cartographie française (uniquement les
routes empruntables par un véhicule à moteur).
6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours de
celui qui a le plus gros, vainqueur: JKB).
Franchement ? Il s'agit de la cartographie française (uniquement les
routes empruntables par un véhicule à moteur).
JKB a écrit :6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours de
celui qui a le plus gros, vainqueur: JKB).
Franchement ? Il s'agit de la cartographie française (uniquement les
routes empruntables par un véhicule à moteur).
Moi je jouais avec les interconnexions BGP de systemes autonomes (AS).
Donc un max théorique de 65535 points, et pas beaucoup d'aretes. Bref,
un monde vraiment beaucoup plus petit...
JKB a écrit :
6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours de
celui qui a le plus gros, vainqueur: JKB).
Franchement ? Il s'agit de la cartographie française (uniquement les
routes empruntables par un véhicule à moteur).
Moi je jouais avec les interconnexions BGP de systemes autonomes (AS).
Donc un max théorique de 65535 points, et pas beaucoup d'aretes. Bref,
un monde vraiment beaucoup plus petit...
JKB a écrit :6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours de
celui qui a le plus gros, vainqueur: JKB).
Franchement ? Il s'agit de la cartographie française (uniquement les
routes empruntables par un véhicule à moteur).
Moi je jouais avec les interconnexions BGP de systemes autonomes (AS).
Donc un max théorique de 65535 points, et pas beaucoup d'aretes. Bref,
un monde vraiment beaucoup plus petit...
Le 02-12-2008, ? propos de
Re: Threads et boost,
Michel Decima ?crivait dans fr.comp.lang.c++ :JKB a écrit :6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours de
celui qui a le plus gros, vainqueur: JKB).
Franchement ? Il s'agit de la cartographie française (uniquement les
routes empruntables par un véhicule à moteur).
Moi je jouais avec les interconnexions BGP de systemes autonomes (AS).
Donc un max théorique de 65535 points, et pas beaucoup d'aretes. Bref,
un monde vraiment beaucoup plus petit...
Par dessus, j'ai une couche d'optimisation dans un espace pas joli
du tout, avec une fonction de coût ni continue ni dérivable même par
morceau. Problème NP-complet fabuleux (et noeud au cerveau garanti ;-)).
Le 02-12-2008, ? propos de
Re: Threads et boost,
Michel Decima ?crivait dans fr.comp.lang.c++ :
JKB a écrit :
6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours de
celui qui a le plus gros, vainqueur: JKB).
Franchement ? Il s'agit de la cartographie française (uniquement les
routes empruntables par un véhicule à moteur).
Moi je jouais avec les interconnexions BGP de systemes autonomes (AS).
Donc un max théorique de 65535 points, et pas beaucoup d'aretes. Bref,
un monde vraiment beaucoup plus petit...
Par dessus, j'ai une couche d'optimisation dans un espace pas joli
du tout, avec une fonction de coût ni continue ni dérivable même par
morceau. Problème NP-complet fabuleux (et noeud au cerveau garanti ;-)).
Le 02-12-2008, ? propos de
Re: Threads et boost,
Michel Decima ?crivait dans fr.comp.lang.c++ :JKB a écrit :6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours de
celui qui a le plus gros, vainqueur: JKB).
Franchement ? Il s'agit de la cartographie française (uniquement les
routes empruntables par un véhicule à moteur).
Moi je jouais avec les interconnexions BGP de systemes autonomes (AS).
Donc un max théorique de 65535 points, et pas beaucoup d'aretes. Bref,
un monde vraiment beaucoup plus petit...
Par dessus, j'ai une couche d'optimisation dans un espace pas joli
du tout, avec une fonction de coût ni continue ni dérivable même par
morceau. Problème NP-complet fabuleux (et noeud au cerveau garanti ;-)).
Michel Decima a écrit :JKB a écrit :Le 02-12-2008, ? propos de
Re: Threads et boost,
Michel Decima ?crivait dans fr.comp.lang.c++ :JKB a écrit :6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours
de celui qui a le plus gros, vainqueur: JKB).
Franchement ? Il s'agit de la cartographie française (uniquement
les routes empruntables par un véhicule à moteur).
Moi je jouais avec les interconnexions BGP de systemes autonomes
(AS). Donc un max théorique de 65535 points, et pas beaucoup
d'aretes. Bref, un monde vraiment beaucoup plus petit...
Par dessus, j'ai une couche d'optimisation dans un espace pas joli
du tout, avec une fonction de coût ni continue ni dérivable même par
morceau. Problème NP-complet fabuleux (et noeud au cerveau garanti ;-)).
Effectivement, ca fait envie...
Je ne connais pas ce domaine mais je suis surpris qu'il n'y ait pas
d'approche divide&conquer pour éviter de tout charger en mémoire.
Moi ça me fait pas envie, je suis content de pas être à ta place :p
Michel Decima a écrit :
JKB a écrit :
Le 02-12-2008, ? propos de
Re: Threads et boost,
Michel Decima ?crivait dans fr.comp.lang.c++ :
JKB a écrit :
6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours
de celui qui a le plus gros, vainqueur: JKB).
Franchement ? Il s'agit de la cartographie française (uniquement
les routes empruntables par un véhicule à moteur).
Moi je jouais avec les interconnexions BGP de systemes autonomes
(AS). Donc un max théorique de 65535 points, et pas beaucoup
d'aretes. Bref, un monde vraiment beaucoup plus petit...
Par dessus, j'ai une couche d'optimisation dans un espace pas joli
du tout, avec une fonction de coût ni continue ni dérivable même par
morceau. Problème NP-complet fabuleux (et noeud au cerveau garanti ;-)).
Effectivement, ca fait envie...
Je ne connais pas ce domaine mais je suis surpris qu'il n'y ait pas
d'approche divide&conquer pour éviter de tout charger en mémoire.
Moi ça me fait pas envie, je suis content de pas être à ta place :p
Michel Decima a écrit :JKB a écrit :Le 02-12-2008, ? propos de
Re: Threads et boost,
Michel Decima ?crivait dans fr.comp.lang.c++ :JKB a écrit :6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours
de celui qui a le plus gros, vainqueur: JKB).
Franchement ? Il s'agit de la cartographie française (uniquement
les routes empruntables par un véhicule à moteur).
Moi je jouais avec les interconnexions BGP de systemes autonomes
(AS). Donc un max théorique de 65535 points, et pas beaucoup
d'aretes. Bref, un monde vraiment beaucoup plus petit...
Par dessus, j'ai une couche d'optimisation dans un espace pas joli
du tout, avec une fonction de coût ni continue ni dérivable même par
morceau. Problème NP-complet fabuleux (et noeud au cerveau garanti ;-)).
Effectivement, ca fait envie...
Je ne connais pas ce domaine mais je suis surpris qu'il n'y ait pas
d'approche divide&conquer pour éviter de tout charger en mémoire.
Moi ça me fait pas envie, je suis content de pas être à ta place :p
JKB a écrit :Le 02-12-2008, ? propos de
Re: Threads et boost,
Michel Decima ?crivait dans fr.comp.lang.c++ :JKB a écrit :6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours
de celui qui a le plus gros, vainqueur: JKB).
Franchement ? Il s'agit de la cartographie française (uniquement
les routes empruntables par un véhicule à moteur).
Moi je jouais avec les interconnexions BGP de systemes autonomes
(AS). Donc un max théorique de 65535 points, et pas beaucoup
d'aretes. Bref, un monde vraiment beaucoup plus petit...
Par dessus, j'ai une couche d'optimisation dans un espace pas joli
du tout, avec une fonction de coût ni continue ni dérivable même par
morceau. Problème NP-complet fabuleux (et noeud au cerveau garanti ;-)).
Effectivement, ca fait envie...
JKB a écrit :
Le 02-12-2008, ? propos de
Re: Threads et boost,
Michel Decima ?crivait dans fr.comp.lang.c++ :
JKB a écrit :
6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours
de celui qui a le plus gros, vainqueur: JKB).
Franchement ? Il s'agit de la cartographie française (uniquement
les routes empruntables par un véhicule à moteur).
Moi je jouais avec les interconnexions BGP de systemes autonomes
(AS). Donc un max théorique de 65535 points, et pas beaucoup
d'aretes. Bref, un monde vraiment beaucoup plus petit...
Par dessus, j'ai une couche d'optimisation dans un espace pas joli
du tout, avec une fonction de coût ni continue ni dérivable même par
morceau. Problème NP-complet fabuleux (et noeud au cerveau garanti ;-)).
Effectivement, ca fait envie...
JKB a écrit :Le 02-12-2008, ? propos de
Re: Threads et boost,
Michel Decima ?crivait dans fr.comp.lang.c++ :JKB a écrit :6,3 millions de points ;-)
Effectivement, ca fait beaucoup (aujourd'hui sur fclc++, concours
de celui qui a le plus gros, vainqueur: JKB).
Franchement ? Il s'agit de la cartographie française (uniquement
les routes empruntables par un véhicule à moteur).
Moi je jouais avec les interconnexions BGP de systemes autonomes
(AS). Donc un max théorique de 65535 points, et pas beaucoup
d'aretes. Bref, un monde vraiment beaucoup plus petit...
Par dessus, j'ai une couche d'optimisation dans un espace pas joli
du tout, avec une fonction de coût ni continue ni dérivable même par
morceau. Problème NP-complet fabuleux (et noeud au cerveau garanti ;-)).
Effectivement, ca fait envie...
Le 03-12-2008, ? propos de
Re: Threads et boost,
Michael DOUBEZ ?crivait dans fr.comp.lang.c++ :
Je ne connais pas ce domaine mais je suis surpris qu'il n'y ait pas
d'approche divide&conquer pour éviter de tout charger en mémoire.
Disons que le problème au départ consiste à avoir une approche
globale (et non sectorisée) et que pour une question d'architecture
matérielle, il vaut mieux tout avoir en mémoire.
Le 03-12-2008, ? propos de
Re: Threads et boost,
Michael DOUBEZ ?crivait dans fr.comp.lang.c++ :
Je ne connais pas ce domaine mais je suis surpris qu'il n'y ait pas
d'approche divide&conquer pour éviter de tout charger en mémoire.
Disons que le problème au départ consiste à avoir une approche
globale (et non sectorisée) et que pour une question d'architecture
matérielle, il vaut mieux tout avoir en mémoire.
Le 03-12-2008, ? propos de
Re: Threads et boost,
Michael DOUBEZ ?crivait dans fr.comp.lang.c++ :
Je ne connais pas ce domaine mais je suis surpris qu'il n'y ait pas
d'approche divide&conquer pour éviter de tout charger en mémoire.
Disons que le problème au départ consiste à avoir une approche
globale (et non sectorisée) et que pour une question d'architecture
matérielle, il vaut mieux tout avoir en mémoire.
JKB a écrit :Le 03-12-2008, ? propos de
Re: Threads et boost,
Michael DOUBEZ ?crivait dans fr.comp.lang.c++ :Je ne connais pas ce domaine mais je suis surpris qu'il n'y ait pas
d'approche divide&conquer pour éviter de tout charger en mémoire.
Disons que le problème au départ consiste à avoir une approche
globale (et non sectorisée) et que pour une question d'architecture
matérielle, il vaut mieux tout avoir en mémoire.
Est-ce que tu as regardé les classe subgraph et filtered_graph ? Ca te
permet de creer des "vues" sur un graphe existant, sans copier le
contenu (donc tu n'as qu'une seule representation physique du graphe,
et en particulier des proprietes internes).
Ca peut permettre de construire le sous-graphe des départementales sur
la zone de depart et d'arrivee, et le sous-graphe des autoroutes sur
l'ensemble des territoires, par exemple.
Mais bon, tout depend de l'approche choisie, c'est pas forcement
utilisable. Et dans mon souvenir, il y a des pieges subtils sur
l'acces aux proprietes, parce que les edge_descriptor du sous-graphe
ne sont plus des entiers consecutifs (ou qqch comme ca).
JKB a écrit :
Le 03-12-2008, ? propos de
Re: Threads et boost,
Michael DOUBEZ ?crivait dans fr.comp.lang.c++ :
Je ne connais pas ce domaine mais je suis surpris qu'il n'y ait pas
d'approche divide&conquer pour éviter de tout charger en mémoire.
Disons que le problème au départ consiste à avoir une approche
globale (et non sectorisée) et que pour une question d'architecture
matérielle, il vaut mieux tout avoir en mémoire.
Est-ce que tu as regardé les classe subgraph et filtered_graph ? Ca te
permet de creer des "vues" sur un graphe existant, sans copier le
contenu (donc tu n'as qu'une seule representation physique du graphe,
et en particulier des proprietes internes).
Ca peut permettre de construire le sous-graphe des départementales sur
la zone de depart et d'arrivee, et le sous-graphe des autoroutes sur
l'ensemble des territoires, par exemple.
Mais bon, tout depend de l'approche choisie, c'est pas forcement
utilisable. Et dans mon souvenir, il y a des pieges subtils sur
l'acces aux proprietes, parce que les edge_descriptor du sous-graphe
ne sont plus des entiers consecutifs (ou qqch comme ca).
JKB a écrit :Le 03-12-2008, ? propos de
Re: Threads et boost,
Michael DOUBEZ ?crivait dans fr.comp.lang.c++ :Je ne connais pas ce domaine mais je suis surpris qu'il n'y ait pas
d'approche divide&conquer pour éviter de tout charger en mémoire.
Disons que le problème au départ consiste à avoir une approche
globale (et non sectorisée) et que pour une question d'architecture
matérielle, il vaut mieux tout avoir en mémoire.
Est-ce que tu as regardé les classe subgraph et filtered_graph ? Ca te
permet de creer des "vues" sur un graphe existant, sans copier le
contenu (donc tu n'as qu'une seule representation physique du graphe,
et en particulier des proprietes internes).
Ca peut permettre de construire le sous-graphe des départementales sur
la zone de depart et d'arrivee, et le sous-graphe des autoroutes sur
l'ensemble des territoires, par exemple.
Mais bon, tout depend de l'approche choisie, c'est pas forcement
utilisable. Et dans mon souvenir, il y a des pieges subtils sur
l'acces aux proprietes, parce que les edge_descriptor du sous-graphe
ne sont plus des entiers consecutifs (ou qqch comme ca).
