Solved

initialize dynamic integer array

Posted on 1998-12-01
12
209 Views
Last Modified: 2011-09-20
I have an array declared as
int **int_grid;
it is properly allocated.
I need to set int_grid[x][y1] through int_grid[x][y2] (y2>y1) to some value z.
Is there a quicker way than looping through and setting each to z?
Thanks, mm
0
Comment
Question by:marvinm
  • 4
  • 2
  • 2
  • +4
12 Comments
 
LVL 1

Author Comment

by:marvinm
ID: 1254751
Edited text of question
0
 
LVL 2

Expert Comment

by:harrys
ID: 1254752
well, using pointer arithmetics is faster than calculating offsets into the array for every value to set.
Calcutate the offset for the first value and increment the pointer until all z were set.

0
 
LVL 1

Author Comment

by:marvinm
ID: 1254753
Wouldn't (or shouldn't) the compiler generate the same code for accessing int_grid[x][y2]and **(int_grid+some_offset)?
0
Master Your Team's Linux and Cloud Stack!

The average business loses $13.5M per year to ineffective training (per 1,000 employees). Keep ahead of the competition and combine in-person quality with online cost and flexibility by training with Linux Academy.

 
LVL 16

Expert Comment

by:imladris
ID: 1254754
You can use memset:

void *memset(void *dest,int c,size_t count);

This function will set count bytes to the value in c. So you would say:

memset(int_grid[x]+y1,z,y2-y1);

0
 
LVL 1

Author Comment

by:marvinm
ID: 1254755
memset() sets all the bytes to a specified value. I need each integer (in my case 4 bytes) to equal a value.
0
 
LVL 27

Expert Comment

by:BigRat
ID: 1254756
Frankly squeeking, I mean frankly speaking I don't see the necessity of a quick algorithm. The compiler should generate reasonable code for for(int i=y1; i<=y2; i++) int_grid[x][i]=z;
such that only 3 instructions are needed per loop. That is to say any decent compiler.
   One trick which we did in the old days was to initialise the first element of the array and then do a memcpy which copied the first element into the second. By setting the number of elements of the memcpy to n-1 we initialised all the elements to the same value irrespective of how big an element was.
   But is it really necessary these days?
0
 
LVL 12

Accepted Solution

by:
rwilson032697 earned 100 total points
ID: 1254757
Use memcopy to copy blocks of filled in cells:

eg: you have 100 to fill in. Loop through the first 10 setting the value. Then just memcopy (memcpy?) the first block of 10 to the remaining 9 blocks. By playing with how you break it down you can optimise it (eg: set first 10, copy that to next 10, then copy first 20 to next 20 etc, then when the assigned entries are too big to be copied to the remainder just copy the amount you need).

This is as fast as it is going to get.

Cheers,

Raymond.
0
 
LVL 11

Expert Comment

by:alexo
ID: 1254758
memcpy() will probably slow you down due to the overhead of the function call, etc.

Using MSVC4.2 with speed optimizations turned on, this code:

    for (i = 21; i <= 81; ++i)
        array[41][i] = -1;

Produces the following assembly:

        mov     eax, 84
        mov     edx, DWORD PTR _array$[esp+4]
$L159:
        mov     ecx, DWORD PTR [edx+164]
        add     eax, 4
        cmp     eax, 324
        mov     DWORD PTR [ecx+eax-4], -1
        jle     SHORT $L159

A trivial optimization:

        int* p = array[41];
        for (i = 21; i <= 81; ++i)
                p[i] = -1;

Produces the following:

        mov     ecx, 61
        mov     eax, DWORD PTR _array$[esp+4]
        mov     edi, DWORD PTR [eax+164]
        mov     eax, -1
        add     edi, 84
        rep     stosd

Much better.

However, other compilers may perform better optimization.  My suggestion: check with a profiler to see if you REALLY have a bottleneck before manually optimizing code.
0
 
LVL 84

Expert Comment

by:ozo
ID: 1254759
If initialization is a significant part of your total processing time, is it because very few of the elements are actually being used?
If so, it may help to only initialize the elements when they are used
0
 
LVL 12

Expert Comment

by:rwilson032697
ID: 1254760
alexo - you are right, there will be an overhead with the function call. This will mean for small arrays your method will be quicker. Though for large arrays at most only log2n +1 calls will be required (the can be reduced by log2n of the initial number of cells filled in). In these cases it will be significantly faster than looping - even with the hand optimisation you show.

ozo: I agree. Initialisation on demand is a more effective approach with large structures.

Cheers,

Raymond.
0
 
LVL 1

Author Comment

by:marvinm
ID: 1254761
My array is not exceptionally large, I was just looking to keep my code somewhat optimized. Initialization is not really my issue. Sections of the array need to be set to different values at different times. Thanks to all for the help.
0
 
LVL 11

Expert Comment

by:alexo
ID: 1254762
Raymond, I seriously doubt that *anything* you can write using memcpy() will be faster than a "rep stosd" (other instructions are just for setting up the loop) for *any* loop size.
No, with just a little help from the programmer the compiler will generate code that is hard to beat without resorting to hand coded assembly.
0

Featured Post

NAS Cloud Backup Strategies

This article explains backup scenarios when using network storage. We review the so-called “3-2-1 strategy” and summarize the methods you can use to send NAS data to the cloud

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

770 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question