1

yop,

J'ai besoin d'un algo très élémentaire dans une fonction, pour supprimer un élément dans un tableau. C'est amha un truc qui doit être servi à tous les élèves de première année en étude d'info.
Voilà ce que j'ai écrit :
=> Avec memmove :void remove_element (int* array, int* element_count, int removeme) { for (int i = 0; i < *element_count; i ++) { if (array [i] == removeme) { memmove (&(array [i]), &(array [i + 1]), (*element_count - i - 1) * sizeof (int)); (*element_count) --; array = realloc (array, *element_count); return; } } }
=> Avec une boucle for :void remove_element2 (int* array, int* element_count, int removeme) { for (int i = 0; i < *element_count; i ++) { if (array [i] == removeme) { for (; i < *element_count - 1; i ++) array [i] = array [i + 1]; (*element_count) --; array = realloc (array, *element_count); return; } } }
Je voulais savoir s'il y avait une méthode plus rapide qu'une autre, meilleure qu'une autre ou que sais-je encore, bref, laquelle privilégier, parce que perso je m'en fous et je vois pas de différence notable. A noter que appeler memmove avec une longueur nulle semble être valide : http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-October/011065.html

Merci d'avance.
avatar<<< Kernel Extremist©®™ >>>
Feel the power of (int16) !

2

memmove() est optimisée, tu as tout intérêt à l'utiliser quand tu le peux.
avatarZeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

3

Ah ok, j'ignorais, alors merci. smile
avatar<<< Kernel Extremist©®™ >>>
Feel the power of (int16) !

4

Petites remarques en vrac :

- Ta fonction fait en réalité deux choses : elle cherche l'indice d'un élément dans ton tableau, puis une fois qu'elle a cet indice elle supprime l'élément en question. J'aurais tendance à séparer ces deux étapes en deux fonctions différentes, étant donné qu'il est assez probable que tu puisses réutiliser l'une ou l'autre (et même surement les deux)
- Selon le nombre d'itérations en moyenne dans la boucle, conserver "*element_count" dans une variable "int" locale pour éviter de déréférencer plusieurs fois pourrait être intéressant
- Je ne suis pas sûr qu'il soit garanti que "realloc" ne retourne jamais NULL quand on demande une taille de bloc plus petite (ça ne serait pas très logique, mais ça mérite peut-être d'être vérifié)
avatarAll right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)

5

lea tab,a0

move.w Indiceasupprimer,d0
lsl.w #1 ou 2 suivant la taille de ton element,d0
add.w d0,a0
et ensuite quelques move.w ou move.l et hop !!


Asm power !!


GT dehors
avatar< SCPCD > j'aurais du dire "les doigts dans le cul vu que le java c'est de la merde"
Je suis Goto !

6

Disons que bien en marge de la rapidité d'un algo ou d'un autre, ou encore de memmove vs une méthode maison (pour info : memmove est très rapide et presque toujours à privilégier pour les données d'une certaine taille, en plus c'est plus lisible qu'une boucle for) le plus gros problème de performance dans ta méthode c'est l'appel à realloc.
Garde en tête que malloc et consorts sont des opérations lourdes, même sur un PC (plus de mémoire = plus de boulot pour la gérer), et que ça implique en général un syscall donc une interruption de ton programme.
En fonction de la taille usuelle de ton tableau, il vaut mieux partir avec une taille prédéfinie (par exemple 4 éléments) et doubler celle-ci lorsqu'on arrive au bout. De la même manière, lorsque plus de 50% de l'espace est inutilisé, on peut songer à diviser par deux.
En fonction des opérations que tu fais, tu peux utiliser cette approche pour ne pas avoir à déplacer les éléments suivants lorsque tu en retires un (il te suffit de le mettre à une valeur "case vide" style -1). Il te faut alors "compresser" la table lors d'une réallocation vers une taille plus petite et chercher la première "case vide" en cas d'insertion.
avatarHighway Runners, mon jeu de racing à la Outrun qu'il est sorti le 14 décembre 2016 ! N'hésitez pas à me soutenir :)

https://itunes.apple.com/us/app/highway-runners/id964932741

7

GT Turbo -> Lol grin Evidemment, j'adore toujours autant le 68k, mais on peut aussi faire du C de manière élégante, dans les règles de l'art, simplement, la manière de penser et d'aborder les problèmes est différente. Mais tant qu'on recherche pas l'impossible, on peut rester dans le beau. smile
Zeph (./4) :
- Ta fonction fait en réalité deux choses : elle cherche l'indice d'un élément dans ton tableau, puis une fois qu'elle a cet indice elle supprime l'élément en question. J'aurais tendance à séparer ces deux étapes en deux fonctions différentes, étant donné qu'il est assez probable que tu puisses réutiliser l'une ou l'autre (et même surement les deux)

Bien vu. Je suis au début du codage de ce que je fais, donc a priori, la nécessité que tu décris devrait arriver à un moment où l'autre. smile
Zeph (./4) :
- Selon le nombre d'itérations en moyenne dans la boucle, conserver "*element_count" dans une variable "int" locale pour éviter de déréférencer plusieurs fois pourrait être intéressant

Alors ça je me demandais justment. *element_count n'étant pas déclaré volatile, n'est-il pas considéré comme constant par le compilateur ? aucune fonction n'est appelée dans la boucle.
Zeph (./4) :
- Je ne suis pas sûr qu'il soit garanti que "realloc" ne retourne jamais NULL quand on demande une taille de bloc plus petite (ça ne serait pas très logique, mais ça mérite peut-être d'être vérifié)

realloc peut retourner NULL, tout à fait. Le standard ne garantit rien, même quand on rétrécit un espace. Donc une implémentation de <realloc()> comme <malloc(newsize), memcpy(new, old, size), free(old)> serait parfaitement valide, et pourrait échouer. Cependant, je code pour PedroM et AMS, où ça ne peut pas échouer.
Zerosquare (./2) :
memmove() est optimisée, tu as tout intérêt à l'utiliser quand tu le peux.

En fait, étrangement, l'appel à memmove prend 50 octets de plus que le for ! Et l'itération a de très fortes chances d'être très rapide, pas plus de 10 boucles. Et sur TI, je privilégie en général la place, tandis que le domaine d'utilisation de ce code ne demande pas de vitesse. J'ai donc gardé la version <for>


Brunni -> point de vue très intéressant, j'y répodn un peu plus tard ! C'est en effet un choix, expliquable, qui se pose dès qu'on décide de gérer la mémoire à la main. J'y reviens sous peu. smile
avatar<<< Kernel Extremist©®™ >>>
Feel the power of (int16) !

8

Folco (./7) :
Alors ça je me demandais justment. *element_count n'étant pas déclaré volatile, n'est-il pas considéré comme constant par le compilateur ? aucune fonction n'est appelée dans la boucle.
Oui, le compilo devrait optimiser ça, c'est un cas simple.
Folco (./7) :
En fait, étrangement, l'appel à memmove prend 50 octets de plus que le for ! Et l'itération a de très fortes chances d'être très rapide, pas plus de 10 boucles. Et sur TI, je privilégie en général la place, tandis que le domaine d'utilisation de ce code ne demande pas de vitesse. J'ai donc gardé la version <for>
T'avais pas précisé que c'était sur TI et que tu voulais une optimisation taille grin
C'est pas surprenant sinon, memmove() est optimisée en vitesse, pas en taille.
avatarZeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

9

Euh... cheeky
Le linking à memmove est dynamique, pas statique, c'est donc le push/pop des arguments sur la pile qui prend cette taille incommensurable, mon cher Zerosquare. Mais tu peux pas le deviner, je te l'accorde ; certaines fonctions standard, non incluses dans AMS, sont en effet implémentées dans tigcclib, qui est statique. smile
avatar<<< Kernel Extremist©®™ >>>
Feel the power of (int16) !

10

50 octets pour un appel de fonction ?! Hé ben... m'étonne pas que tu n'aimes pas programmer en C sur TI grin
avatarZeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

11

Ben suffit de regarder les .s pour s'en convaincre, c'est un truc à n'utiliser plus que des OS écrits en assembleur sur cartes perforées, je te jure. grin
avatar<<< Kernel Extremist©®™ >>>
Feel the power of (int16) !

12

GT Turbo (./5) :
lea tab,a0

move.w Indiceasupprimer,d0
lsl.w #1 ou 2 suivant la taille de ton element,d0
add.w d0,a0
et ensuite quelques move.w ou move.l et hop !!


Asm power !!


GT dehors
Même pas un movem ?


Folco > Si tu supprimes ou insères souvent des données, tu devrais peut-être penser à utiliser une liste chaînée ?
Enfin ça dépend de ton utilisation de cette fameuse liste.

13

Tiens, c'est pas idiot, mais là ça ne serait pas relevant (#triclasse#). Mes éléments font la taille d'un pointeur, donc je me vois mal allouer un bloc de mem pour y loger 1 pointeur + deux autres pour linker les maillons ^^ Et j'ai pas besoin de perf, mais je garde l'idée, c'est pas mal en effet.
avatar<<< Kernel Extremist©®™ >>>
Feel the power of (int16) !

14

(grin)

15

Pen j'y ai pensé, mais cela depend de la taille des elements et de leur nombre, car il faut un certain nb de move.l par exemple pour que movem.l lui soit supérieur smile (Je parle bien sur en vitesse )


GT Compteur de cycles (Ca fait longtemps que j'ai pas fait cela wink )
avatar< SCPCD > j'aurais du dire "les doigts dans le cul vu que le java c'est de la merde"
Je suis Goto !

16

- ton array doit rester trie?
sinon quand tu remove tu peux swapper avec le(s) dernier(s) elements. (ie: copier les derniers elements dans le trou laisse par la suppression)
pas mal de gains possibles si t'as des gros arrays et que tu remove peu d'elements a chaque fois.

- pourquoi faire un realloc a chaque call? c'est pas grave si l'array est un peu plus gros que necessaire. tu peux le shrink/realloc a la fin quand t'as fini de remove, ou que le delta taille reelle allouee - nombre d'elements actifs devient trop grand
avatarHURRRR !

17

Folco (./1) :
yop,

J'ai besoin d'un algo très élémentaire
#sifflote#
avatarZeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

18

(?)
avatarHURRRR !

19

Ben effectivement il y a plein de façons optimisées de faire des tableaux dynamiques, mais la question de Folco ne portait pas là-dessus ^^
avatarZeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

20

Bear -> oui, je sais plus où, j'ai pas besoin que ma liste soit triée, et je mets le dernier élément à la place de celui que je vire en effet.

Sinon, pour ce que tu proposes au niveau de la gestion de la mémoire, c'est la même chsoe que pour Brunni. Mes tableaux sont de petite taille, et une suppression est une possibilité qui intervient rarement.
Retenir la taille réelle, puis faire des tests pour savoir si oui ou non il faut diminuer ou rétrécir lors des prochains ajouts/suppressions représente un overhead en temps systématique, et en taille qui ne vaudra pas la poignée d'octets qu'il y a à gagner. Le plus petit en place consiste donc à réallouer de manière inconditionnelle, sachant que le coût en perf est rarement payé, et que les perfs n'importent de toute façon pas vu ce que ce code fait (ajout/suppression de widgets dans un layout).

Evidemment, si mon tableau contenait les missiles d'un shoot'em up, j'aobrderais pas ça du tout comme ça ^^
avatar<<< Kernel Extremist©®™ >>>
Feel the power of (int16) !

21

Folco (./20) :
Evidemment, si mon tableau contenait les missiles d'un shoot'em up, j'aobrderais pas ça du tout comme ça ^^


GT calin Folco
avatar< SCPCD > j'aurais du dire "les doigts dans le cul vu que le java c'est de la merde"
Je suis Goto !

22

./17> ha. ben jsais pas ca me paraissait tres elementaire comme suggestion non? grin
mais ok ^^
avatarHURRRR !

23

bearbecue (./22) :
ha. ben jsais pas ca me paraissait tres elementaire comme suggestion non?

Ca l'était, t'inquiète, j'ai bien pensé à tout ça avant d'écrire, mais ce que j'ai écrit, c'est par choix, pas par ignorance ^^
avatar<<< Kernel Extremist©®™ >>>
Feel the power of (int16) !

24

Genre embarrassed

25

Appelle-moi con grin
avatar<<< Kernel Extremist©®™ >>>
Feel the power of (int16) !

26

Call : con n'existe pas !

27

gni
avatar<<< Kernel Extremist©®™ >>>
Feel the power of (int16) !

28

bah jsais pas alors, vu que tu t'en fous de l'ordre, pourquoi tu fais pas juste comme ca:
void remove_element(int* array, int* element_count, int removeme) { for (int i = 0, stop = *element_count; i < stop; i++) { if (array[i] == removeme) { array[i] = array[stop - 1]; (*element_count)--; array = realloc(array, *element_count); return; } } }

? grin c'est justement plus simple, plus rapide meme pour les petits arrays, et pas de question a se poser pour memmove ou boucle a la mano, vu que tu remove de toutes facons qu'un element a la fois smile
(et vu que memmove est un intrinsic sur pas mal de compilos, un memmove de taille constante connue au compile-time sera quasiment toujours plus efficace que la version generique avec un nombre d'elements variable que tu utilises)

et sinon, t'as teste le code genere par ton compilo ? t'as mesure le temps pris par les deux fonctions sur un cas d'utilisation reel?

et avec un peu de bol ton implem de realloc ne fait rien si la taille est plus petite (c'est le cas dans toutes les CRT que je connais en tout cas), donc ca ne prendra quasiment pas de temps (mais du coup ca ne sert a rien de l'appeler)
avatarHURRRR !

29

Ah merde, j'ai dit que je me foutais de l'ordre ? C'est pas ce que je voulais dire alors, au contraire, parce que sinon je connais laméthode que tu proposes, je l'utilise pour les tableaux non ordonnés ^^
bearbecue (./28) :
et sinon, t'as teste le code genere par ton compilo ? t'as mesure le temps pris par les deux fonctions sur un cas d'utilisation reel?

non, mais je connais le code de memmove de PedroM cheeky
bearbecue (./28) :
et avec un peu de bol ton implem de realloc ne fait rien si la taille est plus petite (c'est le cas dans toutes les CRT que je connais en tout cas), donc ca ne prendra quasiment pas de temps (mais du coup ca ne sert a rien de l'appeler)

Intéressant, et pas idiot, oui. Ceci dit, je suis sur TI, à m'amuser, rien de critique. Ceci dit, je retiens pour le jour où je bosserai dans l'info magic grin
avatar<<< Kernel Extremist©®™ >>>
Feel the power of (int16) !

30

k grin
avatarHURRRR !