Discussion :

[AnozerOne]

J'ai un tableau d'entier. Je connais sa taille maximale ainsi que toutes les valeurs qu'il contient.
Je dois retirer des valeurs, redimensionner mon tableau et reclasser les valeurs.

En clair, voici un exemple avec un tableau de 7.

Tableau de Valeurs initial

0 -> valeur X0 *
1 -> valeur X1
2 -> valeur X2 *
3 -> valeur X3
4 -> valeur X4 *
5 -> valeur X5 *
6 -> valeur X6 *

Les index ayant une * doivent être retirés, ce qui donne le tableau suivant :


Tableau de Valeurs résultant

0 -> valeur X1
1 -> valeur X3

Remarques :

- Les autres données n'ont pas besoin d'être effacés, la décalage des données est suffisante, et la taille du nouveau tableau = (Taille de l'ancien tableau - retraits effectués).

- Les index à retirer sont stockés dans un autre tableau que voici :

Tableau des index à retirer

0 -> 0
1 -> 2
2 -> 4
3 -> 5
4 -> 6

Evidemment je connais l'index max de ce tableau également.

Je réfléchis actuellement à un algorithme mais il n'est pas encore achevé.
Ne vous gênez pas pour donner votre approche si cela vous parait évident, même si je comprendrais que vous attendiez ma solution (je la posterais d'ici milieu de semaine prochaine).

Ma seule exigence c'est que cela soit le plus efficace possible.
Ce qui est déjà une grande requête, j'en ai conscience

Merci d'avance pour vos futurs commentaires.

[Zavonen]

Je ne vois pas tellement où est le problème (du point de vue algorithmique). Cela me parait plutôt un problème d'organisation prenant en compte le langage utilisé et ses contraintes (Y-a-t-il des objets dynamiques natifs ou non ?)

Code python :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
# -*- coding: cp1252 -*-
 
Liste=['A','B','C','D','E','F','G']
TD= {0:True,2:True,4:True,5:True,6:True}
 
def Clean (Tableau, Indexes):
    return [ Tableau[i] for i in range(0,len(Tableau)) if not Indexes.get(i)]
 
def main():
    print Clean(Liste,TD)
 
if __name__ == '__main__':
    main()

[pseudocode]

Je propose de faire 2 swaps, pour ramener les éléments non supprimés au début du tableau:

swap Tableau[1],Tableau[0]
swap Tableau[3],Tableau[1]

Code java :

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

1
2
3
4
5
6
7
8
9
10
11
String[] tableau = new String[]{"X0","X1","X2","X3","X4","X5","X6"};
int[] remove = new int[] {0,2,4,5,6};
 
int j=0, k=0, r=remove[k++];
for(int i=0;i<tableau.length;i++) {
	if (i<r)
		swap(tableau,i,j++);  // échange les cases i et j
	else
		if (k<remove.length) r=remove[k++]; else r=tableau.length;
}
tableau = Arrays.copyOf(tableau, j); // nouvelle taille du tableau = j

[Jedai]

La méthode est correcte, à part que faire un swap() n'est pas nécessaire, une simple copie suffit. Par ailleurs si l'objectif est de créer un nouveau tableau plutôt que de modifier l'ancien, il est préférable de faire directement les copie dans le nouveau tableau créé au préalable.

--
Jedaï

[pseudocode]

La méthode est correcte, à part que faire un swap() n'est pas nécessaire

Certes, mon maitre. C'est juste que je n'aime pas perdre des informations.

[AnozerOne]

Le but est de modifier l'ancien tableau, pas d'en créer un nouveau.
Et comme je l'ai dit seul le décalage est important, peu importe que je perde des données, je ne les ai simplement plus besoin et elles seront écrasées ultérieurement de toute façon.

Le langage utilisé est un langage script le jass2 pour l'éditeur de warcraft 3, enfin en réalité le vJass (hack de l'éditeur jasshelper) pseudo orienté objet

Il n'y a pas d'objets dynamiques natifs.

Sinon ca serait sympa de m'expliquer en détail le script de pseudocode je ne connais pas du tout le java et bloque sur certaines choses.

J'ai oublié de préciser que les index à supprimer sont collectés un à un et en ordre algébrique.
Et la taille du tableau à modifier peut varier de 1 à 8191.
Après avoir rempli une feuille blanche de plusieurs exemples diverses j'ai eu une idée d'un algo assez performant à mes yeux.

Je le posterais ce soir si tout va bien.

PS : Quand je dis tableau je parles d'une variable globale array.

[pseudocode]

Sinon ca serait sympa de m'expliquer en détail le script de pseudocode je ne connais pas du tout le java et bloque sur certaines choses.

L'idée générale c'est de déplacer les elements qu'on veut conserver au début du tableau. Pour se faire, on utilise

- Un pointeur "i" qui parcourt itérativement le tableau de gauche a droite (for i=0 to tableau.length)
- Un pointeur "j" initialisé au début du tableau (j=0)

Pour chaque position "i", si on doit converver l'élément en position "i" alors on le déplace en position "j" (et on incrémente "j").

Pour savoir si l'element doit etre conservé, on regarde le numero du prochain élément à supprimer (r=remove[k]). Tant que "i" est inferieur strictement a "r", alors l'élément doit être conservé. Sinon on est dans le cas "i"="r", donc l'élément doit etre supprimé => on ne le déplace pas au début => on ne fait rien. On se contente juste de chercher la prochaine valeur de "r"