Discussion :

[AnozerOne]

Admettons que j'ai une suite de 100 entiers, de 1 à 100.

Lorsque je le désire, je retire un de ces entiers de la suite pour la mettre dans une autre (peu m'importe le nombre choisi).
Y'a t'il moyen de définir un alogrithme pour transformer en un entier exploitable la suite de nombres ?

Quand je dis suite il n'est pas nécessaire que les nombres soient rangés par ordre croissant ou décroissant, ni même ordonnés d'une façon quelquonque.

Comme je me rend compte que je ne suis pas clair je vais faire un petit exemple :

Pour faire plus simple je prendrais une suite de 5 nombres

Au départ la suite 1 contient tous les nombres rangés par ordre croissant et la suite 2 ne contient aucun nombre

Code :

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

1
2
3
4
suite 1
1,2,3,4,5
 
suite 2

Je prends le nombre 1 de la suite 1

Code :

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

1
2
3
4
5
suite 1
2,3,4,5
 
suite 2
1

Je prends le nombre 2 de la suite 1

Code :

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

1
2
3
4
5
suite 1
3,4,5
 
suite 2
1,2

Je prends le nombre 3 de la suite 1

Code :

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

1
2
3
4
5
suite 1
4,5
 
suite 2
1,2,3

Je remet le nombre 2 dans la suite 1

Code :

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

1
2
3
4
5
suite 1
4,5,2
 
suite 2
1,3

Je voudrais pour une suite de 100 nombres (de 1 à 100 ) pouvoir effectuer ce genre d'opération.

Notez que dans l'exemple j'ai pris les entiers les plus faible de la liste, mais cela n'a aucune importance, n'importe quel entier de la suite me convient parfaitement.
De même qu'a la fin la suite 1 donne 4;5;2 , si il faut la réordonner pour rendre l'algorithme plus rapide ce n'est pas un souci, je veux dire l'ordre des nombres n'a vraiment aucune importance, seul le fait de pouvoir extraire un nombre quelquonque de la suite 1 ou 2 pour le mettre dans l'autre suite est important.

Ma seule "exigence" est que le code soit le plus optimisé possible

Suis je clair ?

PS : la plage d'un entier est de -2^32 + 1 <= X <= 2^32 - 1

[pseudocode]

Suis je clair ?

Heu... quel est le rapport avec le titre: codage d'une suite de nombres en un entier ?

[AnozerOne]

Comme je m'en doutais je suis aussi limpide qu'une eau marécageuse

En fait les suites sont virtuelles, je n'ai pas la possibilité de faire des suites de nombres.

Donc il me faudrait un algorithme qui puisse convertir une suite en un entier exploitable et inversement.

je ne peux pas me contenter d'utiliser la formule pour les bases : valeur du nombre*B^n car la plage serait trop grande.

Toujours en reprenant mon exemple.

une suite 1,2,3,4,5 donnerait pour entier 975 (1*5^4 + 2*5^3 + 3*5^2 + 4*5^1 +5*5^0).
mais cette méthode en me convient pas étant donné qu'en réalité j'ai une suite de 1 à 100, donc dépassant largement la plage d'un entier

EDIT : Hmm j'ai trouvé une solution bien plus simple
Il suffit d'utiliser 2 variables array entières (les 2 suites), et deux autres variables entières qui déterminent l'index maximum des variables array.
A chaque ajout d'un nombre dans une suite on incrémente l'index maximum de 1 et on on rajoute le nombre dans la variable array avec pour index l'index max.
A chaque retrait d'un nombre dans une suite on remplace la valeur de la variable utilisée par la valeur de la variable avec pour index l'index max.
Puis on décrémente l'index max de 1.

(Me suis comprenu mais si ce n'est pas votre cas je peux éventuellement faire un exemple concret )

[pseudocode]

Hmm j'ai trouvé une solution bien plus simple
Il suffit d'utiliser 2 variables array entières (les 2 suites), et deux autres variables entières qui déterminent l'index maximum des variables array.
A chaque ajout d'un nombre dans une suite on incrémente l'index maximum de 1 et on on rajoute le nombre dans la variable array avec pour index l'index max.
A chaque retrait d'un nombre dans une suite on remplace la valeur de la variable utilisée par la valeur de la variable avec pour index l'index max.
Puis on décrémente l'index max de 1.

C'est dans des cas comme ça qu'on se rend compte que le français n'est pas un bon langage de programmation.

[droggo]

Fio,

EDIT : Hmm j'ai trouvé une solution bien plus simple
Il suffit d'utiliser 2 variables array entières (les 2 suites), et deux autres variables entières qui déterminent l'index maximum des variables array.
A chaque ajout d'un nombre dans une suite on incrémente l'index maximum de 1 et on on rajoute le nombre dans la variable array avec pour index l'index max.
A chaque retrait d'un nombre dans une suite on remplace la valeur de la variable utilisée par la valeur de la variable avec pour index l'index max.
Puis on décrémente l'index max de 1.

(Me suis comprenu mais si ce n'est pas votre cas je peux éventuellement faire un exemple concret )

Ce que tu décris est le fonctionnement d'une pile LIFO (Last In, First Out), et ne correspond pas l'exemple que tu donnais dans ton premier message.

[Jedai]

Pas exactement puisqu'il peut retirer n'importe quel élément de sa "pile", pas seulement l'élément du dessus.
Néanmoins ça a l'air assez inefficace comme méthode... Il est obligé de faire une recherche linéaire à chaque fois qu'il veut retirer un élément donné.
Un tableau de booléens (implémenté par un tableau de bits) serait beaucoup plus efficace.

--
Jedaï

[droggo]

Hie,

Pas exactement puisqu'il peut retirer n'importe quel élément de sa "pile", pas seulement l'élément du dessus.
Néanmoins ça a l'air assez inefficace comme méthode... Il est obligé de faire une recherche linéaire à chaque fois qu'il veut retirer un élément donné.
Un tableau de booléens (implémenté par un tableau de bits) serait beaucoup plus efficace.

--
Jedaï

Autant pour moi, j'avais mal lu.

[AnozerOne]

C'est dans des cas comme ça qu'on se rend compte que le français n'est pas un bon langage de programmation.

Peut être que ceci sera plus clair, cela a été réalisé en Vjass (langage pseudo orienté objet d'un hack de l'éditeur de warcraft3) :

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
library Test initializer Init
 
    globals
        private constant integer MAX = 100 // définit la grandeur de la suite
        private integer array I1 // pile de référence avec les nombres disponibles
        private integer I1Max=MAX // index max de la pile
        private integer array I2 // pile où sont stockés les nombres utilisés
        private integer I2Max=0 // index max de la pile
 
    endglobals
 
    private function Init takes nothing returns nothing // création de la pile
        local integer i=0
 
        loop
        set i=i+1
            set I1[i]=i
        exitwhen i==MAX
        endloop
 
    endfunction
 
    function TakeI1 takes nothing returns integer // on prend un nombre de la pile 1 pour le mettre en pile 2
        local integer i=I1[I1Max]
 
        set I2Max=I2Max+1
        set I2[I2Max]=i
        set I1[I1Max]=0 // pas nécessaire mais bon ...
        set I1Max=I1Max-1
 
        return i
    endfunction
 
    function AddI1 takes integer number returns nothing // on prend un nombre de la pile 2 pour le remettre dans la pile 1
        local integer i=0
 
        set I1Max=I1Max+1
 
        loop
        set i=i+1
        exitwhen number==I2[i] 
        endloop
 
        set I1[I1Max]=I2[i]
        set I2[i]=I2[I2Max]
        set I2[I2Max]=0 // pas nécessaire mais bon ...
        set I2Max=I2Max-1
 
    endfunction
 
    function DisplayI1 takes nothing returns nothing // juste pour afficher les valeurs de la pile 1
        local integer i=0
 
        call BJDebugMsg(" ")
        call BJDebugMsg("I1")
 
        loop
        set i=i+1
            call BJDebugMsg(I2S(I1[i]))
        exitwhen i==I1Max
        endloop
 
    endfunction
 
    function DisplayI2 takes nothing returns nothing // juste pour afficher les valeurs de la pile 2
        local integer i=0
 
        call BJDebugMsg(" ")
        call BJDebugMsg("I2")
 
        loop
        set i=i+1
            call BJDebugMsg(I2S(I2[i]))
        exitwhen i==I2Max
        endloop
 
    endfunction
 
endlibrary

Remarques :
- je sais parfaitement que je n'utilise pas l'index 0, c'est un standard que j'ai choisi, ne me demandez pas pourquoi, c'est inutile.
- je n'ai pas prévu de débug pour la fonction AddI1 car le nombre sera forcément correct dans mon utilisation.
- On peut se demander l'intérêt d'une telle chose, mais croyez moi j'en aurais l'utilité

Néanmoins ça a l'air assez inefficace comme méthode... Il est obligé de faire une recherche linéaire à chaque fois qu'il veut retirer un élément donné.
Un tableau de booléens (implémenté par un tableau de bits) serait beaucoup plus efficace

En effet pour la fonction AddI1 je dois faire une loop pour déterminer dans quel variable est stocké le nombre.
Par contre j'ai du mal à voir l'application de ton idée, pourrait tu me donner la méthode ?

[pseudocode]

En effet pour la fonction AddI1 je dois faire une loop pour déterminer dans quel variable est stocké le nombre.
Par contre j'ai du mal à voir l'application de ton idée, pourrait tu me donner la méthode ?

Je pense que ce que veux dire Jedai c'est que tu n'a pas besoin d'implémenter physiquement les structures Liste1 et Liste2.

Tout ce qu'il te faut c'est un moyen de savoir si un nombre donné est dans Liste1 (et sinon il est forcément dans Liste2). Donc un booléen fait l'affaire.

L'approche naive consisterait a avoir un tableau de booléen de taille 2^32, comme ca on pourrait directement assigner/évaluer l'appartenance d'un entier à la liste L1.

Code :

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

1
2
3
4
5
6
7
 
boolean isL1[2^32];
 
// assigne 123 dans la liste L1
isL1[123]=true;
 
if (isL1[123]) { /* 123 est dans L1 */ } else { /* 123 est dans L2 */ }

Le tableau de taille 2^32 etant un peu gros (), on doit créer un index qui pour chaque entier nous donne un numéro unique (0...100) qu'on va utiliser comme indice dans le tableau de booleen.

Si ton langage est assez évolué, tu dois déja avoir ce genre de structure (map, table de hashage), sinon il faut en implémenter une.

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
 
int MAX=0; // nombre d'entiers stockés actuellement
map<int,int> index;
boolean[100] isL1 ;
 
// si 123 n'est pas dans l'index, on l'y ajoute
if ( index(123) == INCONNU ) {
  MAX=MAX+1
  index(123)=MAX; // MAX est le numero d'index de 123
}
 
// assigne 123 dans la liste L1
isL1[ index(123) ]=true;
 
if (isL1[ index(123) ]) { /* 123 est dans L1 */ } else { /* 123 est dans L2 */ }

[AnozerOne]

Euh ca me semble beaucoup plus lourd, du moins en mémoire utilisée.
Au pire des cas ma loop aura seulement 100 itérations, c'est pas la mort pour une simple comparaison de variables, surtout que ce genre d'action ne sera pas si fréquent.

Je n'ai pas compris pourquoi l'utilisation d'autant de booléens mais la plage d'index d'un tableau va de 0 à 8190 (y'a aussi l'index 8191 mais la carte plantera lors du chargement d'une partie sauvegardée, si on utilise cet index )

Mais si il faut j'ai le game cache à disposition qui me permet de faire des tables à l'index que je veux, il demande 2 chaines de caractères (strings) en paramètre pour écrire/lire une variable, et je dispose des fonctions permettant de convertir un entier en string et inversement, malheureusement celles ci sont lentes.

Toutefois si ca supprime l'utilisation de la boucle pourquoi pas, faut voir.

PS : regardez bien la fonction TakeI1, car je peux me tromper mais je crois que pseudocode n'a pas compris ce que je veux exactement

[Jedai]

Euh ca me semble beaucoup plus lourd, du moins en mémoire utilisée.

Selon le langage dans lequel tu codes, ce genre de structure peut-être implémenté comme un tableau de bits en sous-main, elle est alors nettement plus légère que ta solution actuelle : Même pour 10000 entiers, tu n'aurais pas besoin de plus de 313 mots en mémoire.

--
Jedaï

[AnozerOne]

faut que je teste alors, mais faut surtout que l'on m'explique cette fameuse méthode

[pseudocode]

@Jedai: coder les 2^32 entiers possibles sur des mots de 32 bits ca fait quand meme 4194304 mots.

L'algo de VB_ca_rox me parait plutot bien, surtout si la recherche linéaire ne se fait que sur une centaine de valeurs.

[Jedai]

@Jedai: coder les 2^32 entiers possibles sur des mots de 32 bits ca fait quand meme 4194304 mots.

A priori, il n'a pas besoin de coder tous les entiers possibles, mais seulement une quantité très réduite et dans un intervalle petit. Plus exactement les nombres de 1 à 100, soit 4 mots. En utilisant cette solution, il remplace deux tableaux de 100 mots par 2 tableaux de 4 mots, et lors d'un déplacement il s'épargne un nombre d'opérations non négligeable (disons de l'ordre de 25 lectures et 1 écriture). L'intérêt de la chose dépend de si ce déplacement est une opération très commune ou pas (s'il doit le faire des centaines de fois par secondes il sentira la différence, c'est certain !).

--
Jedaï

[AnozerOne]

Je ne lancerais la fonction AddI1 qu'occasionnellement.
Toutefois je suis toujours à la recherche de la meillleure performance, mais je doute fortement que ta solution soit possible avec le jass.
Comme je ne programme pas vraiment (pas de "vrai" langage) j'ai du mal à te suivre.
Mais si tu pouvais poster le pseudo code, pas le modérateur (oui je sais elle est trop facile), ca serait sympa, car là je reste dans le flou.
Evidemment pour l'exemple tu peux prendre une suite de 1 à 10

[AnozerOne]

Non pas que ca intéresse quelqu'un mais j'ai optimisé le code en supprimant la boucle et je me sens donc obligé de poster le code.
L'avantage est que désormais le temps d'éxécution sera identique quel que soit la taille de la suite.
J'utilise plus de mémoire mais c'est vraiment sans importance.
Je n'ai toujours pas prévu de débug pour le recyclage d'un nombre (fonction AddI1), car j'avais prévu d'utiliser un tableau de booleen pour savoir si le nombre est utilisé ou non mais ca n'est pas suffisant, car dans mon utilisation les nombres représentent en fait des index de tableaux, on pourrait donc par erreur choisir un mauvais index avec une erreur de code.
Bref je pense que l'utilisation de cette méthode restera du domaine privé

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
library Test initializer Init
 
    globals
        private constant integer MAX = 10 // définit la grandeur de la suite (doit être positif)
        private integer array I1 // pile de référence avec les nombres disponibles
        private integer I1Max=MAX // index max de la pile
        private integer array I2 // pile où sont stockés les nombres utilisés
        private integer I2Max=0 // index max de la pile
        private integer array Iref // on stocke la "position" des nombres
    endglobals
 
    private function Init takes nothing returns nothing // création de la pile
        local integer i=0
 
        loop
        set i=i+1
            set I1[i]=i
            set Iref[i]=i
        exitwhen i==MAX
        endloop
 
    endfunction
 
    function TakeI1 takes nothing returns integer // on prend un nombre de la pile 1 pour le mettre en pile 2
    local integer i=I1[I1Max]
 
    debug if I1Max==0 then
    debug   call BJDebugMsg("tous les nombres sont utilisés")
    debug   return 0
    debug endif
 
        set I2Max=I2Max+1
        set I2[I2Max]=i
        set I1[I1Max]=0 // pas nécessaire mais bon ...
        set I1Max=I1Max-1
        set Iref[i]=I2Max
 
        return i
    endfunction
 
    function AddI1 takes integer number returns nothing // on prend un nombre de la pile 2 pour le remettre dans la pile 1
 
        set I1Max=I1Max+1
        set I1[I1Max]=number
        call BJDebugMsg("I1Max = " + I2S(I1Max) )
        set I2[Iref[number]]=I2[I2Max]
        set Iref[I2[I2Max]]=Iref[I2[I2Max]]-1
        set I2[I2Max]=0 // pas nécessaire mais bon ...
        set I2Max=I2Max-1
 
    endfunction
 
    function DisplayI1 takes nothing returns nothing // juste pour afficher les valeurs de la pile 1
        local integer i=0
 
        call BJDebugMsg(" ")
        call BJDebugMsg("I1")
        call BJDebugMsg(" ")
 
        loop
        set i=i+1
            call BJDebugMsg(I2S(I1[i]))
        exitwhen i==I1Max
        endloop
        call BJDebugMsg(" ")
 
    endfunction
 
    function DisplayI2 takes nothing returns nothing // juste pour afficher les valeurs de la pile 2
        local integer i=0
 
        call BJDebugMsg(" ")
        call BJDebugMsg("I2")
        call BJDebugMsg(" ")
 
        loop
        set i=i+1
            call BJDebugMsg(I2S(I2[i]))
        exitwhen i==I2Max or I2Max==0
        endloop
        call BJDebugMsg(" ")
 
    endfunction
 
endlibrary

PS : je ne comprend toujours pas la solution de Jedai

[Jedai]

PS : je ne comprend toujours pas la solution de Jedai

Il s'agit simplement d'utiliser des tableaux de booléens, mais de les représenter en sous-main par des tableaux de bits, on a ainsi une efficacité et une consommation mémoire idéale pour ton problème. Je ne vois rien de mieux dans ton cas.
Néanmoins si ton langage n'a pas d'opération bit à bit, cette solution n'est pas accessible (sauf éventuellement si ton langage offre des tableaux de booléens en tant que primitive qui ont cette représentation mémoire).

--
Jedaï

[AnozerOne]

Hmm je vois les grandes lignes mais pour que je saisisse totalement il me faudrait un ex concret, quel que soit le langage utilisé, je pense que je comprendrais la méthode.
Merci d'avance