UNIX Socket FAQ

A forum for questions and answers about network programming on Linux and all other Unix-like systems

You are not logged in.

  • Index
  • » C
  • » efficient equality comparison for 2d arrays

#1 2004-11-05 09:08 PM

socks
Member
Registered: 2004-09-27
Posts: 12

Re: efficient equality comparison for 2d arrays

What is the optimal way to test for equality between two 2D arrays?  I wrote some code that works but I don't know if it is optimal.  Could someone please post code that will run more efficiently than mine?  My comparision method is posted below:

Note: packet is a struct that contains a 2d array.  The 2D array called payload holds next hop info for a node and distance vector info.

int compare(packet  *array1, packet *array2, int row, int col)
{
  int result=1;
   int i, c;
   for(i=0; i<row; i++)
   {
     for(c=0; c<col; c++)
     {   
         if(array1->payload[i][c]!=array2->payload[i][c])
          {
           result=0;
           return result;
          }
     }
   }
return result;
}

Offline

#2 2004-11-05 10:35 PM

RobSeace
Administrator
From: Boston, MA
Registered: 2002-06-12
Posts: 3,847
Website

Re: efficient equality comparison for 2d arrays

If it's just strict exact equality in the entire array that you care
about, how about a simple memcmp()?  Ie:

int compare(packet  *array1, packet *array2, int row, int col)
{
    return (memcmp (array1->payload, array2->payload,
                                  sizeof (array1->payload[0][0]) * row * col));
}

Of course, if these are fixed-size non-dynamic arrays, you could
get away with dropping row and col args, and simply use
"sizeof (array1->payload)", too...

Offline

#3 2004-11-05 11:04 PM

socks
Member
Registered: 2004-09-27
Posts: 12

Re: efficient equality comparison for 2d arrays

Thanks. I just found out that memcmp and memcpy are very efficient methods because they were written in assembly is that true?  Other than using memcmp is there another way to optimize checking for equality between two 2D arrays (i.e. would mapipulating pointers so that the 2D array could be treated as a 1D array increase efficiency)?

Offline

#4 2004-11-06 07:32 PM

RobSeace
Administrator
From: Boston, MA
Registered: 2002-06-12
Posts: 3,847
Website

Re: efficient equality comparison for 2d arrays

Yes, generally, most decent libc's will have a very efficient
memcmp() and memcpy(), most likely written in highly optimized
assembly...  It's a pretty safe bet to assume you can't improve on
their efficiency, at least...

But, as for other methods not involving the use of optimized libc
functions...  Well, you might gain some slight efficiency by going
with your own pointer arithmetic instead of using indexing...  Ie.,
assuming "payload" is defined as a 2D array of ints:

int compare(packet  *array1, packet *array2, int row, int col)
{
    int *p1, *p2, *pend;
    p1 = (int*) (array1->payload);
    p2 = (int*) (array2->payload);
    pend = p1 + (row * col);
    for (; p1 < pend; p1++, p2++) {
        if (*p1 != *p2) return (*p1 - *p2);
    }
    return (0);
}

I wouldn't expect a very noticable increase in efficiency, though...
Though, if the arrays are fairly large and/or this comparison
function is called quite often, it might add up to a noticable amount...

Offline

#5 2010-10-22 03:21 AM

Andrew Phillips
Guest

Re: efficient equality comparison for 2d arrays

#6 2010-10-22 11:40 AM

i3839
Oddministrator
From: Amsterdam
Registered: 2003-06-07
Posts: 2,239

Re: efficient equality comparison for 2d arrays

Offline

  • Index
  • » C
  • » efficient equality comparison for 2d arrays

Board footer

Powered by FluxBB