Discussion :

[Jimalexp]

Salut,

J'ai recréé un genre de LinkedList dans un langage appellé unrealscript.

Voici la méthode qui sert à recupérer les éléments conteneurs qui portent une référence vers un objet.

J'ai modifié les conteneurs pour qu'ils supportent les doubles liens et là je suis en train de me casser la tête pour adapter la méthode pour gagner de la vitesse.

Le raisonnement est simple. Si l'indice se trouve vers le début de la liste, j'utilise des getNext() et, si l'indice se trouve près de la fin de la liste, j'utilise les getPrevious(). Mais, apparemment, je coince au niveau de l'algorithmique et ca m'exaspère.

Un petit coup de pouce ne serais donc pas de refus .

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
function ListElement getListElement( int index )
{
	local int i, size;
	local ListElement le;
 
	if( !isEmpty() )
	{
		if( index > 0 ) // index is a valid value
		{
			//if( index < size/2 ) // Closer to List start
			//{
				le = getFirstListElement();
 
				i = 1; // Account for firstListElement
 
				while( i != index )
				{
					le = le.getNext();
 
					if( le == none )
						return none;
 
					i++;
				}
 
				return le;
			//}
 
			// Divide and conquer
			// Might need fixing
			/* if( index >= size/2 ) // Closer to List end
			{
				le = getLastListElement();
 
				i = size; // Account for lastListElement
 
				while( i != index )
				{
					le = le.getPrevious();
 
					if( le == none )
						return none;
 
					i--;
				}
 
				return le;
			} */
		}
	}
 
	return none;
}

[Zavonen]

Je ne vois aucune initialisation de la variable locale size de type int.

[Jimalexp]

Exacte, et merci de prendre le temps de lire tout le code. J'ai surement viré l'initialisation avant de faire un copier-coller.

Normalement, à l'intérieur du premier if il y a l'instruction "size = size()". Cette méthode va tout simplement chercher la valeur d'un compteur qui est incrémenté/décrémenté selon les opérations d'ajout ou de suppréssion.

Ce qui me brouille surtout ici c'est la partie où "index >= size/2" (la première partie fonctionne à merveille). Le raisonnement c'est qu'on part de lastListElement (référence vers le dernier conteneur) pour arriver au conteneur qui correspond à la valeur index. Il y a peut être une manière plus éfficace de procéder aussi. C'est là que j'ai un peu de mal à imaginer les choses à l'envers sur "papier".

Le fonctionnement de la boucle a son importance aussi. Est-ce que le code à l'intérieur du bloc est executé ou pas lorsque la condition est remplie. C'est assez basique, d'autant plus que je me souviens de mes premiers cours sur les nuances "jusqu'à ce que" et "tant que". En principe, le block while ici ne s'exécute que si la condition est vraie.

P.S: Avec tous les problèmes que ca soulève, je suis en train de me demander si ce ne serais pas plus intéressant que chaque conteneur dispose d'un id pour correspondre avec index.

[Jimalexp]

Zut, le code est bon mais pas le placement des returns. Encore une victime de la cécité selective .

Au moins j'ai compris la différence entre boucles. Quant à l'idée d'ajouter un id à chaque conteneur, ca semble intéressant jusqu'à ce qu'on se rends compte qu'un petit changement dois être répercuté dans toute la liste.

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
function ListElement getListElement( int index )
{
	local int id, listsize;
	local ListElement le;
 
	if( !isEmpty() )
	{
		listsize = size();
 
		// index is a valid value
		if( index > 0 && index <= listsize )
		{
			// Divide and conquer
 
			if( index < listsize/2 ) // Closer to List start
			{
				le = getFirstListElement();
				id = 1;
 
				// Do not use a do...while() here as it will run the block at least once and skip index=1
				while( id != index )
				{
					le = le.getNext();
 
					if( le == none )
						return none;
 
					id++;
				}
			}
 
			if( index >= listsize/2 ) // Closer to List End
			{
				le = getLastListElement();
				id = listsize;
 
				while( id != index )
				{
					le = le.getPrevious();
 
					if( le == none )
						return none;
 
					id--;
				}
			}
 
			return le;
		}
	}
 
	return none;
}