Discussion :

[hugo123]

Bonjour,

En voyant les autres titres de post dans ce forum j'ai l'impression de poser une question bête ^^ (certaines j'ai même pas compris le titre)

Bref, j'ai un souci avec un algo concernant une liste de valeurs.

Grosso modo, j'ai une liste d'éléments associé à une valeur qui viennent d'une base de données. La valeur correspond à l'ordre de l'élément :

[1,objet1],[2,objet2],[3,objet3],[4,objet4],[5,objet5]

Je propose une action via une interface Web pour réordonner mes éléments, l'utilisateur choisis l'objet 5 par exemple et le place en début de liste :

[1,objet5],[2,objet1],[3,objet2],[4,objet3],[5,objet4]


=> la valeur de l'objet 5 est passé à 1 et tout les autres ont été incrémentés de 1

Ca marche, mais c'est lent. En effet à chaque fois qu'on réordonne un élément, il faut prendre tout les objets entre celui choisi et sa nouvelle position et incrémenter leur valeur.
Le fait de modifier la place d'un élément est couteux.

Du coup je cherche s'il y a d'autres algo possibles :

- diminuer le nombre de permutations nécessaires en ayant des trous entre mes valeurs, du coup plutot que d'incrémenter mes valeurs je vais seulement en incrémenter quelques unes pour remplir mes trous

[10,objet1],[20,objet2],[30,objet3],[40,objet4],[50,objet5]
[9,objet5],[10,objet1],[20,objet2],[30,objet3],[40,objet4]
=> aucune permutation, j'ai trouvé une place libre en première place

(mais comment trouver cette place libre et que faire s'il n'y en a pas.)


- autre chose ?

Si vous avez des pistes sur ce type de problème ca m'intéresserait.

a+

[grishka]

Salut,

Ton algo est plutot bon car en moyenne il permet de n'effectuer qu'un update. Tu as transformé une complexité qui dépend de la taille de la liste, par une qui dépend de l'espacement des indices. Dans ton exemple, dans le cas le plus défavorable, il va falloir regénérer tous les indices une fois sur 10 (si ton utilisateur s'obstine à placer 10 fois de suite le dernier au début). En fait tu vas réellement y gagner sur des listes importantes.

Peut-être pourrais-tu prendre comme nouvel indice la moitié entre le précédent et le suivant, ce qui permet de ne pas favoriser un cas par rapport à un autre.


Enfin je suppose que tu aurais aussi pu optimiser la mise à jour en elle-meme ? (possible avec une seule requete sql)

[souviron34]

euh..

Faire une liste chaînée...


Au lieu d'un tableau..

Là tu es obligé de mettre à jour tous les autres...

Soit le ième élément que tu veux mettre en tête..


Avec une lista chaînée , tu fais (ce sont des pointeurs) :

• elt[i] -> previous -> next = elt[i] -> next
• elt[i] -> next -> previous = elt[i] -> previous

là tu as enlevé le ième élément de la liste

Puis tu fais :

• First -> previous = elt[i]
  
  
• elt[i] -> previous = rien
• elt[i] -> next = First

Là tu as inséré le ième élement en première position


et finalement

• First = elt[i]

tu as bien assigné la première valeur de la liste

Soit 6 opérations seulement, quelle que soit la longueur de la liste...



et maintenant, si tu veux vraiment incrémenter la valeur de chacun, il suffit de repasser une fois à travers toute la liste, mais normalement tu n'aurais pas besoin de stocker le numéro, et donc de l'incrémenter...

[zendeine88]

si je suis juste on utilise un algo qui va faire la permutation toujour avec le dernier, exemple si on choisi l'objet5 la permutation sera avec le dernier de façon directe et automatique .exemple dans un tableau la permutation d'un objet choisi sois directe avec n-1 et sera automatique pour toujour

[hugo123]

pour donner un peu de contexte :

il s'agit d'une liste de taches que l'utilisateur doit réaliser. Chaque tâche à un ordre dans la liste, exemple :

- 1 : ranger sa chambre
- 2 : ranger ses CD
- 3 : laver son chat

et sur l'interface, il est possible de changer cet ordre.

(il s'agit d'un plugin JIRA que je réalise )

Pour répondre aux différentes questions :

Enfin je suppose que tu aurais aussi pu optimiser la mise à jour en elle-meme ? (possible avec une seule requete sql)

Effectivement c'était une piste a laquelle j'ai réfléchi mais en fait il y a double stockage : base de données et index Lucene. Pour ce qui est du stockage base c'est assez performant en insertion et je peux aussi faire un update SQL de masse si besoin. Par contre le stockage Lucene est moins performant en écriture (son avantage c'est la consultation). Et surtout je ne connais pas bien Lucene, du coup je ne sais pas comment modifier des valeurs sur plusieurs documents en un seul coup.
Déjà pour changer une valeur il faut désindexer le document et le recréer, c'est pas formidable ^^

et maintenant, si tu veux vraiment incrémenter la valeur de chacun, il suffit de repasser une fois à travers toute la liste, mais normalement tu n'aurais pas besoin de stocker le numéro, et donc de l'incrémenter...

Assez d'accord sur l'utilisation de liste chainée lorsqu'il s'agit d'infos que je conserve en mémoire mais je ne suis pas sur d'avoir saisi le point : "mais normalement tu n'aurais pas besoin de stocker le numéro"

Dans mon cas j'ai besoin d'un stockage pour l'ordre de l'élément.

A moins que tu veuilles dire qu'en base je pourrais stocker les références des éléments précédents et suivants plutot qu'une valeur numérique représentant un ordre ? Effectivement c'est une idée pas mal, ca devrait fortement diminuer les updates de documents Lucene.

[pseudocode]

Effectivement c'était une piste a laquelle j'ai réfléchi mais en fait il y a double stockage : base de données et index Lucene. Pour ce qui est du stockage base c'est assez performant en insertion et je peux aussi faire un update SQL de masse si besoin. Par contre le stockage Lucene est moins performant en écriture (son avantage c'est la consultation). Et surtout je ne connais pas bien Lucene, du coup je ne sais pas comment modifier des valeurs sur plusieurs documents en un seul coup.
Déjà pour changer une valeur il faut désindexer le document et le recréer, c'est pas formidable ^^

En quoi changer l'ordre implique de modifier les documents ?

Tu veux dire que le numéro d'ordre est stocké dans chaque document ? Et pas dans un objet séparé ?

[hugo123]

Tout a fait, l'ordre est un attribut de l'objet.

Pour en donner un peu plus sur le contexte. Les objets en question sont des fiches JIRA (un bugtracker). Le système de plugin de Jira permet de rajouter des valeurs ou du comportement aux fiches via un système de champs personnalisés.

Ces champs personnalisés permettent de stocker des choses en plus (ici mon ordre). Chaque fiche est stocké sous forme de document Lucene. Si je change la valeur de mon champ personnalisé c'est aussi le document indexé que je dois modifier.

[hugo123]

@souviron34 : j'ai réfléchi un peu à cette solution de liste chainée mais j'ai du mal à la transposer dans mon cas. Ayant besoin d'un stockage il me faudrait stocker les éléments avec les références des éléments précédents et suivants. Or ca complique les choses si j'ai besoin d'afficher l'ordre de mon élément. Typiquement trier sur une colonne, si c'est un chiffre c'est simple, si c'est deux références il faut reconstituer la chaine complète.
Je vais souvent avoir le cas suivant ou j'ai deux objets et j'ai besoin de savoir lequel est placé avant l'autre.

[souviron34]

j'avoue que j'ai un peu de mal avec tes explications..

Si je comprend bien :

tu as une table (disque) avec :

1 objet1 propriete1
2 objet2 propriete2
...

que tu lis en fabriquant des enregistrements

objet1, 1, propriete1
objet2, 2, propriete2
....

et tu veux la trier suivant un élément quelconque..



3 choses que je ne comprend pas très bien :

• veux-tu pouvoir la réécrire comme :
  
  

  objet2, 1, propriete2
  objte1, 2, propriete1
  ...

• Est-ce simplement un traitement en mémoire ?
  
  
• Pourquoi serais-tu obligé d'avoir stocké le numéro d'enregistrement ?

[hugo123]

J'ai des objets (des fiches anomalies) qui contiennent des propriétés (date de création, participants ou ordre de priorité par exemple).

Ces propriétés sont stockées en base de données (table lié avec celle des fiches anomalies)

Pour simplifier :
TABLE1 (ISSUE)

Id
Nom
etc...

TABLE2 (PROPRIETES)
ID fiche
ID
Nom
Valeur
etc...


C'est aussi stocké dans des documents d'index (avec Lucene). Un document comprend toutes les infos de la table 1 et 2.

Le système de plugin me permet d'intervenir au moment de l'affichage du champ à l'écran dans la fiche, ou bien lors de l'affichage d'un un tableau de recherche. C'est ce dernier affichage qui m'intéresse le plus.

Une capture d'écran qui illustrera mieux mon propos :



Sur la capture d'écran, le dernier champ (issue ordering) est mon champ personnalisé. Actuellement il contient des valeurs 1,2,3 et 4 par exemple (qui sont stockées en base et en index) pour pouvoir être réutilisé par la suite.

Je peux faire du drag and drop ou inscrire à la main la nouvelle place dans la liste (Cf. capture d'écran).

Ca marche, mais c'est lent car je dois réordonner tout les éléments entre l'élément déplacé et sa nouvelle position.


Les pistes :

- diminuer le nombre d'opérations (update de masse lucene, je cherche sur le forum Jira si c'est possible)

- améliorer l'algo de réordonnancement


Précision utile, chaque champ n'a pas connaissance des autres au moment de l'affichage. Ce n'est pas moi qui construis la liste des fiches à afficher, le plugin n'agit que sur l'affichage de la colonne.

[souviron34]

je reprend mon point de vue :

soit une table de N lignes à M champs.

Je lis la table et la stocke telle quelle.

Puis je construis une liste chaînée de pointeurs sur cette liste.

Avec l'algo décrit ci-dessus, en 6 opérations je modifie ma liste de pointeurs.

Puis j'affiche ou je stocke en suivant cette liste de pointeurs, si je veux en incrémentant une variable compteur au fur et à mesure du parcours.

Complexité : N + 6

[hugo123]

ok je vois. C'est vrai qu'en modification j'ai une complexité faible mais il y a tout de même des contraintes :

Je lis la table et la stocke telle quelle.
Puis je construis une liste chaînée de pointeurs sur cette liste.

Ca suppose de faire un chargement en démarrage de l'application et de conserver cette liste à jour en fonction des différentes mises à jour de l'application (ajout de fiches anomalies, suppression etc...). Du coup j'ai un troisième référentiel : base, index lucene, liste chainée en mémoire.

Et il me faut un initial load pour stocker en base ce chainage, car après relance de l'application je dois retrouver le même ordre donc il y a persistence des relations entre éléments.

Est ce je ne risque pas d'introduire un troisième référentiel assez lourd à maintenir et couteux en mémoire ?

(dans le système de plugins de Jira je n'aurais de toute facon pas forcément la possibilité de charger et maintenir cette liste a jour en mémoire)

[souviron34]

a priori comme ça je dirais que l'architecture / modélisation est mal faite...

Déjà séparer la table ISSUE de la table date de création et/ou nom de l"émetteur ou toute autre propriété directe, c'est douteux..

Ensuite, avoir une autre table qui n'est pas des pointeurs mais des documents à refaire si on change l'ordre des tâches est ..... plus que douteux...

Tu ne peux pas repenser ta structure de tables ??

Prend exemple sur ce qui se fait dans la suite IBM Rational (ClearQuest), c'est pas mal...


Sinon, en dehors de ce que j'ai mentionné, je donne ma langue au chat....

[hugo123]

date de création et nom de l'émetteur c'était un exemple (faux en l'occurence puisqu'ils sont effectivement dans la table ISSUE).

Les documents eux ne sont pas des tables mais des fichiers index Lucene qui reprennent l'ensemble des propriétés des fiches + valeurs personnalisés rajoutés par les plugins des utilisateurs.

En fait il ne s'agit pas de mes tables donc je ne peux pas les modifier, il s'agit de celles de JIRA (produit Atlassian). C'est le bugtracker que tu retrouves sur tout les produits Apache notamment. Les index Lucene, outre les recherches textuelles très puissantes leur permettent d'avoir des performances très bonnes sur de très larges instances mais ca induit une complexité supplémentaire.
Ils ont un bon système de plugins et c'est dans le cadre d'un plugin que je m'inscris, je n'ai aucune influence sur le reste du code.

Quoi qu'il en soit l'idée de la liste est intéressante, elle m'a ouvert d'autres pistes et j'y réfléchis toujours. Dans un premier temps j'ai réussi a diminuer le temps en groupant les réindexation Lucene (un genre d'update de masse mais qui reste dépendant du nombre de fiches, donc pas très scalables). Ce n'est pas résolu pour autant mais ca baisse l'urgence, c'est devenu a peu près acceptable (30sec => 3 sec même si c'est déjà trop pour une page web)