Solved

initialize dynamic integer array

Posted on 1998-12-01
12
211 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

734 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