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 ?
Il peut allouer ce qu'il veut, tant que ça suit une croissance géométrique, le coefficient ne vaut pas forcément sqrt(2)
Il me semble avoir lu cependant que selon certains critères, sqrt(2) est le facteur idéal. Ce qui est certain, c'est qu'avec un facteur de 2 (qui était le facteur le plus fréquent au début), la somme des tailles des blocs libérés ne suffirait jamais à une nouvelle allocation ; pour tout multiple strictement inférieur à 2, on y arrivera éventuellement.
Je crois qu'il faut pour cela que le facteur soit inférieur au "nombre d'or" (1 + sqrt(5))/2 == 1.618... mais je me ne souviens plus des détails.
À vrai dire, je ne vois pas l'intérêt de sqrt(2) quand 1,5 se calcule beaucoup plus facilement (n += n >> 1), et a à peu près le même comportement.
http://www.python.org/~jeremy/weblog/040115.html
-- Loïc
kanze@gabi-soft.fr wrote:
Loïc Joly wrote:
Il peut allouer ce qu'il veut, tant que ça suit une croissance
géométrique, le coefficient ne vaut pas forcément sqrt(2)
Il me semble avoir lu cependant que selon certains critères,
sqrt(2) est le facteur idéal. Ce qui est certain, c'est qu'avec
un facteur de 2 (qui était le facteur le plus fréquent au
début), la somme des tailles des blocs libérés ne suffirait
jamais à une nouvelle allocation ; pour tout multiple
strictement inférieur à 2, on y arrivera éventuellement.
Je crois qu'il faut pour cela que le facteur soit inférieur au
"nombre d'or" (1 + sqrt(5))/2 == 1.618... mais je me ne souviens
plus des détails.
À vrai dire, je ne vois pas l'intérêt de sqrt(2) quand 1,5 se
calcule beaucoup plus facilement (n += n >> 1), et a à peu près
le même comportement.
Il peut allouer ce qu'il veut, tant que ça suit une croissance géométrique, le coefficient ne vaut pas forcément sqrt(2)
Il me semble avoir lu cependant que selon certains critères, sqrt(2) est le facteur idéal. Ce qui est certain, c'est qu'avec un facteur de 2 (qui était le facteur le plus fréquent au début), la somme des tailles des blocs libérés ne suffirait jamais à une nouvelle allocation ; pour tout multiple strictement inférieur à 2, on y arrivera éventuellement.
Je crois qu'il faut pour cela que le facteur soit inférieur au "nombre d'or" (1 + sqrt(5))/2 == 1.618... mais je me ne souviens plus des détails.
À vrai dire, je ne vois pas l'intérêt de sqrt(2) quand 1,5 se calcule beaucoup plus facilement (n += n >> 1), et a à peu près le même comportement.
http://www.python.org/~jeremy/weblog/040115.html
-- Loïc
kanze
Franck Branjonneau wrote:
Falk Tannhäuser écrivait:
wrote:
Loïc Joly wrote:
Il peut allouer ce qu'il veut, tant que ça suit une croissance géométrique, le coefficient ne vaut pas forcément sqrt(2) > >> Il me semble avoir lu cependant que selon certains critères, > >> sqrt(2) est le facteur idéal. Ce qui est certain, c'est qu'avec > >> un facteur de 2 (qui était le facteur le plus fréquent au > >> début), la somme des tailles des blocs libérés ne suffirait > >> jamais à une nouvelle allocation ; pour tout multiple > >> strictement inférieur à 2, on y arrivera éventuellement.
Je crois qu'il faut pour cela que le facteur soit inférieur au "nombre d'or" (1 + sqrt(5))/2 == 1.618... mais je me ne souviens plus des détails.
Les détails, pour autant que je sache : la n+1 ème allocation doit demander un bloc d'une taille inférieure (ou égale) à la somme des n-1 blocs libérés ; le n ème est occupé.
Voilà le fait que j'avais oublié -- qu'il y a effectivement deux blocs alloués au même temps. Ce qui effectivement ramène le facteur critique à phi à la place de 2.
-- 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
Il peut allouer ce qu'il veut, tant que ça suit une
croissance géométrique, le coefficient ne vaut pas
forcément sqrt(2) > >> Il me semble avoir lu cependant que
selon certains critères, > >> sqrt(2) est le facteur
idéal. Ce qui est certain, c'est qu'avec > >> un facteur de
2 (qui était le facteur le plus fréquent au > >> début), la
somme des tailles des blocs libérés ne suffirait > >>
jamais à une nouvelle allocation ; pour tout multiple > >>
strictement inférieur à 2, on y arrivera éventuellement.
Je crois qu'il faut pour cela que le facteur soit inférieur
au "nombre d'or" (1 + sqrt(5))/2 == 1.618... mais je me ne
souviens plus des détails.
Les détails, pour autant que je sache : la n+1 ème allocation
doit demander un bloc d'une taille inférieure (ou égale) à la
somme des n-1 blocs libérés ; le n ème est occupé.
Voilà le fait que j'avais oublié -- qu'il y a effectivement deux
blocs alloués au même temps. Ce qui effectivement ramène le
facteur critique à phi à la place de 2.
--
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
Il peut allouer ce qu'il veut, tant que ça suit une croissance géométrique, le coefficient ne vaut pas forcément sqrt(2) > >> Il me semble avoir lu cependant que selon certains critères, > >> sqrt(2) est le facteur idéal. Ce qui est certain, c'est qu'avec > >> un facteur de 2 (qui était le facteur le plus fréquent au > >> début), la somme des tailles des blocs libérés ne suffirait > >> jamais à une nouvelle allocation ; pour tout multiple > >> strictement inférieur à 2, on y arrivera éventuellement.
Je crois qu'il faut pour cela que le facteur soit inférieur au "nombre d'or" (1 + sqrt(5))/2 == 1.618... mais je me ne souviens plus des détails.
Les détails, pour autant que je sache : la n+1 ème allocation doit demander un bloc d'une taille inférieure (ou égale) à la somme des n-1 blocs libérés ; le n ème est occupé.
Voilà le fait que j'avais oublié -- qu'il y a effectivement deux blocs alloués au même temps. Ce qui effectivement ramène le facteur critique à phi à la place de 2.
-- 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
Fabien LE LEZ
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)) ?
-- ;-)
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)) ?
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)) ?
-- ;-)
kanze
Fabien LE LEZ wrote:
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.)
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. 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 ?
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.)
-- 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
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.)
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.
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 ?
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.)
--
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.)
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. 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 ?
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.)
-- 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
Jean-Marc Bourguet
writes:
Fabien LE LEZ wrote:
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)) ?
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. 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 ?
facile: taille[n+2] = somme(taille[i], i = 0 .. n) = somme(taille[i], i = 0 .. n-1) + taille[n] = taille[n+1] + taille[n] C'est la serie fibonacci.
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
kanze@gabi-soft.fr writes:
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)) ?
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.
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 ?
facile: taille[n+2] = somme(taille[i], i = 0 .. n)
= somme(taille[i], i = 0 .. n-1) + taille[n]
= taille[n+1] + taille[n]
C'est la serie fibonacci.
A+
--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
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)) ?
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. 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 ?
facile: taille[n+2] = somme(taille[i], i = 0 .. n) = somme(taille[i], i = 0 .. n-1) + taille[n] = taille[n+1] + taille[n] C'est la serie fibonacci.
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
Franck Branjonneau
Fabien LE LEZ écrivait:
On Wed, 30 Mar 2005 17:39:55 +0200, Franck Branjonneau :
La raison de la suite des tailles successives du *est* phi.
Non.
Allez, je te donne à moitié raison ;-).
Toute suite vérifiant que le n+2 ème terme est la somme des n premiers est de Fibonnaci et vérifie :
Le rapport entre deux tailles successives tend vers phi (quand le nombre d'allocations tend vers l'infini).
Et donc ; si, de plus, elle est géométrique sa raison est phi.
Une telle suite existe-t-elle ? La suite phi^n où n est un entier convient.
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)) ?
Je viens de répondre ;-) -- Franck Branjonneau
Fabien LE LEZ <gramster@gramster.com> écrivait:
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.
Allez, je te donne à moitié raison ;-).
Toute suite vérifiant que le n+2 ème terme est la somme des n premiers
est de Fibonnaci et vérifie :
Le rapport entre deux tailles successives tend vers phi (quand le
nombre d'allocations tend vers l'infini).
Et donc ; si, de plus, elle est géométrique sa raison est phi.
Une telle suite existe-t-elle ? La suite phi^n où n est un entier
convient.
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)) ?
Je viens de répondre ;-)
--
Franck Branjonneau <fasbjx@free.fr>
On Wed, 30 Mar 2005 17:39:55 +0200, Franck Branjonneau :
La raison de la suite des tailles successives du *est* phi.
Non.
Allez, je te donne à moitié raison ;-).
Toute suite vérifiant que le n+2 ème terme est la somme des n premiers est de Fibonnaci et vérifie :
Le rapport entre deux tailles successives tend vers phi (quand le nombre d'allocations tend vers l'infini).
Et donc ; si, de plus, elle est géométrique sa raison est phi.
Une telle suite existe-t-elle ? La suite phi^n où n est un entier convient.
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)) ?
Je viens de répondre ;-) -- Franck Branjonneau
Franck Branjonneau
écrivait:
Fabien LE LEZ wrote:
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 ; 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.
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 ?
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.
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 ?) -- Franck Branjonneau
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 ; 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.
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 ?
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.
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 ?)
--
Franck Branjonneau <fasbjx@free.fr>
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 ; 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.
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 ?
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.
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 ?) -- Franck Branjonneau
Franck Branjonneau
Jean-Marc Bourguet écrivait:
writes:
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. 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 ?
facile: taille[n+2] = somme(taille[i], i = 0 .. n) = somme(taille[i], i = 0 .. n-1) + taille[n] = taille[n+1] + taille[n] C'est la serie fibonacci.
Une suite de Fibonacci, *la* suite de Fibonacci vérifie de plus taille[1] = taille[2] = 1.
Et ce n'est pas suffisant pour répondre à la question : Si taille est une suite telle que taille[i] >= k^i, où k est fixé, à partir d'un certain rang. Alors, pour i suffisamment grand, taille[i+2] >= k^(i+1) + k^i et taille[i+2] >= k^(i+2) donc, k^(i+2) >= k^(i+1) + k^i. L'égalité est vérifiée pour phi, il faut que k >= phi. -- Franck Branjonneau
Jean-Marc Bourguet <jm@bourguet.org> écrivait:
kanze@gabi-soft.fr writes:
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.
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 ?
facile: taille[n+2] = somme(taille[i], i = 0 .. n)
= somme(taille[i], i = 0 .. n-1) + taille[n]
= taille[n+1] + taille[n]
C'est la serie fibonacci.
Une suite de Fibonacci, *la* suite de Fibonacci vérifie de plus
taille[1] = taille[2] = 1.
Et ce n'est pas suffisant pour répondre à la question : Si taille est
une suite telle que taille[i] >= k^i, où k est fixé, à partir d'un
certain rang. Alors, pour i suffisamment grand,
taille[i+2] >= k^(i+1) + k^i et
taille[i+2] >= k^(i+2)
donc,
k^(i+2) >= k^(i+1) + k^i.
L'égalité est vérifiée pour phi, il faut que k >= phi.
--
Franck Branjonneau <fasbjx@free.fr>
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. 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 ?
facile: taille[n+2] = somme(taille[i], i = 0 .. n) = somme(taille[i], i = 0 .. n-1) + taille[n] = taille[n+1] + taille[n] C'est la serie fibonacci.
Une suite de Fibonacci, *la* suite de Fibonacci vérifie de plus taille[1] = taille[2] = 1.
Et ce n'est pas suffisant pour répondre à la question : Si taille est une suite telle que taille[i] >= k^i, où k est fixé, à partir d'un certain rang. Alors, pour i suffisamment grand, taille[i+2] >= k^(i+1) + k^i et taille[i+2] >= k^(i+2) donc, k^(i+2) >= k^(i+1) + k^i. L'égalité est vérifiée pour phi, il faut que k >= phi. -- Franck Branjonneau
Alexis Nikichine
wrote:
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.)
J'avais trouvé tout tout bien formulé sur cette page:
http://www.sgi.com/tech/stl/complexity.html
Juste pour dire,
Alexis
-- Some domain is free
kanze@gabi-soft.fr wrote:
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.)
J'avais trouvé tout tout bien formulé sur cette page:
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.)
J'avais trouvé tout tout bien formulé sur cette page:
http://www.sgi.com/tech/stl/complexity.html
Juste pour dire,
Alexis
-- Some domain is free
Falk Tannhäuser
Franck Branjonneau wrote:
Une suite de Fibonacci, *la* suite de Fibonacci vérifie de plus taille[1] = taille[2] = 1.
et généralement taille[n] = (phi^n - (-phi)^-n) / sqrt(5)
Falk
Franck Branjonneau wrote:
Une suite de Fibonacci, *la* suite de Fibonacci vérifie de plus
taille[1] = taille[2] = 1.
et généralement
taille[n] = (phi^n - (-phi)^-n) / sqrt(5)
