Discussion :

[speedster]

Bonjour,

Je souhaite implémenter un graphe représentant l'évolution du classement de plusieurs équipes de football.

L'ajout des résultats peut se faire dans le désordre (ex: insertion pour la journée 5 puis journée 1 pour journée 7...).

Je dispose d'une table de classement pour chaque équipe et par journée.
Ainsi si j'ajoute, modifie ou supprime un résultat concernant la journée j alors une requête mettra à jour tous les lignes de la table pour les journées >= j puisqu'un résultat de la journée j compte pour la journée j+1.

Ce qui m'inquiète, c'est la performance.
En effet, lors de l'affichage du graphe, il faudra que je calcule le classement et ce pour chaque journée et c'est très coûteux.
J'ai implémenté un algorithme récursif de calcul du classement pour séparer même dans les cas les plus extrêmes des équipes à égalité.
En appliquant cet algo sur 20 ou 30 journées, cela devient ingérable.

Avez-vous une idée pour résoudre ce problème autrement ?

[borisd]

Quand tu dis "Calculer le classement", c'est juste un tri sur plusieurs clés, non ?
Il y a des algorithmes très efficaces pour ça, comment t'y prends-tu exactement ?

[speedster]

La table Classement se compose de plusieurs champs :

- numéro (clé)
- num_utilisateur_participant (clé étrangère d'un objet utilisateur participant)
- num_tournoi (clé étrangère d'un objet tournoi)
- groupe (numéro éventuel du groupe - dans le cas d'une coupe type ligue des champions)
- classement (la position dans le classement)
- nb_points
- nb_journees
- nb_victoires
- nb_nuls
- nb_defaites
- nb_buts_pour
- nb_buts_contre
- diff_buts

L'algorithme de classement calcule le classement (position) selon les critères généraux (en cas d'égalité entre ttes les équipes) ou particuliers (entre les équipes à égalité).

Le tri du classement est une fonction récursive :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
	 * Fonction récursive qui trie le classement selon la liste de critères.
	 * @param classementFinal liste contenant le classement trié.
	 * @param equipes les équipes du classement à trier.
	 * @param criterias les critères choisis pour le tri du classement.
	 * @param nbEquipes le nombre d'équipes à trier.
	 * @param toCalculatePart un booléen interne à la méthode.
	 * @param critPart indique s'il s'agit des critères généraux ou particuliers.
	 * @param mode le mode du tournoi (normal ou expert), le calcul du fairplay étant ou non calculé.
	 */
	@SuppressWarnings("unchecked")
	private static final void trierClassement(List<AbstractClassement> classementFinal, List<AbstractClassement> equipes, 
			List<Integer> criterias, int nbEquipes, boolean toCalculatePart, boolean critPart, Integer mode);

Les étapes :
- tri du classement selon les critères demandés
- regroupement par bloc des équipes à égalité selon les critères
- pour chaque bloc (sans entrer dans le détail), calculer les critères suivants et rappeler l'algorithme sur les blocs regroupant les équipes à égalité. La condition d'arrêt est l'obtention de blocs de taille 1 (=> équipes départagées).

Il faut savoir que lorsque je calcule les critères particuliers, je fais une requête pour calculer un "mini-championnat" uniquement entre les équipes à égalité.

Cet algo fonctionne bien et n'est pas très lent compte tenu du fait que les cas extrêmes se présentent rarement.
Par contre, 20, voire 30 appels successifs plombent complètement les performances et cela rend l'affichage du graphe (évolution du classement) inutilisable.

Si tu connais des algorithmes très efficaces, je suis preneur!

[borisd]

Quelle partie du calcul prend beaucoup de temps ? Comment effectues-tu cette étape :

- tri du classement selon les critères demandés

[speedster]

J'effectue un tri sur 3 colonnes (pts, diff buts, buts pour) s'il s'agit des critères généraux ou bien sur une seule colonne (pts) s'il s'agit des critères particuliers.

J'utilise la méthode sort() de la classe utilitaire Collections et un comparator TrieurClassement qui compare 2 valeurs issues de la colonne en question :

Code :

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

1
2
3
4
5
// tri du classement selon les critères demandés 
		// (les critères doivent êtres ordonnés dans la liste du moins important au plus important)
		for (int criteria : criterias) {
			Collections.sort(equipes, new TrieurClassement(criteria, false));
		}

[borisd]

J'avoue que je n'ai pas trop d'idées sans entrer dans l'implémentation...
Je peux juste faire quelques suggestions :
- avoir un accès direct aux données pendant le tri : si jamais ton comparator utilise une ou deux requêtes SQL à chaque fois qu'il doit comparer deux valeurs, le programme passe à mon avis la plupart de son temps à faire ça. Mieux vaut copier les données une bonne fois pour toutes dans un tableau temporaire auquel on peut accéder directement
- limiter le nombre d'objets créés, d'initialisations... dans la portion récursive
- si tu n'arrives finalement pas à réduire le temps de calcul, stocker les classements déjà calculés pour un réaffichage ultérieur
- voir si une partie du calcul ne peut pas se faire incrémentalement d'une journée à la suivante

[speedster]

Je te remercie.
Je vais essayer d'optimiser mon algo.

En fait cet algo est destiné à calculer le classement (cumulatif et non par journée) des équipes après la mise un jour d'un score.

Avant d'implémenter l'évolution du classement, j'ai pensé à la performance et j'ai donc appelé cet algo dans une boucle pour voir comment il se comporte.

Je devrais peut être songer à développer une fonction différente se servant du coeur de l'algo pour cette fonctionnalité mais ne pas boucler bêtement sur la fonction TrierClassement.