Array Resizing Algorithm

[cman]

Does anyone know a good algorithm for resizing a dynamic array? What I'm interested in is what size to choose for the new array before the old one is copied to it and then deleted. Thanks for any info!

[hutch--]

If you just want it larger without changing the order, reallocate the memory with the extra space you require. Its when you start dpoing insertions that it gets a bit complicated.

[dedndave]

if at all possible - make it large enough to start with
you haven't given us enough details to really help you much

[Slugsnack]

if you're intending to do a lot of insertion + resizing of the array then i'd suggest using an ADT like linked list instead

[jj2007]

if you're intending to do a lot of insertion + resizing of the array then i'd suggest using an ADT like linked list instead

Wiki example here; but that would slow down the access to the array. If you have a direct access design, e.g.

Code Select Expand

MyArrayTable  dd P0, P1, P2, ... where Pn are the pointers to the strings or

Code Select Expand

MyArrayTable  dd P0, L0, P1, L1, P2, L2, ... where Pn are the pointers to the strings and Ln the lengths

then you just shift all elements above Pinsert to the right, or all elements above Pdelete to the left. The bottleneck here is the availability of free space on the right - have a look at HeapReAlloc...

One strategy is to reduce the calls to HeapReAlloc by allocating a given number of elements beyond the currently needed ones, so that the next time you are using up the extra ones.

[cman]

OK, thanks for the information. I need a strategy to re-size the array before copying the old data to the array. I remember when I was taking a course on data structures one of my professors had a formula to re-size the array based on its current size , increasing the size in large proportion when the array was smaller and then gradually decreasing the percentage the size would increase as the array becomes very large ( obviously you wouldn't want to just double the size of the original array for every resizing when the array got very large ). Just wondered if anyone had seen such an algorithm ( I'll check my texts on algorithms latter! ). Thanks again. :U

[ecube]

can use GlobalAlloc and GlobalRealloc to resize memory you create with that.

http://msdn.microsoft.com/en-us/library/aa366590%28VS.85%29.aspx

[jj2007]

... re-size the array before copying the old data to the array

Again, it would help if you were more specific and detailed about your problem.

If you are talking string arrays, you would normally not copy the data but rather rearrange the pointers only, as shown above.

The magic formula for the table of pointers depends a lot on the application. You may need a testbed for simulating a typical "session" with typical inserts and deletes. HeapReAlloc works fine but is slower than just shifting the pointers right or left, so allocating more than you need is indeed a good strategy. Use a formula of the type ExtraDwords=FixedAmount+factor*NumElements, with e.g. FixedAmount=1024 and factor=0.02, and start timing your testbed...

[MichaelW]

The attachment is an attempt to measure the cost of reallocations, assuming a growable heap, an increase in the allocated size of 1MB per call, and with the additional memory beyond the original size initialized to zero. Testing under Windows 2000 on my P3 system with only 512MB of physical memory and a bunch of things running, the time for each reallocation varied by something like the 1.1 power of the total allocation size. Not initializing the additional memory to zero reduced the time by a uniform 5ms, which amounted to a 25% reduction in time for a 3MB total allocation, but less than 2% for a 32MB total allocation.

EDIT:

Modified the code to show the address of the reallocated block, and thus provide an indication of why the reallocation is taking so long.

Code Select Expand


total(KB)  address    time(ms)
------------------------------
3072      00830020h     20
4096      00B40020h     28
5120      00F50020h     36
6144      01460020h     43
7168      01A70020h     50
8192      02180020h     58
9216      02990020h     67
10240     032A0020h     73
11264     03CB0020h     82
12288     047C0020h     90
13312     053D0020h     98
14336     060E0020h     105
15360     06EF0020h     112
16384     07E00020h     119
17408     08E10020h     126
18432     09F20020h     135
19456     0B130020h     141
20480     0C440020h     149
21504     0D850020h     169
22528     0ED60020h     200
23552     10370020h     208
24576     11A80020h     220
25600     13290020h     227
26624     14BA0020h     237
27648     165B0020h     249
28672     180C0020h     259
29696     19CD0020h     268
30720     1B9E0020h     277
31744     1D7F0020h     285
32768     1F700020h     294


[cman]

Wow, thanks for the code MichaelW! :U And thanks everyone else for the tips and information!  :U