J'aimerai faire un décalage dans un tableau t=[2,3,7,9,0,1] et je veut pouvoir ajouter un element a une k-eme case est-ce que c'est possible de tel sorte que j'ai par exemple t=[2,3,7,11,9,0,1]
J'ai pensé a la méthode ou je copie le premier element et ensuite j'ajoute l'element puis le reste du tableau. Mais cette methode peut prendre beaucoup de temps si le tableau est plus grand.
Coucou ! Excuse moi, mais elle est ou la question? Tu veux une méthode pour le faire? Un algo?
Il me semble (je me trompe peut-être, mais je crois pas) que ce que tu as proposé est bon, puisque dans tous les cas, il va y avoir un décalage, si tu veux ajouter un element a la k-eme position, tu vas devoir décaler tous ceux qui viennent après. N'oublie pas d'augmenter la taille de ton tableau de 1 pour pas avoir de segfault et pour ce qui est du temps, tu devrais pas t'inquiéter pour ça ^^'
« Je n’ai pas besoin de preuve. Les lois de la nature, contrairement aux lois de la grammaire, ne permettent aucune exception. » D. Mendeleïev
Ce que je voulais dire c'est que je vais bien ecraser la valeur k en la remplacer par ma valeur et j'aggrandit mon tableau mais du coup je vais devoir décaler tout le reste de mon tableau. Et quand je veut dire que ca va prendre du temp c'est dans le temps d'éxécution quand mon tableau peut être un tableau de 200 case. Ce que je demande c'est s'il n' y a pas une méthode qui prendrait moins de temps à l'execution et qui serai moins lourd.
Beaucoup de temps ? Tu penses à quelle ordre de grandeur ? On a des PC qui gèrent des mondes ouverts immenses, en HD avec des textures loin d'être dégeulasses et de méchants calcul pluôt complexes avec en plus l'OS qui tourne derrrière et pas que... Même in PI est capable d'émuler une PSX ou une dreamcast et c'est loin d'être un gros PC.
Donc à partir de quel moment faire un simple décalage dans une table prend (significativement) du temps ? Quelles sont tes contraintes ? C'est une opréation tellement basique que ça doit probablement arriver des milliers fois entre le moment tu appuies sur une touche et le moment où tu la relâches.
Ne pose pas la question, fais le et si c'est effectivement trop lent en comparaison de ce que tu en attends (et si jamais tu arrives à t'en rendre compte pour commencer) alors tu pourras revinir ici en disant "j'ai fais ça et c'est trop lent".
Effectivement, c’est une opération couteuse (à relativiser), mais y a pas le choix.
Le tableau est une structure de données qui à ses forces et ses faiblesses, tu mets justement le doigts sur une de ses principales faiblesses. Entre autres choses, un tableau permet l’accès arbitraire (accès à n’importe quelle case en temps constant) grâce à un simple calcul d’adresse, en contre partie l’ajout ailleurs qu’à la fin est couteux.
L’exemple inverse est la liste chaînée, l’ajout est en temps constant, n’importe où dans la liste, mais l’accès aux éléments ne peut se faire que dans l’ordre (pour accéder à l’élément \(n\) il faut d’abord accéder à l’élément \(n-1\)).
L’exemple inverse est la liste chaînée, l’ajout est en temps constant, n’importe où dans la liste, mais l’accès aux éléments ne peut se faire que dans l’ordre (pour accéder à l’élément \(n\) il faut d’abord accéder à l’élément \(n-1\)).
Un ajout dans une chaîne nécessite de la parcourir à priori. Si tu veux aller à n pour y ajouter un élément, il faut passer de la même manière par les N- pour l'atteindre (ou par les N+ en double). ajouter en N=250 sera sensiblement plus coûteux qu'ajouter en N=2 (pour une simple).
Je peux me tromper, mais je pense que la table reste (en moyenne) plus performante. Après, on ne parle pas d'une minute ou même de 10 secondes, mais de quelques µs... Et encore. Le PO parle d'une "grosse" table de 200 entiers, ce n'est rien du tout. Perso, il ne me viendrait même pas à l'esprit de me poser la question ou alors si je code pour un MO5 et encore...
Après, une solution ne se détermine pas simplement sur une impression. Encore une fois, il faut définir ce que tu entends par "lent". Un Os qui démarre en 15 minutes c'est lent, après qu'il démarre en 15 secondes ou en 15.2, je m'en fiche, cela ne fait aucune vraie différence dans l'absolu, les 2 sont suffisamment rapides pour moi.
Si tu dois faire des insertions occasionelles, ce sera invisible, si tu dois en faire 300 à chaque tour de programme, il faut effectivement envisager une autre soluiton, ptêt même que tu as un problème de conception plus profond.
Je ne donnais la liste chaînée qu’à titre d’exemple.
L’ajout est en temps constant mais il faut effectivement d’abord atteindre l’élément où doit être ajouté l’élément avant de pouvoir faire l’ajout, mais ça ne fait pas partie de l’ajout. Contrairement aux tableaux où le décalage n’est fait que pour l’ajout, on peut très bien avoir/conserver un pointeur vers un élément plus près pour une autre raison dans une liste chaînée.
Décaler éléments d'un tableau
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
« Je n’ai pas besoin de preuve. Les lois de la nature, contrairement aux lois de la grammaire, ne permettent aucune exception. »
D. Mendeleïev
Bonhomme !! | Jeu de plateforme : Prototype.
« Je n’ai pas besoin de preuve. Les lois de la nature, contrairement aux lois de la grammaire, ne permettent aucune exception. »
D. Mendeleïev
Bonhomme !! | Jeu de plateforme : Prototype.