Discussion :

[Nico65]

Bonjour,

j'utilise l'algorithme suivant pour calculer la moyenne des X derniers elements d'un gros flux de données (comprendre qu'il n'est pas stocké entièrement en mémoire). Je veux que ma moyenne soit mise à jour très rapidement à chaque nouvelle entrée, donc j'utilise une file sous la forme d'une LinkedList (voir classe Moyenne dans le code ci-dessous)

Je peux ainsi obtenir, par exemple, la moyenne des 1000 derniers elements
Maintenant, je veux obtenir en plus la moyenne des 500 derniers elements du même flux. Je peux creer un Moyenne(1000) et un Moyenne(500) et faire un addLast() sur les deux, mais 1500 elements seront stockés en mémoire dont 500 en doublon, et je souhaite ne pas avoir de doublons. J'ai pensé faire une classe SousMoyenne qui met à jour un Iterator sur la LinkedList, mais l'itérateur devient obsolète lorsque l'on fait un addLast() sur la liste chainée (... je regrette mes bon vieux pointeurs C )

Vous voyez une solution ?
Ne vous cassez pas la tête à faire du code, juste une vague idée, je creuserais

Merci d'avance

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
 
class Moyenne {
	LinkedList<Integer> list = new LinkedList<Integer>();
	int maxNbEntrees, total = 0;
 
	Moyenne(int maxNbEntrees) {
		this.maxNbEntrees = maxNbEntrees;
	}
 
	void addLast(int val) {
		list.addLast(val);
		total += val;
		if (list.size() > maxNbEntrees)
			total -= list.removeFirst();
	}
 
	double moyenne() {
		return (list.size() == 0) ? 0 : total / list.size();
	}
 
	public static void main(String args[]) {
		Moyenne moy = new Moyenne(2);
		moy.addLast(10);
		moy.addLast(4);
		moy.addLast(6); // le 10 est supprimé de la liste
		System.out.println(moy.moyenne()); // 5
	}
}

je souhaite pouvoir faire :

Code :

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

1
2
3
4
5
6
7
8
9
 
	GroupeMoyenne grp = new GroupeMoyenne(1000); // hérite de SousMoyenne(1000);
	SousMoyenne moy500 = new SousMoyenne(grp, 500);
	while (...) {
		...
		grp.addLast(element); // met grp ET moy500 à jour
		moy500.moyenne(); // moyenne des 500 derniers elements
		grp.moyenne();    // moyenne des 1000 derniers elements
	}

[Nico65]

par principe, puisque j'ai posé la question, je propose une solution

lier plusieurs files ensemble. Lorsque la methode addLast() retire le premier élement, elle appelle addLast() de cet element sur la file suivante s'il y en a une, et ainsi de suite. Je vous épargne le code

[herve91]

Une proposition se basant sur un buffer circulaire partagé entre les différents objets (la contrainte est que les SousMoyenne doivent être créées avant l'appel à la méthode addLast) :

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
public class Moyenne {
 
	private int[] list; // partagée
	private int tete; // partagée
	private int queue;
 
	private int maxNbEntrees, nbEntrees;
	private int total;
 
	private Moyenne parent;
	private List<Moyenne> enfants;
 
	public Moyenne(int maxNbEntrees) {
		this(null, maxNbEntrees);
	}
 
	public Moyenne(Moyenne parent, int maxNbEntrees) {
		this.maxNbEntrees = maxNbEntrees;
		if (parent == null) {
			this.list = new int[maxNbEntrees];
		} else {
			parent = parent.getParent();
			if (parent.nbEntrees > 0) {
				throw new IllegalArgumentException(
						"La liste parente n'est pas vide");
			}
			this.parent = parent;
			if (parent.enfants == null) {
				parent.enfants = new ArrayList<Moyenne>();
			}
			parent.enfants.add(this);
		}
	}
 
	public Moyenne sousMoyenne(int maxNbEntrees) {
		Moyenne enfant = new Moyenne(this, maxNbEntrees);
		return enfant;
	}
 
	public void addLast(int val) {
		if (parent != null) {
			parent.addLast(val);
		} else {
			adjust(val);
			if (enfants != null) {
				for (Moyenne enfant : enfants) {
					enfant.adjust(val);
				}
			}
 
			list[tete++] = val;
			if (tete == maxNbEntrees) {
				tete = 0;
			}
		}
	}
 
	protected void adjust(int val) {
		total += val;
 
		if (nbEntrees == maxNbEntrees) {
			total -= getParent().list[queue++];
			if (queue == getParent().maxNbEntrees) {
				queue = 0;
			}
		} else {
			nbEntrees++;
		}
	}
 
	protected Moyenne getParent() {
		return parent == null ? this : parent.getParent();
	}
 
	public String toString() {
		StringBuilder sb = new StringBuilder(50).append('[');
 
		if (nbEntrees > 0) {
			int[] list = getParent().list;
			int maxNbEntrees = getParent().maxNbEntrees;
 
			int q = queue;
			sb.append(list[q++]);
 
			for (int count = 1; count < nbEntrees; count++) {
				if (q == maxNbEntrees) {
					q = 0;
				}
				sb.append(", ").append(list[q++]);
			}
		}
 
		return sb.append(']').toString();
	}
 
	public double moyenne() {
		return nbEntrees == 0 ? 0 : (double) total / nbEntrees;
	}
 
}

[Nico65]

le test suivant est faux, mais l'idée est bonne, merci

dans mon cas précis (pas le code au dessus, celui dans mon logiciel), ça ne fonctionne pas car je fais des moyennes pondérées et la limite est le poids, donc je ne connais pas à l'avance le nombre d'entrées, c'est sans doute pour ça que je n'ai pas pensé directement à cette implémentation

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
list[tete++] = val;
if (tete == maxNbEntrees) {
	tete = 0;
}
 
// devrait être :
 
if (tete++ == maxNbEntrees) {
	tete = 0;
}
list[tete] = val;
 
// et la même chose pour queue

[herve91]

le test suivant est faux, mais l'idée est bonne, merci

Je ne pense pas j'ai testé avec le main ci-dessous :

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
	public static void main(String args[]) {
		Moyenne moy = new Moyenne(5);
		Moyenne moy2 = moy.sousMoyenne(3);
		moy.addLast(10);
		moy.addLast(4);
		moy.addLast(4);
		moy.addLast(4);
		moy.addLast(4);
		System.out.println(moy + " = " + moy.moyenne());
		System.out.println(moy2 + " = " + moy2.moyenne());
		moy.addLast(10);
		System.out.println(moy + " = " + moy.moyenne());
		System.out.println(moy2 + " = " + moy2.moyenne());
		moy.addLast(4);
		System.out.println(moy + " = " + moy.moyenne());
		System.out.println(moy2 + " = " + moy2.moyenne());
		moy.addLast(7);
		System.out.println(moy + " = " + moy.moyenne());
		System.out.println(moy2 + " = " + moy2.moyenne());
		moy.addLast(1);
		System.out.println(moy + " = " + moy.moyenne());
		System.out.println(moy2 + " = " + moy2.moyenne());
		moy.addLast(5);
		System.out.println(moy + " = " + moy.moyenne());
		System.out.println(moy2 + " = " + moy2.moyenne());
		moy.addLast(8);
		System.out.println(moy + " = " + moy.moyenne());
		System.out.println(moy2 + " = " + moy2.moyenne());
		moy.addLast(3);
		System.out.println(moy + " = " + moy.moyenne());
		System.out.println(moy2 + " = " + moy2.moyenne());
		moy.addLast(1);
		System.out.println(moy + " = " + moy.moyenne());
		System.out.println(moy2 + " = " + moy2.moyenne());
		moy.addLast(6);
		System.out.println(moy + " = " + moy.moyenne());
		System.out.println(moy2 + " = " + moy2.moyenne());
	}

et les résultats sont conformes :

[10, 4, 4, 4, 4] = 5.2
[4, 4, 4] = 4.0
[4, 4, 4, 4, 10] = 5.2
[4, 4, 10] = 6.0
[4, 4, 4, 10, 4] = 5.2
[4, 10, 4] = 6.0
[4, 4, 10, 4, 7] = 5.8
[10, 4, 7] = 7.0
[4, 10, 4, 7, 1] = 5.2
[4, 7, 1] = 4.0
[10, 4, 7, 1, 5] = 5.4
[7, 1, 5] = 4.333333333333333
[4, 7, 1, 5, 8] = 5.0
[1, 5, 8] = 4.666666666666667
[7, 1, 5, 8, 3] = 4.8
[5, 8, 3] = 5.333333333333333
[1, 5, 8, 3, 1] = 3.6
[8, 3, 1] = 4.0
[5, 8, 3, 1, 6] = 4.6
[3, 1, 6] = 3.3333333333333335

[Nico65]

ah oui, j'ai confondu tete++ et ++tete