Re^2: Data structure challenge (amortized)

If amortizing the initialization cost over the lifetime of the structure were allowed, then simple Perl arrays could be used (by not preallocating the size of the array so that the initial creation is still O(1)). Your use of strings 'suffer' from this same 'problem'. So I'm pretty sure Abigail would reject this solution.

Your solution would qualify if you could preallocate the length of the string w/o Perl initializing the contents of the string. This is pretty trivial to do in XS, hence the disqualification of that method.

- tye

Comment on Re^2: Data structure challenge (amortized)

Replies are listed 'Best First'.
Re: Re^2: Data structure challenge (amortized) by dpuu (Chaplain) on Mar 17, 2004 at 21:27 UTC
I'm not allowed to amortize the initialization over the life of the structure: but what about over the life of the program: is it valid (in the context of this challenge) big array (vec, whatever) at time zero and then manage it using my own allocator?	[reply]
Re^4: Data structure challenge (amortized) by sleepingsquirrel (Chaplain) on Mar 18, 2004 at 00:01 UTC
As long as we're only talking big-O notation, I think that that O(n) initialization is a wash. Inserting n items at O(1) is O(n). And O(n) (for initialization) + O(n) (for n insertions) = O(n).	[reply]
Re: Data structure challenge (amortized) by Abigail-II (Bishop) on Mar 18, 2004 at 00:15 UTC
I'm not sure what you mean. Note that if you use an array, the array size is `U`. And, yes, `n` insertions, each taking constant time is `O (n)`. However, initializing all elements of an array of size `U` takes `Θ (U)`. But it's not given that `U = O (n)`. There might only be `O (sqrt (U))` insertions. Abigail	[reply]