Re: quickly comparing blocks of ints


Snis Pilbor wrote:
Hello,

In a time-intensive part of my code, I manually check if two
blocks of ints (of the same size) are identical. I do it in the
straightforward way...

bool compare_int_tables( int *intpointer1, int *intpointer2 )
{
int i;

for ( i = 0; i < size; i++ )
{
if ( intpointer1[i] != intpointer2[i] )
return FALSE;
}
return TRUE;
}


My question is, is there any faster way to do this? I am not very
familiar with what various chips various processors have, but is
checking blocks of generic data like this common enough that it's worth
using a special function from some .h file to do the above in hopes
that the compiler will relegate the work to some super-fast chip, or
something?

Thanks for help with this,
S.P.

As you are just comparing for in/equality it might be worth computing a
hash value for each integer block to reduce the number of full
comparisons. Where the hash values are different there is no need to
compare the blocks - they must be different. Effectively this replaces
a full block comparison with a single integer comparison. A full
comparison is only needed where the hash values are the same because of
the possibility of collisions. You save many comparisons at the cost
of one hash computation per block.

You don't say where the integer blocks originate. If you have control
over their production then if the hash can be built as each number
block is being built then that might not add too much overhead to the
program. Even if the blocks come in from outside, each hash only has
to be calculated once while a block may have to be compared many times.
Assuming that you do more than one comparison per block this should
give a time saving. The higher the proportion of mismatches the better
the saving should be as a match will always need a full comparison.

rossum

.

Relevant Pages

  • Re: booleans, hash() and objects having the same value
    ... passed as argument to the hash() function... ... the rare cases that you want bools to hash differently from ints, ... would be that objects with compatible (i.e. one inherits from the other) ...
    (comp.lang.python)
  • Re: hashCode() for Custom classes
    ... How many different Strings exist? ... enough unique ints to go 'round. ... The purpose of a hash code is to map a large set of wide inputs to a smaller set of narrower inputs. ... Hash indexing is only step one - if more than one key is in the same hash bucket, you walk the list comparing each bucket denizen against the candidate for step two. ...
    (comp.lang.java.programmer)
  • Re: hashCode for 4 ints?
    ... Since .hashCode() returns an int, how do I create a unique identifier for ... the 128 bits contained in the 4 ints? ... is allowed to return the same hash also for unequal objects. ... and might not be worth the trouble at all ...
    (comp.lang.java.programmer)
  • Re: quickly comparing blocks of ints
    ... rossum wrote: ... blocks of ints are identical. ... Where the hash values are different there is no need to ... You don't say where the integer blocks originate. ...
    (comp.programming)