comment reduire ca

David Fleury

05/06/2007 à 21:06

On Jun 4, 9:45 pm, David Fleury wrote:

Note bien qu'à mon avis, même ma version initiale (qui générait
toutes les permutations, pour en supprimer les dupliqués par la
suite) a probablement une performance adéquate.

oula, faudrait préciser "adéquate"...
sur mon PC il ne vaut plus rien au delà de N = 12

Et si c'est vrai
que les copies pourraient être signifiantes quand on fait 10000
dans 100000, dans la pratique... même sans les copies, ça risque
de craquer. Le nombre de combinaisons dans ce cas déborde un
double, c-à-d qu'il dépasse 1E306. Alors, ce n'est pas en
supprimant une copie de chaîne qu'on va le faire passer dans le
temps (ni en mémoire).

Ta dernière version est bien.
pour le fun, j'ai mesuré avec ça (sauf erreur)
Les meilleurs méthode peuvent aller jusqu'à N = 32, en prenant le
plus mauvais cas ( K = N / 2 )
J'ai gardé juste un calcul du nombre de solutions pour les 4 algos.
(celui avec next_permutation ne peut affiche le nombre de solutions
sans stockage)

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <iterator>

#include <time.h>
using namespace std;

void compute_permutation( int maxSize, int maxPermutation )
{
std::vector< int > ref ;
for ( int i = 1 ; i <= maxPermutation ; ++ i ) {
ref.push_back( i ) ;
}
std::set< std::vector< int > > result ;
int v = 0;
do {
std::vector< int > combi( ref.begin(), ref.begin() + maxSize ) ;
std::sort( combi.begin(), combi.end() ) ;
//result.insert( combi ) ;
} while ( std::next_permutation( ref.begin(), ref.end() ) ) ;
cout << result.size() << " solution(s)" << endl;
}

static int cR = 0;

void compute_recursif( int maxSize, int end, vector< int > v =
vector<int>(), int begin = 0, int currentSize = 0 )
{
if ( currentSize == maxSize ) {
//copy( v.begin(), v.end(), ostream_iterator<int>( cout, " " ) );
//cout << endl;
++cR;
}
else
for ( int i = begin + 1; i <= end; ++i )
{
vector<int> tmp = v;
tmp.push_back( i );
compute_recursif( maxSize, end, tmp, i,currentSize+1 );
}
}

bool increment( vector<int>& value, int maxValue, int maxPermutation )
{
bool hasOverflow = true;
int currentDigit = value.size()-1;

while( hasOverflow && currentDigit >= 0 )
{
hasOverflow = ++value[currentDigit] > ( maxValue - ( maxPermutation
- currentDigit - 1 ) );
if ( !hasOverflow )
for ( int i = currentDigit+1; i < value.size(); ++i )
value[i] = value[i-1] + 1;

--currentDigit;
}
if ( hasOverflow && currentDigit<0 ) return false;

return true;
}

void compute_iteratif( int maxPermutation, int maxValue )
{
vector< int > value;
for ( int i = 1 ; i <= maxPermutation; ++i )
value.push_back( i ) ;

int v = 0;
do {
//copy( value.begin(), value.end(), ostream_iterator<int>( cout, "
" ) );
//cout << endl;
++v;
} while( increment( value, maxValue, maxPermutation ) );

cout << v << " solution(s)" << endl;
}

static int cI = 0;
void
m_from_n_iter(
std::vector< std::vector< int > >&
result,
std::vector< int >& so_far,
std::vector< int >::const_iterator
set_begin,
std::vector< int >::const_iterator
set_end,
int m )
{
if ( so_far.size() == m ) {
//result.push_back( so_far ) ;
cI++;
} else {
int left = m - so_far.size() ;
while ( set_end - set_begin >= left ) {
so_far.push_back( *set_begin ) ;
++ set_begin ;
m_from_n_iter( result, so_far, set_begin, set_end, m ) ;
so_far.pop_back() ;
}
}
}

void
m_from_n(
std::vector< std::vector< int > >& result,
std::vector< int > const& set_of_n, // n == .size()
int m )
{
std::vector< int > so_far ;
m_from_n_iter( result,
so_far,
set_of_n.begin(),
set_of_n.end(),
m ) ;
}

void compute_iterator( int K, int N )
{
std::vector< std::vector< int > > tmp;
std::vector< int > n;
for ( int i = 1; i <= N; ++i )
n.push_back( i );
m_from_n( tmp, n, K );
}

int main()
{
int N = 32;
int K = N / 2;

clock_t c = clock();
cout << "-- compute_iteratif : " << endl;
compute_iteratif( K, N );
cout << (clock() - c)/CLOCKS_PER_SEC << " second(s) " << endl;

c = clock();
cout << "-- compute_iterator : " << endl;
compute_iterator( K, N );
cout << cI << " solution(s)" << endl;
cout << (clock() - c)/CLOCKS_PER_SEC << " second(s) " << endl;

c = clock();
cout << "-- compute_recursif : " << endl;
compute_recursif( K, N );
cout << cR << " solution(s)" << endl;
cout << (clock() - c)/CLOCKS_PER_SEC << " second(s) " << endl;

c = clock();
cout << "-- compute_permutation : " << endl;
compute_permutation( K, N );
cout << (clock() - c)/CLOCKS_PER_SEC << " second(s) " << endl;
}

On Jun 4, 9:45 pm, David Fleury <dfleu...@libertysurf.fr> wrote:

Note bien qu'à mon avis, même ma version initiale (qui générait
toutes les permutations, pour en supprimer les dupliqués par la
suite) a probablement une performance adéquate.

oula, faudrait préciser "adéquate"...
sur mon PC il ne vaut plus rien au delà de N = 12

Et si c'est vrai
que les copies pourraient être signifiantes quand on fait 10000
dans 100000, dans la pratique... même sans les copies, ça risque
de craquer. Le nombre de combinaisons dans ce cas déborde un
double, c-à-d qu'il dépasse 1E306. Alors, ce n'est pas en
supprimant une copie de chaîne qu'on va le faire passer dans le
temps (ni en mémoire).

Ta dernière version est bien.
pour le fun, j'ai mesuré avec ça (sauf erreur)
Les meilleurs méthode peuvent aller jusqu'à N = 32, en prenant le
plus mauvais cas ( K = N / 2 )
J'ai gardé juste un calcul du nombre de solutions pour les 4 algos.
(celui avec next_permutation ne peut affiche le nombre de solutions
sans stockage)

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <iterator>

#include <time.h>
using namespace std;

void compute_permutation( int maxSize, int maxPermutation )
{
std::vector< int > ref ;
for ( int i = 1 ; i <= maxPermutation ; ++ i ) {
ref.push_back( i ) ;
}
std::set< std::vector< int > > result ;
int v = 0;
do {
std::vector< int > combi( ref.begin(), ref.begin() + maxSize ) ;
std::sort( combi.begin(), combi.end() ) ;
//result.insert( combi ) ;
} while ( std::next_permutation( ref.begin(), ref.end() ) ) ;
cout << result.size() << " solution(s)" << endl;
}

static int cR = 0;

void compute_recursif( int maxSize, int end, vector< int > v =
vector<int>(), int begin = 0, int currentSize = 0 )
{
if ( currentSize == maxSize ) {
//copy( v.begin(), v.end(), ostream_iterator<int>( cout, " " ) );
//cout << endl;
++cR;
}
else
for ( int i = begin + 1; i <= end; ++i )
{
vector<int> tmp = v;
tmp.push_back( i );
compute_recursif( maxSize, end, tmp, i,currentSize+1 );
}
}

bool increment( vector<int>& value, int maxValue, int maxPermutation )
{
bool hasOverflow = true;
int currentDigit = value.size()-1;

while( hasOverflow && currentDigit >= 0 )
{
hasOverflow = ++value[currentDigit] > ( maxValue - ( maxPermutation
- currentDigit - 1 ) );
if ( !hasOverflow )
for ( int i = currentDigit+1; i < value.size(); ++i )
value[i] = value[i-1] + 1;

--currentDigit;
}
if ( hasOverflow && currentDigit<0 ) return false;

return true;
}

void compute_iteratif( int maxPermutation, int maxValue )
{
vector< int > value;
for ( int i = 1 ; i <= maxPermutation; ++i )
value.push_back( i ) ;

int v = 0;
do {
//copy( value.begin(), value.end(), ostream_iterator<int>( cout, "
" ) );
//cout << endl;
++v;
} while( increment( value, maxValue, maxPermutation ) );

cout << v << " solution(s)" << endl;
}

static int cI = 0;
void
m_from_n_iter(
std::vector< std::vector< int > >&
result,
std::vector< int >& so_far,
std::vector< int >::const_iterator
set_begin,
std::vector< int >::const_iterator
set_end,
int m )
{
if ( so_far.size() == m ) {
//result.push_back( so_far ) ;
cI++;
} else {
int left = m - so_far.size() ;
while ( set_end - set_begin >= left ) {
so_far.push_back( *set_begin ) ;
++ set_begin ;
m_from_n_iter( result, so_far, set_begin, set_end, m ) ;
so_far.pop_back() ;
}
}
}

void
m_from_n(
std::vector< std::vector< int > >& result,
std::vector< int > const& set_of_n, // n == .size()
int m )
{
std::vector< int > so_far ;
m_from_n_iter( result,
so_far,
set_of_n.begin(),
set_of_n.end(),
m ) ;
}

void compute_iterator( int K, int N )
{
std::vector< std::vector< int > > tmp;
std::vector< int > n;
for ( int i = 1; i <= N; ++i )
n.push_back( i );
m_from_n( tmp, n, K );
}

int main()
{
int N = 32;
int K = N / 2;

clock_t c = clock();
cout << "-- compute_iteratif : " << endl;
compute_iteratif( K, N );
cout << (clock() - c)/CLOCKS_PER_SEC << " second(s) " << endl;

c = clock();
cout << "-- compute_iterator : " << endl;
compute_iterator( K, N );
cout << cI << " solution(s)" << endl;
cout << (clock() - c)/CLOCKS_PER_SEC << " second(s) " << endl;

c = clock();
cout << "-- compute_recursif : " << endl;
compute_recursif( K, N );
cout << cR << " solution(s)" << endl;
cout << (clock() - c)/CLOCKS_PER_SEC << " second(s) " << endl;

c = clock();
cout << "-- compute_permutation : " << endl;
compute_permutation( K, N );
cout << (clock() - c)/CLOCKS_PER_SEC << " second(s) " << endl;
}

Vous avez filtré cet utilisateur ! Consultez son message

On Jun 4, 9:45 pm, David Fleury wrote:

Note bien qu'à mon avis, même ma version initiale (qui générait
toutes les permutations, pour en supprimer les dupliqués par la
suite) a probablement une performance adéquate.

oula, faudrait préciser "adéquate"...
sur mon PC il ne vaut plus rien au delà de N = 12

Et si c'est vrai
que les copies pourraient être signifiantes quand on fait 10000
dans 100000, dans la pratique... même sans les copies, ça risque
de craquer. Le nombre de combinaisons dans ce cas déborde un
double, c-à-d qu'il dépasse 1E306. Alors, ce n'est pas en
supprimant une copie de chaîne qu'on va le faire passer dans le
temps (ni en mémoire).

Ta dernière version est bien.
pour le fun, j'ai mesuré avec ça (sauf erreur)
Les meilleurs méthode peuvent aller jusqu'à N = 32, en prenant le
plus mauvais cas ( K = N / 2 )
J'ai gardé juste un calcul du nombre de solutions pour les 4 algos.
(celui avec next_permutation ne peut affiche le nombre de solutions
sans stockage)

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <iterator>

#include <time.h>
using namespace std;

void compute_permutation( int maxSize, int maxPermutation )
{
std::vector< int > ref ;
for ( int i = 1 ; i <= maxPermutation ; ++ i ) {
ref.push_back( i ) ;
}
std::set< std::vector< int > > result ;
int v = 0;
do {
std::vector< int > combi( ref.begin(), ref.begin() + maxSize ) ;
std::sort( combi.begin(), combi.end() ) ;
//result.insert( combi ) ;
} while ( std::next_permutation( ref.begin(), ref.end() ) ) ;
cout << result.size() << " solution(s)" << endl;
}

static int cR = 0;

void compute_recursif( int maxSize, int end, vector< int > v =
vector<int>(), int begin = 0, int currentSize = 0 )
{
if ( currentSize == maxSize ) {
//copy( v.begin(), v.end(), ostream_iterator<int>( cout, " " ) );
//cout << endl;
++cR;
}
else
for ( int i = begin + 1; i <= end; ++i )
{
vector<int> tmp = v;
tmp.push_back( i );
compute_recursif( maxSize, end, tmp, i,currentSize+1 );
}
}

bool increment( vector<int>& value, int maxValue, int maxPermutation )
{
bool hasOverflow = true;
int currentDigit = value.size()-1;

while( hasOverflow && currentDigit >= 0 )
{
hasOverflow = ++value[currentDigit] > ( maxValue - ( maxPermutation
- currentDigit - 1 ) );
if ( !hasOverflow )
for ( int i = currentDigit+1; i < value.size(); ++i )
value[i] = value[i-1] + 1;

--currentDigit;
}
if ( hasOverflow && currentDigit<0 ) return false;

return true;
}

void compute_iteratif( int maxPermutation, int maxValue )
{
vector< int > value;
for ( int i = 1 ; i <= maxPermutation; ++i )
value.push_back( i ) ;

int v = 0;
do {
//copy( value.begin(), value.end(), ostream_iterator<int>( cout, "
" ) );
//cout << endl;
++v;
} while( increment( value, maxValue, maxPermutation ) );

cout << v << " solution(s)" << endl;
}

static int cI = 0;
void
m_from_n_iter(
std::vector< std::vector< int > >&
result,
std::vector< int >& so_far,
std::vector< int >::const_iterator
set_begin,
std::vector< int >::const_iterator
set_end,
int m )
{
if ( so_far.size() == m ) {
//result.push_back( so_far ) ;
cI++;
} else {
int left = m - so_far.size() ;
while ( set_end - set_begin >= left ) {
so_far.push_back( *set_begin ) ;
++ set_begin ;
m_from_n_iter( result, so_far, set_begin, set_end, m ) ;
so_far.pop_back() ;
}
}
}

void
m_from_n(
std::vector< std::vector< int > >& result,
std::vector< int > const& set_of_n, // n == .size()
int m )
{
std::vector< int > so_far ;
m_from_n_iter( result,
so_far,
set_of_n.begin(),
set_of_n.end(),
m ) ;
}

void compute_iterator( int K, int N )
{
std::vector< std::vector< int > > tmp;
std::vector< int > n;
for ( int i = 1; i <= N; ++i )
n.push_back( i );
m_from_n( tmp, n, K );
}

int main()
{
int N = 32;
int K = N / 2;

clock_t c = clock();
cout << "-- compute_iteratif : " << endl;
compute_iteratif( K, N );
cout << (clock() - c)/CLOCKS_PER_SEC << " second(s) " << endl;

c = clock();
cout << "-- compute_iterator : " << endl;
compute_iterator( K, N );
cout << cI << " solution(s)" << endl;
cout << (clock() - c)/CLOCKS_PER_SEC << " second(s) " << endl;

c = clock();
cout << "-- compute_recursif : " << endl;
compute_recursif( K, N );
cout << cR << " solution(s)" << endl;
cout << (clock() - c)/CLOCKS_PER_SEC << " second(s) " << endl;

c = clock();
cout << "-- compute_permutation : " << endl;
compute_permutation( K, N );
cout << (clock() - c)/CLOCKS_PER_SEC << " second(s) " << endl;
}

James Kanze

06/06/2007 à 09:38

On Jun 5, 9:06 pm, David Fleury wrote:

On Jun 4, 9:45 pm, David Fleury wrote:

Note bien qu'à mon avis, même ma version initiale (qui générait
toutes les permutations, pour en supprimer les dupliqués par la
suite) a probablement une performance adéquate.

oula, faudrait préciser "adéquate"...
sur mon PC il ne vaut plus rien au delà de N = 12

Oui. C'est adéquat pour 3 sur 6:-). C'est vrai qu'avec un
algorithme O(n!), ça peut dégrader vite.

Et si c'est vrai
que les copies pourraient être signifiantes quand on fait 10000
dans 100000, dans la pratique... même sans les copies, ça risque
de craquer. Le nombre de combinaisons dans ce cas déborde un
double, c-à-d qu'il dépasse 1E306. Alors, ce n'est pas en
supprimant une copie de chaîne qu'on va le faire passer dans le
temps (ni en mémoire).

Ta dernière version est bien.
pour le fun, j'ai mesuré avec ça (sauf erreur)
Les meilleurs méthode peuvent aller jusqu'à N = 32, en prenant le
plus mauvais cas ( K = N / 2 )
J'ai gardé juste un calcul du nombre de solutions pour les 4 algos.
(celui avec next_permutation ne peut affiche le nombre de solutions
sans stockage)

Est-ce que le problème, c'est la mémoire, ou le temps
d'exécution ? Parce que j'imagine qu'en stockant les solutions,
on arrive assez vite à épuiser la mémoire aussi. (Ou à épuiser
la mémoire vive, et à se mettre à paginer comme un fou.) C'est
certainement un problème avec ma première solution, où on stocke
d'abord toutes les n! permutations. Pour N = 6, il n'y a que
720 ; pas de problème en vue, mais déjà avec N = 10, il y en a
plus de 3 millions, et à N = 13, on dépasse la capacité
d'adressage sur une machine 32 bits. (J'ai une machine 64 bits
sous la main, mais elle n'est configurée qu'avec 1 Go de mémoire
virtuelle. Alors, elle s'arrête déjà à N = 11 avec mon premier
algorithme. Qui tourne aussi extrèmement lentement, à cause du
paging. Mais tant que je reste dans la mémoire physique, les
temps d'exécution sont « adéquate », et ceci sur un très
vieille et très lente Sparc.)

--
James Kanze (GABI Software) email:
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

On Jun 5, 9:06 pm, David Fleury <dfleu...@libertysurf.fr> wrote:

On Jun 4, 9:45 pm, David Fleury <dfleu...@libertysurf.fr> wrote:

Note bien qu'à mon avis, même ma version initiale (qui générait
toutes les permutations, pour en supprimer les dupliqués par la
suite) a probablement une performance adéquate.

oula, faudrait préciser "adéquate"...
sur mon PC il ne vaut plus rien au delà de N = 12

Oui. C'est adéquat pour 3 sur 6:-). C'est vrai qu'avec un
algorithme O(n!), ça peut dégrader vite.

Et si c'est vrai
que les copies pourraient être signifiantes quand on fait 10000
dans 100000, dans la pratique... même sans les copies, ça risque
de craquer. Le nombre de combinaisons dans ce cas déborde un
double, c-à-d qu'il dépasse 1E306. Alors, ce n'est pas en
supprimant une copie de chaîne qu'on va le faire passer dans le
temps (ni en mémoire).

Ta dernière version est bien.
pour le fun, j'ai mesuré avec ça (sauf erreur)
Les meilleurs méthode peuvent aller jusqu'à N = 32, en prenant le
plus mauvais cas ( K = N / 2 )
J'ai gardé juste un calcul du nombre de solutions pour les 4 algos.
(celui avec next_permutation ne peut affiche le nombre de solutions
sans stockage)

Est-ce que le problème, c'est la mémoire, ou le temps
d'exécution ? Parce que j'imagine qu'en stockant les solutions,
on arrive assez vite à épuiser la mémoire aussi. (Ou à épuiser
la mémoire vive, et à se mettre à paginer comme un fou.) C'est
certainement un problème avec ma première solution, où on stocke
d'abord toutes les n! permutations. Pour N = 6, il n'y a que
720 ; pas de problème en vue, mais déjà avec N = 10, il y en a
plus de 3 millions, et à N = 13, on dépasse la capacité
d'adressage sur une machine 32 bits. (J'ai une machine 64 bits
sous la main, mais elle n'est configurée qu'avec 1 Go de mémoire
virtuelle. Alors, elle s'arrête déjà à N = 11 avec mon premier
algorithme. Qui tourne aussi extrèmement lentement, à cause du
paging. Mais tant que je reste dans la mémoire physique, les
temps d'exécution sont « adéquate », et ceci sur un très
vieille et très lente Sparc.)

--
James Kanze (GABI Software) email:james.kanze@gmail.com
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

Vous avez filtré cet utilisateur ! Consultez son message

On Jun 5, 9:06 pm, David Fleury wrote:

On Jun 4, 9:45 pm, David Fleury wrote:

Note bien qu'à mon avis, même ma version initiale (qui générait
toutes les permutations, pour en supprimer les dupliqués par la
suite) a probablement une performance adéquate.

oula, faudrait préciser "adéquate"...
sur mon PC il ne vaut plus rien au delà de N = 12

Oui. C'est adéquat pour 3 sur 6:-). C'est vrai qu'avec un
algorithme O(n!), ça peut dégrader vite.

Et si c'est vrai
que les copies pourraient être signifiantes quand on fait 10000
dans 100000, dans la pratique... même sans les copies, ça risque
de craquer. Le nombre de combinaisons dans ce cas déborde un
double, c-à-d qu'il dépasse 1E306. Alors, ce n'est pas en
supprimant une copie de chaîne qu'on va le faire passer dans le
temps (ni en mémoire).

Ta dernière version est bien.
pour le fun, j'ai mesuré avec ça (sauf erreur)
Les meilleurs méthode peuvent aller jusqu'à N = 32, en prenant le
plus mauvais cas ( K = N / 2 )
J'ai gardé juste un calcul du nombre de solutions pour les 4 algos.
(celui avec next_permutation ne peut affiche le nombre de solutions
sans stockage)

Est-ce que le problème, c'est la mémoire, ou le temps
d'exécution ? Parce que j'imagine qu'en stockant les solutions,
on arrive assez vite à épuiser la mémoire aussi. (Ou à épuiser
la mémoire vive, et à se mettre à paginer comme un fou.) C'est
certainement un problème avec ma première solution, où on stocke
d'abord toutes les n! permutations. Pour N = 6, il n'y a que
720 ; pas de problème en vue, mais déjà avec N = 10, il y en a
plus de 3 millions, et à N = 13, on dépasse la capacité
d'adressage sur une machine 32 bits. (J'ai une machine 64 bits
sous la main, mais elle n'est configurée qu'avec 1 Go de mémoire
virtuelle. Alors, elle s'arrête déjà à N = 11 avec mon premier
algorithme. Qui tourne aussi extrèmement lentement, à cause du
paging. Mais tant que je reste dans la mémoire physique, les
temps d'exécution sont « adéquate », et ceci sur un très
vieille et très lente Sparc.)

--
James Kanze (GABI Software) email:
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

David Fleury

06/06/2007 à 20:29

Est-ce que le problème, c'est la mémoire, ou le temps
d'exécution ? Parce que j'imagine qu'en stockant les solutions,
on arrive assez vite à épuiser la mémoire aussi. (Ou à épuiser
la mémoire vive, et à se mettre à paginer comme un fou.) C'est
certainement un problème avec ma première solution, où on stocke
d'abord toutes les n! permutations. Pour N = 6, il n'y a que
720 ; pas de problème en vue, mais déjà avec N = 10, il y en a
plus de 3 millions, et à N = 13, on dépasse la capacité
d'adressage sur une machine 32 bits. (J'ai une machine 64 bits
sous la main, mais elle n'est configurée qu'avec 1 Go de mémoire
virtuelle. Alors, elle s'arrête déjà à N = 11 avec mon premier
algorithme. Qui tourne aussi extrèmement lentement, à cause du
paging. Mais tant que je reste dans la mémoire physique, les
temps d'exécution sont « adéquate », et ceci sur un très
vieille et très lente Sparc.)

Le temps d'exécution n'est pas bon.. J'ai supprimé le stockage des
solutions. Seules la génération (next_permutation) et le tri pénalise le
premier traitement.

Pour les pires cas si K = N, l'algo génére N! permutations alors qu'une
seule est valide. Pour N = 10, ça fait quand même presque 4.10e6 tris
inutiles.

David.

alex

06/06/2007 à 22:14

"Mathias Gaunard" a écrit dans le message de news:
466029fc$0$5608$

c'est rigolo il me semble qu'il y a à peu près un an le même problème
était posé.
Un TD repris d'une année sur l'autre et toujours mal compris ;-) ?

Je croyais que c'était la même personne qui n'avait toujours pas trouvé de
réponse au problème.

alors peut-être un redoublant ;-) ??

James Kanze

07/06/2007 à 08:47

On Jun 6, 8:29 pm, David Fleury wrote:

Est-ce que le problème, c'est la mémoire, ou le temps
d'exécution ? Parce que j'imagine qu'en stockant les solutions,
on arrive assez vite à épuiser la mémoire aussi. (Ou à épuis er
la mémoire vive, et à se mettre à paginer comme un fou.) C'est
certainement un problème avec ma première solution, où on stocke
d'abord toutes les n! permutations. Pour N = 6, il n'y a que
720 ; pas de problème en vue, mais déjà avec N = 10, il y en a
plus de 3 millions, et à N = 13, on dépasse la capacité
d'adressage sur une machine 32 bits. (J'ai une machine 64 bits
sous la main, mais elle n'est configurée qu'avec 1 Go de mémoire
virtuelle. Alors, elle s'arrête déjà à N = 11 avec mon premier
algorithme. Qui tourne aussi extrèmement lentement, à cause du
paging. Mais tant que je reste dans la mémoire physique, les
temps d'exécution sont « adéquate », et ceci sur un très
vieille et très lente Sparc.)

Le temps d'exécution n'est pas bon.. J'ai supprimé le stockage des
solutions. Seules la génération (next_permutation) et le tri pénali se le
premier traitement.

Pour les pires cas si K = N, l'algo génére N! permutations alors qu 'une
seule est valide. Pour N = 10, ça fait quand même presque 4.10e6 tr is
inutiles.

Effectivement. J'ai fait quelques essais moi-même, en stockant
les résultats dans un std::set (qui supprime les dupliqués au
fur et à mesure). Pour N = 6, les deux solutions que j'ai
proposées prenent toutes les deux trop peu de temps pour
mesurer. (J'utilisais simplement la commande « time » de
Solaris, qui est assez limitée en ce qui concerne la
résolution.) Pour N = 8, on constatait une nette différence.
Pour N = 10, on voyait déjà le rétard dans la première solution
à l'oeil nu : environ 8 sécondes. Pour N = 10, j'ai aborté
après cinq minutes, sans qu'elle avait fini. Or que le temps
pour la deuxième solution se mesurait encore in centaines de
millisecondes.

Enfin, j'avais bien dit lorsque j'ai posté la première qu'elle
n'était peut-être pas de plus performante:-). Je l'avais essayé
pour 3 sur 6, et ça allait. Mais c'est incroyable à quelle
vitesse un algorithme O(n!) cesse d'aller.

--
James Kanze (GABI Software) email:
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

On Jun 6, 8:29 pm, David Fleury <dfleu...@libertysurf.fr> wrote:

Est-ce que le problème, c'est la mémoire, ou le temps
d'exécution ? Parce que j'imagine qu'en stockant les solutions,
on arrive assez vite à épuiser la mémoire aussi. (Ou à épuis er
la mémoire vive, et à se mettre à paginer comme un fou.) C'est
certainement un problème avec ma première solution, où on stocke
d'abord toutes les n! permutations. Pour N = 6, il n'y a que
720 ; pas de problème en vue, mais déjà avec N = 10, il y en a
plus de 3 millions, et à N = 13, on dépasse la capacité
d'adressage sur une machine 32 bits. (J'ai une machine 64 bits
sous la main, mais elle n'est configurée qu'avec 1 Go de mémoire
virtuelle. Alors, elle s'arrête déjà à N = 11 avec mon premier
algorithme. Qui tourne aussi extrèmement lentement, à cause du
paging. Mais tant que je reste dans la mémoire physique, les
temps d'exécution sont « adéquate », et ceci sur un très
vieille et très lente Sparc.)

Le temps d'exécution n'est pas bon.. J'ai supprimé le stockage des
solutions. Seules la génération (next_permutation) et le tri pénali se le
premier traitement.

Pour les pires cas si K = N, l'algo génére N! permutations alors qu 'une
seule est valide. Pour N = 10, ça fait quand même presque 4.10e6 tr is
inutiles.

Effectivement. J'ai fait quelques essais moi-même, en stockant
les résultats dans un std::set (qui supprime les dupliqués au
fur et à mesure). Pour N = 6, les deux solutions que j'ai
proposées prenent toutes les deux trop peu de temps pour
mesurer. (J'utilisais simplement la commande « time » de
Solaris, qui est assez limitée en ce qui concerne la
résolution.) Pour N = 8, on constatait une nette différence.
Pour N = 10, on voyait déjà le rétard dans la première solution
à l'oeil nu : environ 8 sécondes. Pour N = 10, j'ai aborté
après cinq minutes, sans qu'elle avait fini. Or que le temps
pour la deuxième solution se mesurait encore in centaines de
millisecondes.

Enfin, j'avais bien dit lorsque j'ai posté la première qu'elle
n'était peut-être pas de plus performante:-). Je l'avais essayé
pour 3 sur 6, et ça allait. Mais c'est incroyable à quelle
vitesse un algorithme O(n!) cesse d'aller.

--
James Kanze (GABI Software) email:james.kanze@gmail.com
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

Vous avez filtré cet utilisateur ! Consultez son message

On Jun 6, 8:29 pm, David Fleury wrote:

Est-ce que le problème, c'est la mémoire, ou le temps
d'exécution ? Parce que j'imagine qu'en stockant les solutions,
on arrive assez vite à épuiser la mémoire aussi. (Ou à épuis er
la mémoire vive, et à se mettre à paginer comme un fou.) C'est
certainement un problème avec ma première solution, où on stocke
d'abord toutes les n! permutations. Pour N = 6, il n'y a que
720 ; pas de problème en vue, mais déjà avec N = 10, il y en a
plus de 3 millions, et à N = 13, on dépasse la capacité
d'adressage sur une machine 32 bits. (J'ai une machine 64 bits
sous la main, mais elle n'est configurée qu'avec 1 Go de mémoire
virtuelle. Alors, elle s'arrête déjà à N = 11 avec mon premier
algorithme. Qui tourne aussi extrèmement lentement, à cause du
paging. Mais tant que je reste dans la mémoire physique, les
temps d'exécution sont « adéquate », et ceci sur un très
vieille et très lente Sparc.)

Le temps d'exécution n'est pas bon.. J'ai supprimé le stockage des
solutions. Seules la génération (next_permutation) et le tri pénali se le
premier traitement.

Pour les pires cas si K = N, l'algo génére N! permutations alors qu 'une
seule est valide. Pour N = 10, ça fait quand même presque 4.10e6 tr is
inutiles.

Effectivement. J'ai fait quelques essais moi-même, en stockant
les résultats dans un std::set (qui supprime les dupliqués au
fur et à mesure). Pour N = 6, les deux solutions que j'ai
proposées prenent toutes les deux trop peu de temps pour
mesurer. (J'utilisais simplement la commande « time » de
Solaris, qui est assez limitée en ce qui concerne la
résolution.) Pour N = 8, on constatait une nette différence.
Pour N = 10, on voyait déjà le rétard dans la première solution
à l'oeil nu : environ 8 sécondes. Pour N = 10, j'ai aborté
après cinq minutes, sans qu'elle avait fini. Or que le temps
pour la deuxième solution se mesurait encore in centaines de
millisecondes.

Enfin, j'avais bien dit lorsque j'ai posté la première qu'elle
n'était peut-être pas de plus performante:-). Je l'avais essayé
pour 3 sur 6, et ça allait. Mais c'est incroyable à quelle
vitesse un algorithme O(n!) cesse d'aller.

--
James Kanze (GABI Software) email:
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

Michael DOUBEZ

08/06/2007 à 09:28

On Jun 4, 9:45 pm, David Fleury wrote:

Note bien qu'à mon avis, même ma version initiale (qui générait
toutes les permutations, pour en supprimer les dupliqués par la
suite) a probablement une performance adéquate.

oula, faudrait préciser "adéquate"...
sur mon PC il ne vaut plus rien au delà de N = 12

Et si c'est vrai
que les copies pourraient être signifiantes quand on fait 10000
dans 100000, dans la pratique... même sans les copies, ça risque
de craquer. Le nombre de combinaisons dans ce cas déborde un
double, c-à-d qu'il dépasse 1E306. Alors, ce n'est pas en
supprimant une copie de chaîne qu'on va le faire passer dans le
temps (ni en mémoire).

Ta dernière version est bien.
pour le fun, j'ai mesuré avec ça (sauf erreur)
Les meilleurs méthode peuvent aller jusqu'à N = 32, en prenant le
plus mauvais cas ( K = N / 2 )
J'ai gardé juste un calcul du nombre de solutions pour les 4 algos.
(celui avec next_permutation ne peut affiche le nombre de solutions
sans stockage)
[snip code]

En travaillant sur les index, on peut faire une version iterative à
occupation mémoire constante mais l'algo passe de n! à (n+1)!.

void combinaison_m_of_n(int m, int n)
{
if( m>n)
{ //combinaison impossible
return;
}

//combinaison d'index
std::vector<int> indexes(m);
//context d'iteration
int i;

//initialisation de l'algo
i=0;
indexes[0]=-1;

while(i>=0)
{
if(indexes[i]<n-m+i)
{ //peut générer une solution en incrémentant un index
++indexes[i];
//génère index suivant minimaux
while(i<m-1)
{
++i;
indexes[i]=indexes[i-1]+1;
}

//NOUVELLE COMBINAISON
std::copy (indexes.begin(),
indexes.end(),
std::ostream_iterator<int>(std::cout));
std::cout<<std::endl;
}
else
{ //ne peut pas générére de nouvelle solution avec l'index
courant
// va voir les index plus petit
--i;
}
}
}

Michael DOUBEZ

08/06/2007 à 12:38

On Jun 4, 9:45 pm, David Fleury wrote:

Note bien qu'à mon avis, même ma version initiale (qui générait
toutes les permutations, pour en supprimer les dupliqués par la
suite) a probablement une performance adéquate.

oula, faudrait préciser "adéquate"...
sur mon PC il ne vaut plus rien au delà de N = 12

Et si c'est vrai
que les copies pourraient être signifiantes quand on fait 10000
dans 100000, dans la pratique... même sans les copies, ça risque
de craquer. Le nombre de combinaisons dans ce cas déborde un
double, c-à-d qu'il dépasse 1E306. Alors, ce n'est pas en
supprimant une copie de chaîne qu'on va le faire passer dans le
temps (ni en mémoire).

Ta dernière version est bien.
pour le fun, j'ai mesuré avec ça (sauf erreur)
Les meilleurs méthode peuvent aller jusqu'à N = 32, en prenant le
plus mauvais cas ( K = N / 2 )
J'ai gardé juste un calcul du nombre de solutions pour les 4 algos.
(celui avec next_permutation ne peut affiche le nombre de solutions
sans stockage)
[snip code]

En travaillant sur les index, on peut faire une version iterative à
occupation mémoire constante mais l'algo passe de n! à (n+1)!.

J'ai beau chercher, je n'arrive pas à trouver un algo recurssif
terminal. Le meilleur reccurssif (de profondeur max N equivalent à
l'iteratif mais en O(n!)) auquel je peux penser est:

//return combinaison starting at index in range [minval;maxval[
void combi_req_index(int index,int m, int minval, int maxval,
vector<int> indexes)
{
for(;minval<maxval;++minval)
{
indexes[index]=minval;
if(index<m-1)
{
combi_req_index(index+1,m,minval+1,maxval-1,indexes)
}
else
{
//SOLUTION
std::copy (indexes.begin(),
indexes.end(),
std::ostream_iterator<int>(std::cout));
std::cout<<std::endl;
}
}
}

void combinaison_m_of_n(int m, int n)
{
if( m>n)
{ //combinaison impossible
return;
}

//combinaison d'index
std::vector<int> indexes(m);
//return combinaison statring at index 0
combi_req_index(0,m,0,n-m,indexes);
}

On Jun 4, 9:45 pm, David Fleury <dfleu...@libertysurf.fr> wrote:

Note bien qu'à mon avis, même ma version initiale (qui générait
toutes les permutations, pour en supprimer les dupliqués par la
suite) a probablement une performance adéquate.

oula, faudrait préciser "adéquate"...
sur mon PC il ne vaut plus rien au delà de N = 12

Et si c'est vrai
que les copies pourraient être signifiantes quand on fait 10000
dans 100000, dans la pratique... même sans les copies, ça risque
de craquer. Le nombre de combinaisons dans ce cas déborde un
double, c-à-d qu'il dépasse 1E306. Alors, ce n'est pas en
supprimant une copie de chaîne qu'on va le faire passer dans le
temps (ni en mémoire).

Ta dernière version est bien.
pour le fun, j'ai mesuré avec ça (sauf erreur)
Les meilleurs méthode peuvent aller jusqu'à N = 32, en prenant le
plus mauvais cas ( K = N / 2 )
J'ai gardé juste un calcul du nombre de solutions pour les 4 algos.
(celui avec next_permutation ne peut affiche le nombre de solutions
sans stockage)
[snip code]

En travaillant sur les index, on peut faire une version iterative à
occupation mémoire constante mais l'algo passe de n! à (n+1)!.

J'ai beau chercher, je n'arrive pas à trouver un algo recurssif
terminal. Le meilleur reccurssif (de profondeur max N equivalent à
l'iteratif mais en O(n!)) auquel je peux penser est:

//return combinaison starting at index in range [minval;maxval[
void combi_req_index(int index,int m, int minval, int maxval,
vector<int> indexes)
{
for(;minval<maxval;++minval)
{
indexes[index]=minval;
if(index<m-1)
{
combi_req_index(index+1,m,minval+1,maxval-1,indexes)
}
else
{
//SOLUTION
std::copy (indexes.begin(),
indexes.end(),
std::ostream_iterator<int>(std::cout));
std::cout<<std::endl;
}
}
}

void combinaison_m_of_n(int m, int n)
{
if( m>n)
{ //combinaison impossible
return;
}

//combinaison d'index
std::vector<int> indexes(m);
//return combinaison statring at index 0
combi_req_index(0,m,0,n-m,indexes);
}

David Fleury

09/06/2007 à 17:11

En travaillant sur les index, on peut faire une version iterative à
occupation mémoire constante mais l'algo passe de n! à (n+1)!.

Ta version itérative est diablement efficace en tout cas.
Je la note dans un coin de ma tête. ;)

J'ai beau chercher, je n'arrive pas à trouver un algo recurssif
terminal. Le meilleur reccurssif (de profondeur max N equivalent à
l'iteratif mais en O(n!)) auquel je peux penser est:

espie

09/06/2007 à 22:05

A l'epoque lointaine ou je generais des tonnes de permutations pour leur
faire subir des choses immondes, la premiere question a se poser, c'etait:
est-ce qu'on a besoin d'avoir les permutations dans l'ordre ?

ou est-ce qu'on se preoccupe juste de sortir chaque solution une seule
fois ?

(je n'ai jamais compris pourquoi la STL ne possedait QUE l'algo complique
qui sort TOUTES les permutations dans l'ordre).

Si on se fiche de l'ordre dans lequel on obtient les resultats, les
solutions les plus efficaces se basent sur un tableau de toutes
les entrees (initialement triee), et d'echanges sur les divers elements.

Ca fait une solution recursive simple, qui peut facilement devenir
iterative en explicitant la pile, de type generateur.

En tres vite, ca donne ceci, pour sortir toutes les permutations dans
n'importe quel ordre (et sans specialement optimiser, c'est juste le concept).

#include <vector>
#include <iostream>

void
display(const std::vector<int> &t)
{
int n = t.size();
for (int i = 0; i < n; i++)
std::cout << t[i] << " ";
std::cout << "n";
}

void
permute(std::vector<int> &t, int i)
{
int n = t.size();
if (i >= n) {
display(t);
} else {
for (int j = i; j < n; j++) {
std::swap(t[i], t[j]);
permute(t, i+1);
}
}
}

void
init(std::vector<int> &t, int n)
{
t.resize(n);
for (int i = 0; i < n; i++) {
t[i] = i+1;
}
}

int
main()
{
std::vector<int> t;
init(t, 6);
permute(t, 0);
}

(mes excuses aux familles pour non-utilisation de toutes les possibilites
de la STL, je fais plus de perl que de C++ ces temps-ci...)

espie

09/06/2007 à 22:18

In article <f4f15u$1q3f$,
Marc Espie wrote:

A l'epoque lointaine ou je generais des tonnes de permutations pour leur
faire subir des choses immondes, la premiere question a se poser, c'etait:
est-ce qu'on a besoin d'avoir les permutations dans l'ordre ?

ou est-ce qu'on se preoccupe juste de sortir chaque solution une seule
fois ?

(je n'ai jamais compris pourquoi la STL ne possedait QUE l'algo complique
qui sort TOUTES les permutations dans l'ordre).

Si on se fiche de l'ordre dans lequel on obtient les resultats, les
solutions les plus efficaces se basent sur un tableau de toutes
les entrees (initialement triee), et d'echanges sur les divers elements.

Ca fait une solution recursive simple, qui peut facilement devenir
iterative en explicitant la pile, de type generateur.

En tres vite, ca donne ceci, pour sortir toutes les permutations dans
n'importe quel ordre (et sans specialement optimiser, c'est juste le concept).

Je savais bien que j'avais oublie un truc (penser a refaire un swap
au retour de permute).

Version revue et corrigee, qui resoud exactement le probleme de depart,
i.e., les permutations partielles. Juste avec de la combi, sans besoin
de stockage supplementaire.

En terme de complexite, c'est optimal: en temps, l'algo est lineaire
par rapport a la taille de la sortie. En espace, on utilise un
tableau de n elements, et d'une pile d'appels de profondeur n-k, donc
lineaire par rapport a la taille de l'entree.

L'algo ne se generalise pas simplement aux cas ou on voudrait generer
des permutations partielles qui contiennent plusieurs fois le meme
element...

#include <vector>
#include <iostream>

void
display(const std::vector<int> &t, int k)
{
int n = t.size();
for (int i = 0; i < k; i++)
std::cout << t[i] << " ";
std::cout << "n";
}

void
permute(std::vector<int> &t, int i, int k)
{
int n = t.size();
if (i >= k) {
display(t, k);
} else {
for (int j = i; j < n; j++) {
std::swap(t[i], t[j]);
permute(t, i+1, k);
std::swap(t[i], t[j]);
}
}
}

void
init(std::vector<int> &t, int n)
{
t.resize(n);
for (int i = 0; i < n; i++) {
t[i] = i+1;
}
}

int
main()
{
std::vector<int> t;
init(t, 6);
permute(t, 0, 3);
}

In article <f4f15u$1q3f$1@biggoron.nerim.net>,
Marc Espie <espie@nerim.net> wrote:

A l'epoque lointaine ou je generais des tonnes de permutations pour leur
faire subir des choses immondes, la premiere question a se poser, c'etait:
est-ce qu'on a besoin d'avoir les permutations dans l'ordre ?

ou est-ce qu'on se preoccupe juste de sortir chaque solution une seule
fois ?

(je n'ai jamais compris pourquoi la STL ne possedait QUE l'algo complique
qui sort TOUTES les permutations dans l'ordre).

Si on se fiche de l'ordre dans lequel on obtient les resultats, les
solutions les plus efficaces se basent sur un tableau de toutes
les entrees (initialement triee), et d'echanges sur les divers elements.

Ca fait une solution recursive simple, qui peut facilement devenir
iterative en explicitant la pile, de type generateur.

En tres vite, ca donne ceci, pour sortir toutes les permutations dans
n'importe quel ordre (et sans specialement optimiser, c'est juste le concept).

Je savais bien que j'avais oublie un truc (penser a refaire un swap
au retour de permute).

Version revue et corrigee, qui resoud exactement le probleme de depart,
i.e., les permutations partielles. Juste avec de la combi, sans besoin
de stockage supplementaire.

En terme de complexite, c'est optimal: en temps, l'algo est lineaire
par rapport a la taille de la sortie. En espace, on utilise un
tableau de n elements, et d'une pile d'appels de profondeur n-k, donc
lineaire par rapport a la taille de l'entree.

L'algo ne se generalise pas simplement aux cas ou on voudrait generer
des permutations partielles qui contiennent plusieurs fois le meme
element...

#include <vector>
#include <iostream>

void
display(const std::vector<int> &t, int k)
{
int n = t.size();
for (int i = 0; i < k; i++)
std::cout << t[i] << " ";
std::cout << "n";
}

void
permute(std::vector<int> &t, int i, int k)
{
int n = t.size();
if (i >= k) {
display(t, k);
} else {
for (int j = i; j < n; j++) {
std::swap(t[i], t[j]);
permute(t, i+1, k);
std::swap(t[i], t[j]);
}
}
}

void
init(std::vector<int> &t, int n)
{
t.resize(n);
for (int i = 0; i < n; i++) {
t[i] = i+1;
}
}

int
main()
{
std::vector<int> t;
init(t, 6);
permute(t, 0, 3);
}

Vous avez filtré cet utilisateur ! Consultez son message

In article <f4f15u$1q3f$,
Marc Espie wrote:

A l'epoque lointaine ou je generais des tonnes de permutations pour leur
faire subir des choses immondes, la premiere question a se poser, c'etait:
est-ce qu'on a besoin d'avoir les permutations dans l'ordre ?

ou est-ce qu'on se preoccupe juste de sortir chaque solution une seule
fois ?

(je n'ai jamais compris pourquoi la STL ne possedait QUE l'algo complique
qui sort TOUTES les permutations dans l'ordre).

Si on se fiche de l'ordre dans lequel on obtient les resultats, les
solutions les plus efficaces se basent sur un tableau de toutes
les entrees (initialement triee), et d'echanges sur les divers elements.

Ca fait une solution recursive simple, qui peut facilement devenir
iterative en explicitant la pile, de type generateur.

En tres vite, ca donne ceci, pour sortir toutes les permutations dans
n'importe quel ordre (et sans specialement optimiser, c'est juste le concept).

Je savais bien que j'avais oublie un truc (penser a refaire un swap
au retour de permute).

Version revue et corrigee, qui resoud exactement le probleme de depart,
i.e., les permutations partielles. Juste avec de la combi, sans besoin
de stockage supplementaire.

En terme de complexite, c'est optimal: en temps, l'algo est lineaire
par rapport a la taille de la sortie. En espace, on utilise un
tableau de n elements, et d'une pile d'appels de profondeur n-k, donc
lineaire par rapport a la taille de l'entree.

L'algo ne se generalise pas simplement aux cas ou on voudrait generer
des permutations partielles qui contiennent plusieurs fois le meme
element...

#include <vector>
#include <iostream>

void
display(const std::vector<int> &t, int k)
{
int n = t.size();
for (int i = 0; i < k; i++)
std::cout << t[i] << " ";
std::cout << "n";
}

void
permute(std::vector<int> &t, int i, int k)
{
int n = t.size();
if (i >= k) {
display(t, k);
} else {
for (int j = i; j < n; j++) {
std::swap(t[i], t[j]);
permute(t, i+1, k);
std::swap(t[i], t[j]);
}
}
}

void
init(std::vector<int> &t, int n)
{
t.resize(n);
for (int i = 0; i < n; i++) {
t[i] = i+1;
}
}

int
main()
{
std::vector<int> t;
init(t, 6);
permute(t, 0, 3);
}

comment reduire ca

10 réponses

Veuillez sélectionner un problème