Optimisation - Inversion d'éléments dans une liste

[Mewyn]

Bonjour,

J'ai une fonction qui inverse les éléments (des sommets) d'une liste de i à j:

Code :

1
2
3
4
5
6
7
	protected void reverse(int i,int j,List<Sommet> _path_) {
		for(int k=0;k<=(j-i)/2;k++) {
			Sommet tmp =_path_.get(i+k);
			_path_.set(i+k,_path_.get(j-k));
			_path_.set(j-k,tmp);
		}
	}

J'aimerai savoir si il est possible d'optimiser cette fonction, pour information l'objet _path_ passer en argument est une arrayList.

[tchize_]

Non, mallheureusement, pas de méthode plus rapide avec l'arrayList. On pourrais peut-être envisager de créer une méthode plus rapide dans une nouvelle implémentation de List<> mais faut avoir une bonne raison. Le gain serait marginal.

Ici, avec ArrayList, set(index,value) est déjà en O(1)

[thelvin]

Ben, on peut imaginer de renvoyer une "vue" inversée de la List, plutôt que modifier la List elle-même.

On ferait une nouvelle classe qui implémente List et qui se base sur une autre List, le but étant de présenter exactement les mêmes données, mais en sens inverse. Ce serait bien plus compliqué, mais du coup produire cette nouvelle List serait O(1) au lieu de O(n), et elle exécuterait toutes ses méthodes avec la même complexité que la première.

Par contre, si on fait ça, ça ne modifie pas la List d'origine. Ça permet juste d'avoir à disposition, une List, qui a les éléments de la List d'origine, en sens inverse (et qui change à chaque fois que la List d'origine change, et vice-versa.)

TL;DR: un pattern décorateur. C'est O(1) au lieu de O(n)

[tchize_]

Sauf qu'ici il n'inverse pas la liste, mais juste une section et, à priori, je pense qu'il est obligé de modifier la liste d'origine, si c'est pour modifier des données dans une structure en arbre dans le cadre d'un algo

Sinon, effectivement, on peux envisager un décorateur qui contient une table de redirection, et l'inversion se ferait uniquement via cette table.

[thelvin]

Ah, effectivement.