Solved

initialize dynamic integer array

Posted on 1998-12-01
12
207 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
Comment Utility
Edited text of question
0
 
LVL 2

Expert Comment

by:harrys
Comment Utility
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
Comment Utility
Wouldn't (or shouldn't) the compiler generate the same code for accessing int_grid[x][y2]and **(int_grid+some_offset)?
0
 
LVL 16

Expert Comment

by:imladris
Comment Utility
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
Comment Utility
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
Comment Utility
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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 12

Accepted Solution

by:
rwilson032697 earned 100 total points
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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

What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
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…
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

771 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

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now