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!
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.
if at all possible - make it large enough to start with
you haven't given us enough details to really help you much
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
Quote from: Slugsnack on December 19, 2009, 05:09:09 AM
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 (http://en.wikipedia.org/wiki/Abstract_data_type#Example:_abstract_stack_.28functional.29); but that would slow down the access to the array. If you have a direct access design, e.g.
MyArrayTable dd P0, P1, P2, ... where Pn are the pointers to the strings or
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.
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
can use GlobalAlloc and GlobalRealloc to resize memory you create with that.
http://msdn.microsoft.com/en-us/library/aa366590%28VS.85%29.aspx
Quote from: cman on December 19, 2009, 08:06:11 PM
... 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...
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.
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
Wow, thanks for the code MichaelW! :U And thanks everyone else for the tips and information! :U