Re: slow startup on windows

On Sun, 27 Oct 2024 12:58:44 -0400
"John Selverian" <[email protected]> wrote:

>I never knew how slow an append() was. As I've said before, it
>runs almost instantly on Linux/OSX.
>
>Generally, I don't like to hard code sizes but I can sort of do
>both. I'll hard code a size then keep track of it and if I'm
>lower I'll just assign it, if I'm larger I'll append(). I usually
>don't add more than 20 at a time. I don't want to have to change
>this size every time I add one dataset. I'm not very good at
>counting, I'll let the computer do that. Then I'll periodically
>update the hard coded size.

A common approach is to start with a given size, then each time the
size is exceeded, then just double the size of the array.

Amortized analysis of this technique will still be O(N), although
keep in mind that every time a power of 2 is crossed, a major
amount of work still takes place.  But this is at least scalable
for one at a time addition w/o going quadratic.

We do this, btw, in FXHash and other dictionary types.

But nothing can ultimately beat allocation the space in advance, if
you know it, or if you can somehow (over-) estimate it. 

This has nothing to do with hardwiring.  If you're reading a file,
maybe gettings the file's size is a clue, e.g. if each line is mostly
the same size.  It doesn't have to be exact, it could just be an estimate.

The successive doubling technique works very well if you can't even come
up with an estimate, at least you can keep the *average* append time from
being quadratic in N.

Think of the doubling algorithm as a piggybank.  Initially, the piggy
bank is empty.  Each time you append, the cost is 2. One for the append,
one for the piggy bank.  After appending 2**p items, your piggy bank
has enough to pay for 2**p reallocations, therefore the average cost
is 2 for each item; adding N items thus has a cost of 2N, which is
O(N) in our big-O notation where constants are swept under the rug.

Ergo append can be linear with this approach....


	Cheers,

                   	   -- JVZ



-- 
+----------------------------------------------------------------------------+
| Copyright (C) 12:00 03/31/2018 Jeroen van der Zijp.   All Rights Reserved. |
+----------------------------------------------------------------------------+