Bonjour,
J'ai déjà rencontré ce prb et je l'avais solutionné de manière "batarde",
mais à force je me dis qu'il faudrait que je découvre un peu le fond du
prb....
soit une variable short* toto[4], qqsoit i toto[i] = (short*)malloc(64);
soit une fonction f déclarée par : void f(short param[4][64]);
comment caster "proprement" la variable toto pour la passer à f ?
On Wed, 30 Mar 2005 17:39:55 +0200, Franck Branjonneau :
La raison de la suite des tailles successives du *est* phi.
Non. Le rapport entre deux tailles successives tend vers phi (quand le nombre d'allocations tend vers l'infini).
D'où ma question : est-il obligatoire que les tailles successives forment une suite de raison constante ? Ne serait-il pas plus simple d'implémenter directement la règle
taille[n+1]= somme (taille[i], i=0..(n-1)) ?
Plus simple, je ne sais pas ; je ne connais rien de plus simple que de multiplier l'ancienne taille par deux, et la multiplier par 1,5 n'est pas très compliqué non plus. (Pour des facteurs plus complexe, je crois que j'utiliserais une table.)
Tu présupposes une représentation binaire des nombres ;
Parce que la norme l'exige, au moin en ce qui concerne les types entiers.
moi je présuppose une représentation de Bergman et je dis : il n'y a rien de plus simple que de multiplier par phi.
Seulement, une telle implémentation n'est pas conforme. Il faut dire que les implémentations hardware n'en courent pas la rue non plus.
Quant à la conformité : d'après ce que je comprends, pour être conforme aux exigeances de complexité, il faut une expression qui grandit au moins aussi vite que k^n, pour un k arbitraire.
Où se trouve cette exigence ?
Indirectement, à travers les exigences de la complexité amortie de push_back.
Je ne crois pas que ta formule convient, formellement, mais je ne suis pas sûr -- est-ce qu'on peut prouver qu'il existe un n et un k tel que pour tout i > n, taille[ i ] >= k^i ?
k = i = 1; taille[i] = k^i convient.
En effet. Mais avec une expression comme k^i, avec k == 1, le tableau ne va pas grandir très vite. Il y a aussi une exigence de k > 1 que j'ai oublié de préciser.
Aussi, on peut, en toute légitimité, poser la question de la signification d'une telle exigeance dans la mésure que n a une borne supérieur (dictée par la taille de la mémoire virtuelle ou la taille d'un pointeur). En choisissant k suffisamment petit, on peut rendre n'importe quelle formule conforme dans le domaine possible. En fait, parler d'un comportement asymtotique sur une fonction dont le domaine est borné n'a pas de sens. (Mais je crois que l'intention de la norme est assez claire.)
Je ne comprends pas. La de borne supérieure ? (de mémoire finie ? de taille de pointeur ?)
De l'un ou l'autre. Le fait est qu'il y a toujours une borne supérieure absolue pour la taille d'un vector. (Y compris avec des allocator exotique qui ont des pointer bizarre.) Une exigence asymtotique n'a pas beaucoup d'utilité si je constate que je n'approcherai à l'asymtote que lorsque la table contiendra 2^256 éléments, et qu'avant ça, je suis nettement moins rapide que voulu.
En fait, étant donné la taille limitée de la mémoire adressable, la solution la plus simple (et 100% conforme), c'est d'allouer toute la mémoire disponible immédiatement dans le constructeur. Je n'aurais non seulement un temps constant amorit pour push_back, j'aurais un temps constant tout court.
Évidemment, ça crée une certaine risque (et même une risque certaine) des exceptions bad_alloc dans la reste du programme. Mais enfin, on ne peut pas tout avoir:-).
-- James Kanze GABI Software Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Franck Branjonneau wrote:
kanze@gabi-soft.fr écrivait:
Fabien LE LEZ wrote:
On Wed, 30 Mar 2005 17:39:55 +0200, Franck Branjonneau
<fasbjx@free.fr>:
La raison de la suite des tailles successives du *est*
phi.
Non. Le rapport entre deux tailles successives tend vers
phi (quand le nombre d'allocations tend vers l'infini).
D'où ma question : est-il obligatoire que les tailles
successives forment une suite de raison constante ? Ne
serait-il pas plus simple d'implémenter directement la
règle
taille[n+1]= somme (taille[i], i=0..(n-1)) ?
Plus simple, je ne sais pas ; je ne connais rien de plus
simple que de multiplier l'ancienne taille par deux, et la
multiplier par 1,5 n'est pas très compliqué non plus. (Pour
des facteurs plus complexe, je crois que j'utiliserais une
table.)
Tu présupposes une représentation binaire des nombres ;
Parce que la norme l'exige, au moin en ce qui concerne les types
entiers.
moi je présuppose une représentation de Bergman et je dis : il
n'y a rien de plus simple que de multiplier par phi.
Seulement, une telle implémentation n'est pas conforme. Il faut
dire que les implémentations hardware n'en courent pas la rue
non plus.
Quant à la conformité : d'après ce que je comprends, pour
être conforme aux exigeances de complexité, il faut une
expression qui grandit au moins aussi vite que k^n, pour un
k arbitraire.
Où se trouve cette exigence ?
Indirectement, à travers les exigences de la complexité amortie
de push_back.
Je ne crois pas que ta formule convient, formellement, mais
je ne suis pas sûr -- est-ce qu'on peut prouver qu'il existe
un n et un k tel que pour tout i > n, taille[ i ] >= k^i ?
k = i = 1; taille[i] = k^i convient.
En effet. Mais avec une expression comme k^i, avec k == 1, le
tableau ne va pas grandir très vite. Il y a aussi une exigence
de k > 1 que j'ai oublié de préciser.
Aussi, on peut, en toute légitimité, poser la question de la
signification d'une telle exigeance dans la mésure que n a
une borne supérieur (dictée par la taille de la mémoire
virtuelle ou la taille d'un pointeur). En choisissant k
suffisamment petit, on peut rendre n'importe quelle formule
conforme dans le domaine possible. En fait, parler d'un
comportement asymtotique sur une fonction dont le domaine
est borné n'a pas de sens. (Mais je crois que l'intention de
la norme est assez claire.)
Je ne comprends pas. La de borne supérieure ? (de mémoire
finie ? de taille de pointeur ?)
De l'un ou l'autre. Le fait est qu'il y a toujours une borne
supérieure absolue pour la taille d'un vector. (Y compris avec
des allocator exotique qui ont des pointer bizarre.) Une
exigence asymtotique n'a pas beaucoup d'utilité si je constate
que je n'approcherai à l'asymtote que lorsque la table
contiendra 2^256 éléments, et qu'avant ça, je suis nettement
moins rapide que voulu.
En fait, étant donné la taille limitée de la mémoire adressable,
la solution la plus simple (et 100% conforme), c'est d'allouer
toute la mémoire disponible immédiatement dans le constructeur.
Je n'aurais non seulement un temps constant amorit pour
push_back, j'aurais un temps constant tout court.
Évidemment, ça crée une certaine risque (et même une risque
certaine) des exceptions bad_alloc dans la reste du
programme. Mais enfin, on ne peut pas tout avoir:-).
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
On Wed, 30 Mar 2005 17:39:55 +0200, Franck Branjonneau :
La raison de la suite des tailles successives du *est* phi.
Non. Le rapport entre deux tailles successives tend vers phi (quand le nombre d'allocations tend vers l'infini).
D'où ma question : est-il obligatoire que les tailles successives forment une suite de raison constante ? Ne serait-il pas plus simple d'implémenter directement la règle
taille[n+1]= somme (taille[i], i=0..(n-1)) ?
Plus simple, je ne sais pas ; je ne connais rien de plus simple que de multiplier l'ancienne taille par deux, et la multiplier par 1,5 n'est pas très compliqué non plus. (Pour des facteurs plus complexe, je crois que j'utiliserais une table.)
Tu présupposes une représentation binaire des nombres ;
Parce que la norme l'exige, au moin en ce qui concerne les types entiers.
moi je présuppose une représentation de Bergman et je dis : il n'y a rien de plus simple que de multiplier par phi.
Seulement, une telle implémentation n'est pas conforme. Il faut dire que les implémentations hardware n'en courent pas la rue non plus.
Quant à la conformité : d'après ce que je comprends, pour être conforme aux exigeances de complexité, il faut une expression qui grandit au moins aussi vite que k^n, pour un k arbitraire.
Où se trouve cette exigence ?
Indirectement, à travers les exigences de la complexité amortie de push_back.
Je ne crois pas que ta formule convient, formellement, mais je ne suis pas sûr -- est-ce qu'on peut prouver qu'il existe un n et un k tel que pour tout i > n, taille[ i ] >= k^i ?
k = i = 1; taille[i] = k^i convient.
En effet. Mais avec une expression comme k^i, avec k == 1, le tableau ne va pas grandir très vite. Il y a aussi une exigence de k > 1 que j'ai oublié de préciser.
Aussi, on peut, en toute légitimité, poser la question de la signification d'une telle exigeance dans la mésure que n a une borne supérieur (dictée par la taille de la mémoire virtuelle ou la taille d'un pointeur). En choisissant k suffisamment petit, on peut rendre n'importe quelle formule conforme dans le domaine possible. En fait, parler d'un comportement asymtotique sur une fonction dont le domaine est borné n'a pas de sens. (Mais je crois que l'intention de la norme est assez claire.)
Je ne comprends pas. La de borne supérieure ? (de mémoire finie ? de taille de pointeur ?)
De l'un ou l'autre. Le fait est qu'il y a toujours une borne supérieure absolue pour la taille d'un vector. (Y compris avec des allocator exotique qui ont des pointer bizarre.) Une exigence asymtotique n'a pas beaucoup d'utilité si je constate que je n'approcherai à l'asymtote que lorsque la table contiendra 2^256 éléments, et qu'avant ça, je suis nettement moins rapide que voulu.
En fait, étant donné la taille limitée de la mémoire adressable, la solution la plus simple (et 100% conforme), c'est d'allouer toute la mémoire disponible immédiatement dans le constructeur. Je n'aurais non seulement un temps constant amorit pour push_back, j'aurais un temps constant tout court.
Évidemment, ça crée une certaine risque (et même une risque certaine) des exceptions bad_alloc dans la reste du programme. Mais enfin, on ne peut pas tout avoir:-).
-- James Kanze GABI Software Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
