www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Deamortizing AA's and Dynamic Arrays

reply Manfred Nowak <svv1999 hotmail.com> writes:
Is "Deamortizing AA's and Dynamic Arrays" of any interest?

-manfred
Apr 23 2007
next sibling parent reply Dan <murpsoft hotmail.com> writes:
Manfred Nowak Wrote:


 Is "Deamortizing AA's and Dynamic Arrays" of any interest?
 
 -manfred



By "Deamortizing" you mean "reduce the cost of" right?
I'm not an accountant.

- Dan
Apr 23 2007
parent reply 0ffh <spam frankhirsch.net> writes:
Dan wrote:

 Manfred Nowak Wrote:

 Is "Deamortizing AA's and Dynamic Arrays" of any interest?



 I'm not an accountant.



I think he means trading occasional "longer" waits for regular
short waits....

Regards, Frank
Apr 23 2007
parent reply Derek Parnell <derek nomail.afraid.org> writes:
On Mon, 23 Apr 2007 22:14:46 +0200, 0ffh wrote:


 Dan wrote:

 Manfred Nowak Wrote:

 Is "Deamortizing AA's and Dynamic Arrays" of any interest?



 I'm not an accountant.



 I think he means trading occasional "longer" waits for regular
 short waits....



In that case, Manfred probably used the term "Amortizing" rather than
"De-Amortizing". To me, the 'de-' prefix implies an operation that reverses
the effect of amortizing the behaviour. In other words, 'de-amortizing'
means bunching up the costs into larger lumps and 'amortizing' means
spreading the costs into smaller lumps. In both case, the lumps would be
predictable rather than probabilistically determined.

Manfred has quoted a Wikipedia reference and it seems to uphold my
understanding of the term, but I suppose I could just be reading it
incorrectly.

-- 
Derek
(skype: derek.j.parnell)
Melbourne, Australia
"Justice for David Hicks!"
24/04/2007 12:38:13 PM
Apr 23 2007
parent 0ffh <spam frankhirsch.net> writes:
Derek Parnell wrote:

 On Mon, 23 Apr 2007 22:14:46 +0200, 0ffh wrote:
 In that case, Manfred probably used the term "Amortizing" rather than
 "De-Amortizing". To me, the 'de-' prefix implies an operation that reverses
 the effect of amortizing the behaviour. In other words, 'de-amortizing'
 means bunching up the costs into larger lumps and 'amortizing' means
 spreading the costs into smaller lumps. In both case, the lumps would be
 predictable rather than probabilistically determined.



I'm not 100% sure here how the language should be used.
My interpretation runs thus:

"Amortising" is just a mathematical "trick" to make different sorts of
algorithms comparable in terms of computational cost per function call,
by spreading lumped costs equally over all calls.
Therefore, I interpret "deamortising" a piece of /concrete code/ as
removing the need for this "spreading trick" by replacing a "lumpy"
method with a more "incremental" one.

Regards, Frank
Apr 23 2007
prev sibling parent reply Derek Parnell <derek nomail.afraid.org> writes:
On Mon, 23 Apr 2007 19:32:12 +0000 (UTC), Manfred Nowak wrote:


 Is "Deamortizing AA's and Dynamic Arrays" of any interest?



I can't really say because I'm not sure what you mean by "deamortizing".

If "amortizing" means spreading the cost over a longer period of time (many
small payments over the time), then the reverse would mean that you intend
to 'spend' the cost in bigger hits (a few large payments over the time)

So I expect you mean something like implementing AA and DynArr by doing a
lots of 'pre-processing' work at create or expand time rather than little
bits of work for each new element.

If, then yes I'd be interested.

-- 
Derek
(skype: derek.j.parnell)
Melbourne, Australia
"Justice for David Hicks!"
24/04/2007 10:32:11 AM
Apr 23 2007
parent Manfred Nowak <svv1999 hotmail.com> writes:
Derek Parnell wrote


 I can't really say because I'm not sure what you mean by
 "deamortizing". 




Amortizing is explained here: 
http://en.wikipedia.org/wiki/Amortized_analysis

So: 0ffh had the right interpretation of the word "deamortizing". This 
technical term came to my knowledge quite recently.

-manfred
Apr 23 2007