[HTML/JS/DOM]Algo casse tête ( Trouvé :) )

Algo casse tête ( Trouvé :) ) [HTML/JS/DOM] - HTML/CSS - Programmation

Marsh Posté le 14-01-2004 à 02:28:35    

Bonjour,
 
Le problème est le suivant :
 
J'ai un tableau HTML "normalisé".
 
Normalisé pour moi, ça veux dire :
Il n'y a pas de cellule avec des rowspan ou colspan inutiles.
Pas de cellule non utilisée.
 
Je cherche un algo en JavaScript (DOM) le plus efficace possible qui me donne pour une cellule les Numéros de ligne et de colonne.
 
Pour le moment le seul algo que je vois :
 
J'initialise un Array à 2 dimensions avec toutes les case à false.
 
Ensuite je fais plusieurs boucle:
Boucle sur les lignes TR
Je cherche la première case de l'Array à false
Boucle sur les TD de la ligne TR
Si c'est la cellule que je cheche, sa position est celle de la case trouvée
Sinon
- je met à true les case occupées pas la cellule (rowspan et colspan).
- Je cherche dans la ligne de l'Array la case suivante à false.
Fin boucle TD
Fin boucle TR
 
Exemple :
 
Tableau HTML


  1 2 3 4 5 6 7 8 9
 +-+-+-+-+-+-+-+-+-+
1|A|B B|C C C C C|D|
 +-+   +         + +
2|E|B B|C C C C C|D|
 + +   +-+-+-+-+-+ +
3|E|B B|F|X|     |D|
 +-+   +-+-+-+-+-+-+
4| |B B|     | | | |
 +-+-+-+-+-+-+-+-+-+
5| | | | | | |     |
 +-+-+-+-+-+-+-+-+-+


 
Array Javascript


 +-+-+-+-+-+-+-+-+-+
1|1 1 1 1 1 1 1 1 1|
 +                 +
2|1 1 1 1 1 1 1 1 1|
 +                 +
3|1 1 1 1 X 0 0 0 0|
 +                 +
4|0 1 1 0 0 0 0 0 0|
 +                 +
5|0 0 0 0 0 0 0 0 0|
 +-+-+-+-+-+-+-+-+-+


Dans cet exemple, je cherche la position de la case X (Premier TD du Troisième TR)
En Remplissant de 1 l'Array JS avec les cases occupées par les cellules A, B, C, D, E et F, je trouve bien la position de ma cellule : Ligne 3, colonne 5.
 
Je me demande donc si y'a pas plus simple :D


Message édité par Mara's dad le 18-01-2004 à 01:23:30

---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.
Reply

Marsh Posté le 14-01-2004 à 02:28:35   

Reply

Marsh Posté le 14-01-2004 à 09:47:12    

Bon, y'a plus simple...
 
En fait un simple Array de n colonnes suffit :
 
Tableau HTML


  1 2 3 4 5 6 7 8 9
 +-+-+-+-+-+-+-+-+-+
1|A|B B|C C C C C|D|
 +-+   +         + +
2|E|B B|C C C C C|D|
 + +   +-+-+-+-+-+ +
3|E|B B|F|X|     |D|
 +-+   +-+-+-+-+-+-+
4| |B B|     | | | |
 +-+-+-+-+-+-+-+-+-+
5| | | | | | |     |
 +-+-+-+-+-+-+-+-+-+


 
Array Javascript init


 +-+-+-+-+-+-+-+-+-+
1|1 1 1 1 1 1 1 1 1|
 +-+-+-+-+-+-+-+-+-+


 
Pour chaque cellule, on cherche dans l'Array le premier plus petit nombre. Ca donne le Numéro de ligne de la cellule.
On augmente le nombre de rowspan, pour les colspan colonnes de la cellule.
 
Traitement de A, le tableau devient :


 +-+-+-+-+-+-+-+-+-+
1|2 1 1 1 1 1 1 1 1|  
 +-+-+-+-+-+-+-+-+-+


 
Traitement de B, le tableau devient :


 +-+-+-+-+-+-+-+-+-+
1|2 5 5 1 1 1 1 1 1|
 +-+-+-+-+-+-+-+-+-+


 
Traitement de C, le tableau devient :


 +-+-+-+-+-+-+-+-+-+
1|2 5 5 3 3 3 3 3 1|
 +-+-+-+-+-+-+-+-+-+


 
Traitement de D, le tableau devient :


 +-+-+-+-+-+-+-+-+-+
1|2 5 5 3 3 3 3 3 4|
 +-+-+-+-+-+-+-+-+-+


 
Traitement de E, le tableau devient :


 +-+-+-+-+-+-+-+-+-+
1|4 5 5 3 3 3 3 3 4|
 +-+-+-+-+-+-+-+-+-+


 
Traitement de F, le tableau devient :


 +-+-+-+-+-+-+-+-+-+
1|4 5 5 4 3 3 3 3 4|
 +-+-+-+-+-+-+-+-+-+


 
Traitement de X :
Fini, la position de X est : Ligne 3 colonne 5.


---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.
Reply

Marsh Posté le 14-01-2004 à 10:53:47    

La fonction en JS :

Code :
  1. /*
  2. Cette fonction cherche la position de la cellule passée en paramètre
  3. */
  4. function getCellPos( oCell )
  5. {
  6. var c = getNbCols(); // Retourne le nombre de colonnes de curTable.
  7. var i; // Iterateur
  8. var j; // Numéro de colonne trouvé
  9. var l; // Numéro de ligne trouvé
  10. var x = new Array( c ); // Tableau des positions
  11. var pos = new Array( 2 ); // Tableau pour les valeurs de retour.
  12. // Ligne de recherche
  13. // On commence au début du tableau
  14. var line = curTable.firstChild;
  15. // Cellule de recheche
  16. var cell;
  17. // Initialisation du tableau des positions
  18. for( i = 0; i < c; i++ )
  19. {
  20.  x[ i ] = 1;
  21. }
  22. // Boucle principale. Je sais que je vais trouver !
  23. while( true )
  24. {
  25.  // Première cellule de la ligne
  26.  cell = line.firstChild;
  27.  // Changement de ligne, on revient au début
  28.  j = 0;
  29.  // Boucle sur les cellules
  30.  while( cell )
  31.  {
  32.   // On cherche la plus petite valeur dans x
  33.   l = x[ j ];
  34.   for( i = j; i < c; i++  )
  35.   {
  36.    if( x[ i ] < l )
  37.    {
  38.     j = i;
  39.     l = x[ i ];
  40.    }
  41.   }
  42.   // On a trouvé
  43.   if( cell == oCell )
  44.   {
  45.    pos[0] = x[ j ];
  46.    pos[1] = j + 1;
  47.    return( pos );
  48.   }
  49.   // On marque les positions occupées par la cellule
  50.   for( i = 0; i < cell.colSpan; i++ )
  51.   {
  52.    x[ j + i ] += cell.rowSpan;
  53.   }
  54.   // Cellule suivante
  55.   cell = cell.nextSibling;
  56.  }
  57.  // Ligne suivante
  58.  line = line.nextSibling;
  59. }
  60. }


 
curTable est une variable globale qui est le TBODY du tableau HTML sur lequel on travaille.


Message édité par Mara's dad le 14-01-2004 à 10:56:57

---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.
Reply

Marsh Posté le 15-01-2004 à 09:33:10    

Un petit up pour dire que je peux avoir facilement le numéro de ligne de la cellule.
 
J'ai cherché, mais je ne vois pas en quoi ça peut aider à simplifier l'algo.
 
Si vous avez des idées, n'hésitez pas hein :D


---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.
Reply

Marsh Posté le 17-01-2004 à 02:42:00    

Ce que ça donne pour le moment :
http://www.surleau.org/edit/tab.html
 
Manque l'ajout de colonne.
Peut-être pour demain matin...
 
PS : Si le lien ne marche pas, y'a celui-là :
http://www.surleau.com/edit/tab.html
mais ce sera pas forcément la dernière version.
M'enfin vu qu'il semble que je sois le seul intéressé :ange:  
 
Normalement, ça marche sous IE et Moz.


Message édité par Mara's dad le 17-01-2004 à 02:46:56

---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.
Reply

Marsh Posté le 17-01-2004 à 03:04:01    

[:wam] il est fou [:wam]
impressionant en tous cas.
 
juste une question naive: c'est quoi l'interet de faire ça coté client?


---------------
Hey toi, tu veux acheter des minifigurines Lego, non ?
Reply

Marsh Posté le 17-01-2004 à 10:19:04    

Pour un Content Management Systems par exemple.
 
http://www.bris.ac.uk/is/projects/cms/ttw/ttw.html#os


---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.
Reply

Marsh Posté le 17-01-2004 à 13:08:10    

par exemple .... :D
 
en tout cas, comme moins moins ... c'est impressionnant !
mais c'est vraiment ce faire chier pour peu de choses non !?


---------------
from here and there -- \o__________________________________ -- la révolution de la terre, en silence
Reply

Marsh Posté le 17-01-2004 à 13:41:53    

Explique pourquoi ?
 
Pour moi, je le fait pour 2 raisons :
 
- Je n'ai rien trouvé de satisfaisant dans les éditeurs existants. Il sont soit IE soient Moz et s'il font les 2, c'est avec du code spécifique. D'autre part il n'ont jamais toutes les fonctions dont j'ai besoin, et souvent, il sont buggués.
 
- J'ai trouvé que c'était un très bon exercice pour apprendre le DOM JS. Ca me permet de me familiariser avec et de trouver des solutions qui ne soient jamais propres à IE ou Moz.
 
Le seul trus qui reste spécifique à un browser, c'est la gestion du clavier :
windows.event.key pour IE alors que Moz passe un objet event à la fonction qui gère les événements onKey...
Je cherche en ce moment le moyen de rendre ce fonctionnement spécifique des browsers le plus générique possible pour le code JS.


---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.
Reply

Marsh Posté le 17-01-2004 à 14:41:15    

d'accord avec toi, c'est un super exercice !
mais je vois pas bien l'intérêt de ce genre de feature pour un cms par exemple .... ca va permettre aux utilisateurs de generer du html avec des couleurs hideuses ou une mise en page foireuse. Ca risque *fort* de pourrir la charte graphique adoptée lors du deploiement du cms.
 
disons que de manière général, je ne suis pas convaincu par l'outil.
 
(...mais je ne connais pas ton contexte d'utilisation  ;)  )


---------------
from here and there -- \o__________________________________ -- la révolution de la terre, en silence
Reply

Marsh Posté le 17-01-2004 à 14:41:15   

Reply

Marsh Posté le 17-01-2004 à 15:27:50    

L'outils permet juste à l'utilisateur de générer un tableau HTML pour présenter des infos tabulaires.
Le style du tableau poura ensuite être choisi parmis une liste prédéfinie conforme à la charte.
 
Ce n'est pas un outils global de mise en page, juste un composant. Pour le moment ce n'est que la partie de l'éditeur qui permet définir le layout du tableau.
Taille, style, contenu seront définis ailleur :D
 
Par exemple, pour le moment, je bosse "officiellement" sur la version 2 de lutece, le CMS open source de paris.fr
Dans lutece, il n'y a pas pour le momemnt de possibilité pour un rédacteur de générer un tableau.
Ce genre de choses :  
http://www.paris.fr/fr/Sport/equip [...] tarifs.ASP doit être généré à la main ou avec un outil externe. Le respect de la charte incombe au rédacteur et au responsable de publication.
 
Par ailleur je travaille, "Officieusement" cette fois, depuis plusieurs années à un CMS dont la vocation est d'être "HYPER SIMPLE".
J'écris le composant tableau pour mon propre CMS. Si j'arrive à faire quelque-chose de robuste, je pourais proposer de l'intégrer à lutece V2 :D


Message édité par Mara's dad le 17-01-2004 à 15:38:17

---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.
Reply

Marsh Posté le 17-01-2004 à 19:00:40    

Salut,
 
Alors déjà, il y a quelquechose dans ton algo que je pense qu'on peut éviter, c'est la recherche de la plus petite valeur dans x :
- quand tu es dans une même ligne, au moment où tu marques les positions occupées par une cellule, tu peux déjà en profiter pour augmenter j de la valeur de colspan, ceci permettant de réduire le temps de recherche
- ensuite, tu n'es pas obligé de chercher un minimum ... car tu connais la valeur de ce minimum vu que c'est le numéro de ligne en cours. Il te suffit donc de chercher la première occurence de ce numéro.
Je suis d'accord, ça ne réduira pas de beaucoup de temps de calcul mais bon c'est ça de gagné :)
 
Et j'ai une autre manière de trouver la position de x, en exploitant le fait que tu puisses facilement avoir le numéro de ligne de la cellule. Ca me permet de trouver en 6 étapes au lieu de 7 la position ... mais c'est un mauvais exemple du fait que les C prennent pas mal de place en largeur.  
En fait je m'occupe uniquement de la partie du tableau située entre le début et la position éventuelle de X ce qui devrait être plus rapide que de balayer toute la largeur.
J'explique par l'exemple :
X se trouve à la ligne 3, je fais donc un tableau de 3 éléments que je remplis de 1 :

1, 1, 1

 
(je le dis tout de suite, au fur et à mesure je me suis rendu compte que j'utilisais pas mal le dernier algo que tu as proposé ;) )
Ces 3 valeurs indique la prochaine colonne libre pour les 3 premières rangées (et non l'inverse pour ton algo).
Je démarre de la première ligne du tableau HTML :
- Première cellule : A (1, 1) (colspan, rowspan)
  je modifie donc ma liste en conséquence :

2, 1, 1


 
je regarde si il y a encore des valeurs à 1 (en fait je mets dans une variable la colonne en cours) : OUI en ligne 2 => je regarde donc la ligne 2 :
- Cellule E (1, 2) =>

2, 2, 2


je vois que la colonne 1 est remplie ... je passe à la colonne 2.
Pour cela je cherche la première occurence de 2 ... c'est à la ligne 1 : je lis donc l'élément suivant à cette ligne :
- Cellule B (2, 4) =>

4, 4, 4

(je me fous des rangées suivantes)
Il n'y a plus de 2 ... je passe à 3 ... plus de 3 ... je passe à 4 (ya sûrement moyen d'optimiser ça, entre autre en notant lors du remplissage d'une colonne la plus petite valeur entrée ... ce qui permettra de voir que dans notre c'est 4 et non 3)
Je cherche la première occurence de 4 ... c'est en 1 :
- Cellule C (5, 2) =>

9, 9, 4


 
Je recherche la première occurence de 4 (on peut commencer à chercher à partir de la ligne 3 vu qu'on connaît la hauteur de C) : c'est à la ligne 3 !
On lit la prochaine cellule à la ligne 3 :
- Cellule F (1, 1) =>

9, 9, 5


Plus de 4 ... on passe à 5 ... premier 5 à la ligne 3 :
- Cellule X (1, 1) =>
on a gagné ! on peut donc lire colonne 5 =)
 
Un autre exemple (parce que cet exemple m'a posé des problèmes au début) :
on a  


A B D C E G H
E B D C I J K
F F D O O O O
F F X O O O O


 
on commence avec

1, 1, 1 ,1

(X à la ligne 4)
 
Cellule A (1, 1)

2, 1, 1, 1


 
Cellule E (1, 1)

2, 2, 1, 1


 
Cellule F (2, 2)

2, 2, 3, 3


 
Cellule B (1, 2)

3, 3, 3, 3


 
Cellule D (1, 3)

4, 4, 4, 3


 
Cellule X (1, 1)
Bingo -> colonne 3, ligne 4
 
(Le problème que j'avais rencontré, c'est que j'utilisais tout d'abord la liste pour avoir la prochaine ligne de libre (comme dans ton algo) et avec le F qui débordait vers la droite je me suis rendu compte qu'il fallait changer d'orientation ... en accord avec le fait que j'analyser colonne par colonne au lieu de ligne par ligne)
 
Le problème c'est que tu ne pourrais pas faire

Code :
  1. line = line.nextSibling


vu qu'il faut gérer plusieurs lignes en même temps ... faudrait pouvoir stocker l'élément cell de chaque ligne dans un tableau de dimension égale à celle de la liste (donc 4) et ensuite faire

Code :
  1. t[3] = t[3].nextSibling

si c'est possible.

Reply

Marsh Posté le 17-01-2004 à 19:17:34    

J'ai lu vite fait :D
Je ne suis pas sûr d'avoir saisi l'idée, mais je vais voir çà.
En tout cas, je te remercie de ta contribution, t'es le premier à t'intéresser au problème :sol:
 
Sinon, je confirme, il est possible de stocker les cellules dans un tableau.


---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.
Reply

Marsh Posté le 17-01-2004 à 19:19:40    

mara's dad a écrit :

J'ai lu vite fait :D
Je ne suis pas sûr d'avoir saisi l'idée, mais je vais voir çà.


 
 
Bah en fait tu prends ton algo et tu lui fais faire une rotation de 90°  :whistle:  

Reply

Marsh Posté le 17-01-2004 à 19:51:44    

et moi ma question? :o
 
 
(perso pour faire ce genre de truc je prefererais une syntaxe wiki-like - oui oui y'en a qui supportent les tableaux - à moins qu'il y ait un réél besoin de tableaux complexes? auquel je ferais qd meme le truc coté serveur... je critique pas je cherche à comprendre :o)


---------------
Hey toi, tu veux acheter des minifigurines Lego, non ?
Reply

Marsh Posté le 17-01-2004 à 19:52:48    


 
elle n'etait pas intéressante.... [:veryfree]


---------------
from here and there -- \o__________________________________ -- la révolution de la terre, en silence
Reply

Marsh Posté le 18-01-2004 à 01:07:03    

the real moins moins a écrit :

et moi ma question? :o
 
 
(perso pour faire ce genre de truc je prefererais une syntaxe wiki-like - oui oui y'en a qui supportent les tableaux - à moins qu'il y ait un réél besoin de tableaux complexes? auquel je ferais qd meme le truc coté serveur... je critique pas je cherche à comprendre :o)


 
Tu fais comment 'Coté serveur' ?
Tu demande au rédacteur combien de lignes et de colonnes c'est çà ? -> Beaucoup trop limité pour moi :D


---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.
Reply

Marsh Posté le 18-01-2004 à 01:22:36    

Tentacle a écrit :


 
 
Bah en fait tu prends ton algo et tu lui fais faire une rotation de 90°  :whistle:  
 


Done !

Code :
  1. /*
  2. Cette fonction cherche la position de la cellule passée en paramètre
  3. */
  4. function getCellPos( oCell )
  5. {
  6. var aCol = new Array();  // Tableau des positions des colonnes
  7. var aCell = new Array(); // Tableau des cellules
  8. var i, j, colSpan, rowSpan;
  9. var line;
  10. var linePos = getLinePos( oCell.parentNode );
  11. // Init tableaux
  12. line = curTable.firstChild;
  13. i = 1;
  14. do
  15. {
  16.  aCell[i] = line.firstChild;
  17.  aCol[i] = 1;
  18.  i++;
  19.  // Ligne suivante
  20.  line = line.nextSibling;
  21. }
  22. while( i <= linePos );
  23. // Traitement
  24. i = 1;
  25. // Tant que la cellule n'est pas celle qu'on cherche
  26. while( aCell[i] != oCell )
  27. {
  28.  // Si la cellule existe dans la ligne
  29.  if( aCell[i] )
  30.  {
  31.   colSpan = aCell[i].colSpan;
  32.   rowSpan = aCell[i].rowSpan;
  33.   // Mise à jour du tableau des position en fonction de colSPan et rowSpan
  34.   for( j=0; j < aCell[i].rowSpan; j++ )
  35.   {
  36.    aCol[ i + j ] += colSpan;
  37.   }
  38.   // Mémorisation de la cellule suivante à traiter dans la ligne
  39.   aCell[i] = aCell[i].nextSibling;
  40.   // Ligne suivante
  41.   i += rowSpan;
  42.   // On revient sur la première ligne
  43.   if( i > linePos )
  44.   {
  45.    i = 1;
  46.   }
  47.  }
  48.  // Ligne suivante
  49.  else
  50.  {
  51.   i++;
  52.  }
  53. }
  54. return( aCol[i] );
  55. }


 
C'est plus rapide, j'ai testé.
1.2 secondes contre plus de 2 pour calculer les positions d'un tableau de 20*20 :D
 
En fait l'algo est plus efficace car (en gros) il ne parcours pas les cellules situées à droite de celle que je cherche (pour un tableau simple).
 
J'ai conservé l'ancien algo pour la petite histoire, et pour avoir une solution de rechange si le nouveau devenait fou dans un cas tordu :D
 
Merci, pour la piste, c'est exactement ce que je cherchais. Quand on réfléchi à ce problème, intuitivement on se rends compte que pour trouver la position d'une cellule, il faut regarder ce qui se passe dans le coin supérieur gauche du tableau. Mais pour moi, la réflexion était perturbé par le fait que pour limiter la recherche à la partie gauche il falait connaitre l'info recherché :/ J'ai donc passé pas mal de temps avec un papier et un crayon, à chercher une itération qui s'approche de la cellule par le plus court chemin. Jusqu'à ce que je vois des cellules qui bougent, qui change de couleur, cligottent, bref jusqu'à ce que je me réveille avec une matrice imprimée sur la figure :D
 
A+, il me reste l'insertion des colonnes...


---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.
Reply

Marsh Posté le 18-01-2004 à 03:47:07    

mara's dad a écrit :


 
Tu fais comment 'Coté serveur' ?
Tu demande au rédacteur combien de lignes et de colonnes c'est çà ? -> Beaucoup trop limité pour moi :D

bah non, la meme chose que coté client ... mais ça serait moins complexe grace au préexistant


---------------
Hey toi, tu veux acheter des minifigurines Lego, non ?
Reply

Marsh Posté le 18-01-2004 à 11:39:17    

mara's dad a écrit :


Merci, pour la piste, c'est exactement ce que je cherchais. Quand on réfléchi à ce problème, intuitivement on se rends compte que pour trouver la position d'une cellule, il faut regarder ce qui se passe dans le coin supérieur gauche du tableau. Mais pour moi, la réflexion était perturbé par le fait que pour limiter la recherche à la partie gauche il falait connaitre l'info recherché :/


 
Bah si tu n'avais pas dit qu'on pouvait avoir le numéro de ligne facilement ... l'algo que j'ai proposé serait revenu au même que le tien vu qu'il aurait fallu balayer entièrement le tableau de haut en bas pour chaque colonne ...
 
 
J'ai 2 remarques sur le code ... je sais pas si ça améliorera la vitesse mais on peut essayer :
 
- ici :

Code :
  1. for( j=0; j < aCell[i].rowSpan; j++ )
  2.   {
  3.    aCol[ i + j ] += colSpan;
  4.   }


tu vas modifier le tableau aCol sur le nombre de rangée de la cellule or si elle a un rowspan à 20 et que tu sais que la cellule que tu cherches est à la ligne 3 ... tu vas faire 17 assignations en trop. Tu pourrais peut-être faire  

Code :
  1. for( j=0; j <= min (aCell[i].rowSpan, linePos - i); j++)


A noter le < remplacer par <= ou sinon tu mets linePos-i+1 ;)
Par contre un truc que je ne sais pas, c'est si l'interpréteur va réévaluer min(aCell[i].rowSpan,linePos-i) à chaque itération ? Si c'est le cas, vaudrait mieux en stocker le résultat avant la boucle. Je sais pas si tout ça permettra d'accélérer le script mais bon javascript n'a pas l'air très rapide.
 
- Autre remarque, j'ai vu que tu as amélioré l'algorithme dans le sens où tu ne recherches pas à chaque fois la ligne avec la plus petite valeur (où comme je l'avais proposé, celle avec la valeur de la colonne en cours de traitement). C'est pas plus mal dans un sens, car ça évite justement cette recherche.
Mais en fait y a un cas où ça pourrait ralonger le traitement :
A A A A B B B B C C C C
A A A A B B B B C C C C
D F X
 
au départ : 1, 1, 1
cellule A => 5, 5, 1
cellule D => 5, 5, 2 (là tu reviens à la ligne 1 dans ta version)
cellule B => 9, 9, 2
cellule F => 9, 9, 3 (idem)
cellule C => 13, 13, 3
cellule X => BINGO
 
ce que je veux dire, c'est que tu vas faire les cellules B et C pour rien alors que dès que tu as 5, 5, 1 tu devrais te concentrer sur la ligne 3 et tu trouverais X 3 cellules plus loin. Evidemment cela nécéssite de trouver la ligne avec le plus petit numéro mais comme j'avais proposé, ya des manières pour optimiser cela, soit en connaissant le numéro de colonne en cours et en évitant ainsi les comparaisons fastidieuses et aussi dans certains cas de balayer toutes les lignes, soit en repérant le minimum quand tu modifies les valeurs dans aCol.
Enfin je sais pas trop si cela accélèrera le processus ... je pense qu'il faut tester pour voir ... surtout dans les cas courants (mon cas extrême n'est pas forcemment le plus courant).
 

Reply

Marsh Posté le 18-01-2004 à 19:57:08    

1 - for( j=0; i + j <= linePos && j < rowSpan; j++ )
C'est ce que j'avais fais dans un premier temps. En fait cette optimisation avait sautée quand je corrigeais des bugs.
 
2- OK, j'y avais pensé, mais j'ai du mal à être certain que cette optimisation fonctionne dans tous les cas :/
En fait, y'a un contre exemple :
A B C D E F G H I  
J K L M N O P Q R
S S S S S S S S T
U V W X Y Z
Si je cherche Z, en choisissant le plus petit n° de colonne, je vais tester B, C, D, E et K, L, M, N pour rien.
J'ai donc modifié l'algo comme suit :
Si je ne suis pas sur la ligne 1, je reste sur la même ligne i tant que aCol[i] < aCol[i-1] (Edit) et que aCol[i].rowSpan <= aCol[i-1].rowSpan.
 
Ce qui donne :
A, J, S, U, V, W, X, Y et Z !
 

/*
 Cette fonction cherche la position de la cellule passée en paramètre
*/
function getCellPos( oCell )
{
 var aCol = new Array();  // Tableau des positions des colonnes
 var aCell = new Array(); // Tableau des cellules
 var i, j, colSpan, rowSpan;
 var line;
 var linePos = getLinePos( oCell.parentNode );
 
 // Init tableaux
 line = curTable.firstChild;
 i = 1;
 do
 {
  aCell[i] = line.firstChild;
  aCol[i] = 1;
  i++;
  // Ligne suivante
  line = line.nextSibling;
 }
 while( i <= linePos );
 
 // Traitement
 i = 1;
 // Tant que la cellule n'est pas celle qu'on cherche
 while( aCell[i] != oCell )
 {
  // Si la cellule existe dans la ligne
  if( aCell[i] )
  {
   do
   {
    colSpan = aCell[i].colSpan;
    rowSpan = aCell[i].rowSpan;
    // Mise à jour du tableau des position en fonction de colSPan et rowSpan
    for( j=0; i + j <= linePos && j < aCell[i].rowSpan; j++ )
    {
     aCol[ i + j ] += colSpan;
    }
    // Mémorisation de la cellule suivante à traiter dans la ligne
    aCell[i] = aCell[i].nextSibling;
   }
   while( aCell[i] && aCell[i] != oCell && i > 1 && aCol[ i ] < aCol[ i - 1 ] && aCol[i].rowSpan <= rowSpan );
   
   // Ligne suivante
   i += rowSpan;
   
   // On revient sur la première ligne
   if( i > linePos )
   {
    i = 1;
   }
  }
  // Ligne suivante
  else
  {
   i++;
  }
 }
 return( aCol[i] );
}


 
EDIT : Correction il ne faut pas rester sur la même ligne si la cellule suivante a un rowSpan plus grand !


Message édité par Mara's dad le 18-01-2004 à 20:21:54

---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.
Reply

Marsh Posté le 18-01-2004 à 21:13:25    

mara's dad a écrit :


2- OK, j'y avais pensé, mais j'ai du mal à être certain que cette optimisation fonctionne dans tous les cas :/
En fait, y'a un contre exemple :
 
Si je cherche Z, en choisissant le plus petit n° de colonne, je vais tester B, C, D, E et K, L, M, N pour rien.


Ouep je suis d'accord  :D  
 

Citation :

J'ai donc modifié l'algo comme suit :
Si je ne suis pas sur la ligne 1, je reste sur la même ligne i tant que aCol[i] < aCol[i-1] (Edit) et que aCol[i].rowSpan <= aCol[i-1].rowSpan.
Ce qui donne :
A, J, S, U, V, W, X, Y et Z !


 
Heu j'ai pas bien compris pourquoi c'était grave si la prochaine cellule avait un rowSpan supérieure à celui de la prochaine cellule de la ligne au-dessus ?  
 
Et puis, ya un autre contre-exemple (inspiré du tien) mais pour ton code :


A B C D E F G H I  
S S S S S S S S T
J K L M N O P Q R
U U U U U U U U U
V W X Y Z


On va s'attarder sur la ligne J K L M ... alors que ce n'est pas nécéssaire. Peut-être faudrait-t-il plutôt appliquer cette règle quand on est à la ligne de Z et ensuite remonter si nécéssaire d'1 ligne en 1 ligne tout en continuant de l'appliquer puis en redescendant quand c'est possible.
 
Exemple :


A B C C E F G H I  
S S S S S S S S S
J K L M N O P Q R
U U T T D D D D D
V W X Y Z


 
ca ferait dans l'ordre :
A
S
J
U
V
W (car U prend 2 de large)
on peut pas faire le X, on passe à la ligne du dessus
on peut pas faire le T car la ligne dessus a une valeur inférieure ... on remonte encore
K
L
T (on est descendu là)
X
Y
on remonte
mais on peut pas faire le D donc on remonte encore  
M
N
D (on est descendu donc)
et enfin Z
 
Ainsi on économise encore des cellules ... si on continue le script va faire le 20x20 en 0.1 seconde  :lol:  
 
De plus, il ne devrait plus être nécéssaire de faire le

Code :
  1. if( i > linePos )
  2.   {
  3.    i = 1;
  4.   }

 
... sauf que dans le cas d'un tableau avec des cellules prenant toutes uniquement 1 case, ça restera plus rapide.
 

Reply

Marsh Posté le 18-01-2004 à 21:41:53    

Ok, j'ai vu ce PB aussi, je vais voir si je peux modifier le code sans qu'il devienne imcompréhenssible :D
 
Sinon, je viens de faire l'ajout de colonne.
http://www.surleau.org/edit/tab.html
ou
http://www.surleau.com/edit/tab.html


---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.
Reply

Marsh Posté le 20-01-2004 à 00:35:08    

Correction d'un bug + légère optimisation

Code :
  1. /*
  2. Cette fonction cherche la position de la cellule passée en paramètre
  3. */
  4. function getCellPos( oCell )
  5. {
  6. var aCol = new Array();  // Tableau des positions des colonnes
  7. var aCell = new Array(); // Tableau des cellules
  8. var i, j, colSpan, rowSpan;
  9. var line;
  10. var linePos = getLinePos( oCell.parentNode );
  11. var pos;
  12. var sameLine;
  13. // Init tableaux
  14. line = curTable.firstChild;
  15. i = 1;
  16. do
  17. {
  18.  aCell[i] = line.firstChild;
  19.  aCol[i] = 1;
  20.  i++;
  21.  // Ligne suivante
  22.  line = line.nextSibling;
  23. }
  24. while( i <= linePos );
  25. // Traitement
  26. i = 1;
  27. // Tant que la cellule n'est pas celle qu'on cherche
  28. while( aCell[i] != oCell )
  29. {
  30.  // Si la cellule existe dans la ligne
  31.  if( aCell[i] )
  32.  {
  33.   do
  34.   {
  35.    colSpan = aCell[i].colSpan;
  36.    rowSpan = aCell[i].rowSpan;
  37.    sameLine = true;
  38.    // Si rowSpan > 1 il faut compter cette cellule seulement si les positions sont les mêmes pour les lignes en dessous
  39.    if( linePos >= i+1  && rowSpan > 1 )
  40.    {
  41.     pos = aCol[i];
  42.     j=1;
  43.     do
  44.     {
  45.      sameLine = ( aCol[i + j] == pos );
  46.      j++;
  47.     }
  48.     while( sameLine && i + j <= linePos && j < rowSpan );
  49.     // Test OK
  50.     if( sameLine )
  51.     {
  52.      // Mise à jour du tableau des position en fonction de colSPan et rowSpan
  53.      for( j=0; i + j <= linePos && j < rowSpan; j++ )
  54.      {
  55.       aCol[i + j] += colSpan;
  56.      }
  57.      // Mémorisation de la cellule suivante à traiter dans la ligne
  58.      aCell[i] = aCell[i].nextSibling;
  59.     }
  60.     else
  61.     {
  62.      rowSpan = 1;
  63.     }
  64.    }
  65.    else
  66.    {
  67.     aCol[i] += colSpan;
  68.     // Mémorisation de la cellule suivante à traiter dans la ligne
  69.     aCell[i] = aCell[i].nextSibling;
  70.    }
  71.   }
  72.   while( sameLine && aCell[i] && aCell[i] != oCell && i > 1 && aCol[i] < aCol[i - 1] );
  73.   if( aCell[i] == oCell && aCol[i] <= aCol[i - 1] )
  74.   {
  75.    return( aCol[i] );
  76.   }
  77.   // Ligne suivante
  78.   i += rowSpan;
  79.   // On revient sur la première ligne
  80.   if( i > linePos )
  81.   {
  82.    i = 1;
  83.   }
  84.  }
  85.  // Ligne suivante
  86.  else
  87.  {
  88.   i++;
  89.  }
  90. }
  91. return( aCol[i] );
  92. }


 
Edit 2 : Encore un bug corrigé
// Si rowSpan > 1 il faut compter cette cellule seulement si les positions sont les mêmes pour les lignes en dessous


Message édité par Mara's dad le 20-01-2004 à 10:29:35

---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.
Reply

Marsh Posté le 20-01-2004 à 07:38:43    

énorme :love: !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Reply

Marsh Posté le 20-01-2004 à 10:30:01    

Merci :D


---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.
Reply

Marsh Posté le 26-01-2004 à 14:35:39    

Voilà pour ceux que ça intéresse l'algorithme qu'on a finalement obtenu :
 

Code :
  1. function getCellPos( oCell ) { 
  2.   var aCol = new Array();  // Tableau des positions des colonnes   
  3.   var aCell = new Array(); // Tableau des cellules   
  4.   var curLine; // Numéro de ligne en cours de traitement  
  5.   var j, colSpan, rowSpan, rowMax; 
  6.   var line; 
  7.   var aRow = new Array(); // Pile contenant le numéro des lignes de retour
  8.   var nRow = 0; // Nombre d'éléments dans la pile
  9.   var linePos = getLinePos( oCell.parentNode ); // Position de la cellule recherchée  
  10.   // Init tableaux   
  11.   line = curTable.firstChild; 
  12.   for (curLine = 1; curLine <= linePos; curLine++) { 
  13.     aCell[curLine] = line.firstChild; // Première cellule de la ligne  
  14.     aCol[curLine] = 1; 
  15.     line = line.nextSibling;  // Ligne suivante  
  16.   } 
  17.   // Traitement   
  18.   curLine = 1;
  19.   // Tant que la cellule n'est pas celle qu'on cherche   
  20.   while( aCell[curLine] != oCell ) { 
  21.    
  22.     // On récupère la taille de la cellule  
  23.     colSpan = aCell[curLine].colSpan;
  24.     rowSpan = aCell[curLine].rowSpan;
  25.    
  26.     // On mémorise la prochaine cellule à traiter  
  27.     aCell[curLine] = aCell[curLine].nextSibling; 
  28.     // Mise à jour du tableau des positions  
  29.     rowMax = Math.min(curLine + rowSpan - 1, linePos);
  30.     for (j = curLine; j <= rowMax; j++) 
  31.       aCol[j] += colSpan;
  32.     // Si la ligne dessous cette cellule a un indice inférieur, on y va  
  33.     if (rowMax < linePos && aCol[rowMax + 1] < aCol[curLine]) {
  34.       // Si la ligne dessus à un indice strictement supérieur, on empile la ligne courante   
  35.       // Rmq : La première ligne est empilée par défaut
  36.       if (curLine == 1 || aCol[curLine - 1] > aCol[curLine]) { 
  37.         aRow[nRow] = curLine; 
  38.         nRow++;
  39.       } 
  40.       curLine = rowMax + 1;
  41.     } else {
  42.       // Sinon on remonte à la dernière ligne empilée si la ligne précédente a un indice <=
  43.       if (curLine > 1 && aCol[curLine - 1] <= aCol[curLine]) {
  44.         nRow--;
  45.         curLine = aRow[nRow]; 
  46.       }
  47.     }
  48.   }
  49.   return( aCol[curLine] );
  50. }


 
et une deuxième méthode surprenante proposée par Mara's dad :
 

Code :
  1. function getCellPos( oCell ) { 
  2.   var nbCols = getNbCols();
  3.   var cellWidth = ( curTable.offsetWidth - curTable.offsetLeft ) / nbCols;
  4.   return( Math.round( oCell.offsetLeft / cellWidth ) + 1 );
  5. }


 
Et enfin les performances (en sec) de chaque algo sur un tableau de 20x20 cases pour obtenir la position de chacune des cases (interêt minime ... juste pour faire des comparaisons):


            IE  | MOZ  
1er  algo  0.92 | 1.88
2eme algo  2.10 | 0.57


 :pt1cable:

Reply

Marsh Posté le 26-01-2004 à 16:17:50    

Autre version de la deuxième méthode :

Code :
  1. function getCellPos( oCell ) { 
  2. return( Math.round( oCell.offsetLeft * getNbCols() / curTable.offsetWidth ) + 1 );}

 
Les perfs sont les mêmes, j'ai juste fait le calcul en 1 seule ligne.
C'est pas évident au premier abord, mais en fait curTable.offsetLeft vaut 0 ! donc:
 

Code :
  1. var nbCols = getNbCols(); 
  2. var cellWidth = ( curTable.offsetWidth - curTable.offsetLeft ) / nbCols; 
  3. return( Math.round( oCell.offsetLeft / cellWidth ) + 1 );


Est équivalent à :

Code :
  1. var cellWidth = curTable.offsetWidth / getNbCols(); 
  2. return( Math.round( oCell.offsetLeft / cellWidth ) + 1 );


Donc à :

Code :
  1. return( Math.round( oCell.offsetLeft / ( curTable.offsetWidth / getNbCols() ) ) + 1 );


Or, A / ( B / C ) = ( A * C ) / B !
( Pour ceux qu'auraient oublié, par exemple, diviser par un demi revient à multiplier par deux :D )
Donc :

Code :
  1. return( Math.round( oCell.offsetLeft * getNbCols() / curTable.offsetWidth ) + 1 );


 
L'appel systématique de la fonction getNbCols() ne coûte quasiment rien, c'est la division qui est catastophique avec IE.
 
Sous IE, une seule division est plus lente que le parcours de plusieurs nodes dans TBODY !


Message édité par Mara's dad le 26-01-2004 à 16:18:39

---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.
Reply

Marsh Posté le 26-01-2004 à 16:48:39    

mara's dad a écrit :


L'appel systématique de la fonction getNbCols() ne coûte quasiment rien, c'est la division qui est catastophique avec IE.
 
Sous IE, une seule division est plus lente que le parcours de plusieurs nodes dans TBODY !


 
détrompes-toi  :pt1cable:  
 
J'ai fait quelques tests :
 
- ta fonction avec juste des valeurs fixes à la place de oCell.offsetLeft*getNbCols() et de curTable.offsetWidth : 0.03s
- je rajoute la ligne getNbCols() sans récupérer la valeur retournée (je fais toujours la division avec les valeurs fixes): 0.13s
- je rajoute la ligne oCell.offsetLeft; (en n'utilisant toujours pas la valeur retournée : 3.00s  
- je rajoute la ligne curTable.offsetWidth; : 3.00s
Le fait de mettre l'une , l'autre ou les 2 dernières lignes amènent au même temps d'exécution.
 
Donc apparement IE fait un savant calcul à chaque fois (peut-être le même algo que tu voulais  :pt1cable: ) pour connaître la position d'un objet, ce qui lui prend beaucoup de temps. Moz se débrouille mieux apparement ... il garde peut-être les coordonnées des différents objets ?

Reply

Marsh Posté le 26-01-2004 à 21:05:46    

T'as raison, c'est pas la division, mais l'accès aux propriétés offset* !
C'est plus logique comme çà.

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed