Re: [RFC] Vector (string?) growth factor of 1.5 (insted of 2)

[Dhruv Matani <dhruvbird at gmx dot net>]

On Tue, 2004-02-03 at 23:27, Matt Austern wrote:
> On Feb 3, 2004, at 5:11 AM, Dhruv Matani wrote:
> 
> > On Tue, 2004-02-03 at 05:41, Paolo Carlini wrote:
> >> Gabriel Dos Reis wrote:
> >>
> >>> if the only thing you have is a genuine input iterator you're
> >>> effectively stuck. However, if you have at least a bidirectional
> >>> iterator, then you can have an idea of the amount staorage you need.
> >>> We already have dispatchers that compute those iterator categories.
> >>> It might be a good idea to take advantage of them.
> >>
> >> Ok. I think that, by and large, we already do our best, both in
> >> string and in vector...
> >>
> >> A detail comes to my mind, though: perhaps, at construction time,
> >> speed matters more and, in the case of the constructor from input
> >> iterators, we should allow for a bigger factor. Later, memory usage
> >> matters more and a smaller factor seem in order (-> as you say, if
> >> the max speed is really needed reserve is always available, then).
> >
> > Yes. This seems to me to be a really nice suggestion! Make the growth
> > factor inversely proportional to the size of the vector.
> 
> I don't think that is a good suggestion.  In fact, I don't think it is 
> standard
> conforming.

Hmmm. Thanks ;-) You saved quite a few people quite a lot of work!


> It's easy to prove that if you have a constant growth factor, i.e. if 
> you're
> using exponential growth, then adding one element is amortized
> constant time, as required by the standard.  That is, the number of
> copies you perform when you add N elements at a time is O(N).
> 
> If you're using a growth factor inversely proportional to the size of 
> the
> vector, then you've no longer got exponential growth.  The number of
> copies for adding N elements will be superlinear, meaning that adding
> a single element is no longer amortized constant time, which violates
> the standard.
> 
> Exercises for the reader:
> 1. If you've got a growth factor g, then the number of copies you have
> to make when adding N elements, one at a time, approaches k N.
> Find k as a function of g.
> 
> 2. If your growth factor is inversely proportional to the current size 
> of
> the vector, then how many copies do you have to make if you're
> adding N elements one at a time?
> 
> (I know the answer to exercise 1.  I don't know the answer to exercise
> 2.  My guess would be something like N log N, because this problem
> feels more or less like the integral of 1/x.)

I guess the answer to 1. is 1? And for the 2nd one, your original
question was to express k as a function of the growth function (not
factor in this case, since the growth factor is itself a dynamic
quantity which changes with the size of the vector, since it is
inversely proportional to the size. So, for some constant 'c' belonging
to the domain of Natural numbers, G(N) = c/this->size(). And now the
problem is to find k in terms of G). Which is a different beast in
itself! However, by and large I would tend to agree with you about the
copies function having a tight upper bound of O(Nlg(N)). I can't comment
on the problem being related to the integral of 1/x, since the teachers
at my school have made a mess of calculus and I haven't bothered doing
it myself either! But on the other hand, if someone has lots of time on
his/her hands, he/she could graph out the growth of the vector in such a
case on paper, then calculate the derivative at some specific points and
apply (the great!) Newton's interpollation formula and get a good
approximation of the value over a apecific range that we are looking
for. I have a hunch that the graph will have a very steep curve at the
beginning and will smooth out and become almost straight towards the
end. Something like a very high power function when it begins, and
becomes conatant when it is about to die.



-- 
	-Dhruv Matani.
http://www.geocities.com/dhruvbird/