Discussion :

[girmaxime]

Bonjour à toutes et à tous,

je suis en train de faire un cours sur le codage, et pour cela, je cherche à créer l'ensemble des string à 4 lettres minuscules de a à z, sous scilab 5.4.1 32 bits.

Voici mon code:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
clear
clc
alphabet=('abcdefghijklmnopqrstuvwxyz');
 
 
tic()
for i=1:26
    v(i)=part(alphabet,i);
end
toc()
 
k=1;
tic()
for a=1:26
    for b=1:26
        for c=1:26
            for d=1:26
                w(k)=v(a)+v(b)+v(c)+v(d);
                k=k+1;
            end
        end
    end
end
toc()

Mon problème est le suivant: le temps de calcul est beaucoup trop long, du coup j'ai fait varier a de 1 à 1 (environ 3s ), puis de 1 à 3 (environ 28 s) puis de 1 à 6 (environ 120s).

Plus a varie plus le temps de calcul est long, mais le temps de calcul est exponentiel, alors qu'en toute logique il devrait être proportionnel.

D'où mes questions:
y a t il une erreur dans mon code, ou en tout cas une façon de programmer que scilab n'aime pas?
y aurait-il une façon plus simple de générer l'ensemble de ces mots (aaaa,aaab,aaac...)?
Mais pourquoi donc le temps de calcul n'est pas proportionnel, qu'il y ait de petites différences, en fonction de la charge CPU etc, je veux bien, mais la je ne comprends pas?

Merci, Maxime.

[Jerome Briot]

Les boucle sont à éviter dans ce genre de problème car la variable w change de taille à chaque itération, ce qui nuit généralement aux performances du code.
Je maîtrise mieux ce sujet avec MATLAB, mais je pense que Scilab réagit de la même façon.

Voici une version plus efficace qui se base sur l'analyse des permutations dans le tableau final :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
clear
clc
 
alphabet = 'abcdefghijklmnopqrstuvwxyz';
 
N = length(alphabet);
 
tic();
for i = 1:N
    v(1,i) = part(alphabet, i);
end
t = toc();
 
disp(t)
 
tic();
 
d = repmat(v, 1, N*N*N);
 
c = repmat(v, N, 1);
c = repmat(c, 1, N*N);
 
b = repmat(v, N*N, 1);
b = repmat(b, 1, N);
 
a = repmat(v, N*N*N, 1);
 
w = a(:) + b(:) + c(:) + d(:);
 
t = toc();
 
disp(t)

A tester…

[girmaxime]

ca marche!!!

merci beaucoup pour cette réponse, ca marche impeccable.
Effectivement, pour les boucles for, je devrais définir au préalable la taille de ma matrice w, cela devrait mieux marcher.

Mais ta méthode m'a beaucoup plu.

Du coup ci-joint le code optimisé pour marcher quelle que soit la taille de l'alphabet.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
clear
clc
 
//alphabet = 'abcdefghijklmnopqrstuvwxyz';
alphabet = 'abcdef';
N = length(alphabet);
 
tic();
for i = 1:N
    v(1,i) = part(alphabet, i);
end
t = toc();
disp(t)
 
 
 
 
tic();
for i=1:N
    u(:,:,i)=repmat(v,N^(i-1),N^(N-i));
end
 
w=[];
for j=1:N
    w=w+u(:,:,N-j+1);
end
w=w';
 
t = toc();
disp(t)

Bon certes au dela de 6 lettres dans l'alphabet, un problème de pile (stacksize) apparait, mais ça, c'est un autre problème...

Et aussi merci pour les Cours et tutoriels pour apprendre Scilab