Searching An Array

[EvilGuru]

I need to search an array of integers for a value and then return its offset. I currently use this:

int arraySearch(int numbers[], int size, int value)
{
	int i;
	for (i = 0; i < size; i++)
	{
		if (numbers[i] == value) break;
	}
	return i;
}

Does anyone know of a faster (if-statement free) way of doing this, as currently with 55,000 item arrays it can take a while.

[Salem]

There is no if free way, unless you count ?: as being different from if.
To make it a lot quicker, start with a sorted array.

[EvilGuru]

It is for the decryption part of my encryptor. I jumble up an array and then use it to rearrange the file (as well as XORing). The decryptor jumbles up the same array and then works out offsets by finding locations of numbers. However, when I did the jumble function I also made an unjumble function and I am just thinking if I can use it to work out offsets. Here are the two functions:

void jumble(int numbers[], int size, int seed)
{
	int i;
	srand(seed); /* seed the random number generator */
	for (i = 1; i < size; i++)
	{
		int index = rand() % (i + 1);
		int swap = numbers[i];
		numbers[i] = numbers[index];
		numbers[index] = swap;
	}
}
void unjumble(int numbers[],int size, int seed)
{
	int i;
	srand(seed); /* seed the random number generator */
	int *indexes = malloc(size * sizeof(int));
	for (i = 1; i < size; i++){ indexes[i] = rand() % (i + 1); }
	for (i = size - 1; i > 0; i--)
	{
		int index = indexes[i];
		int swap = numbers[i];
		numbers[i] = numbers[index];
		numbers[index] = swap;
	}
	free(indexes);
}

[dwks]

	for (i = 1; i < size; i++)
	{
		int index = rand() % (i + 1);
		int swap = numbers[i];
		numbers[i] = numbers[index];
		numbers[index] = swap;
	}

Isn't that a little inefficient, declaring the variables each time? Or does the compiler optimize it?

[Salem]

> Or does the compiler optimize it?
Makes no difference in C.

In C++, there would be constructor/destructor calls each time around the loop, but I don't think they do much for base types like int.

[dwks]

Okay, then. What I would do is have a binary-searchable array of pointers (or structs). The linear search is always slow, no matter what you do.

[quzah]

Loop unrolling! Make four checks per iteration. Sure, that sounds fun!

for( hptr = array, tptr = array + size, mhptr = mtptr = array + (size / 2);
     hptr < tptr;
     hptr++, tptr--, mtptr++, mhptr-- )
{
    if ( *hptr  == value ) return hptr  - array;
    if ( *tptr  == value ) return tptr  - array;
    if ( *mtptr == value ) return mtptr - array;
    if ( *mhptr == value ) return mhptr - array;
}

Or I bet we could have some fun with Duff's Device. Anyone up to posting a fun Duff's variant?


Quzah.

[EvilGuru]

When you use GCC with -funroll-loops doesn't it do something like that, where as long as the upper boundary is know it is able to do many of them at once?

[Salem]

How often do you unjumble(), because that malloc/free can be pretty expensive compared to everything else going on in that function.

[quzah]

When you use GCC with -funroll-loops doesn't it do something like that, where as long as the upper boundary is know it is able to do many of them at once?

I don't know. I've never looked into that particular option. That code, if it actually functions correctly; starts one pointer at the start, headed towards the tail, one at the tail, headed towards the front, and two in the middle, one headed towards the head, and another towards the tail. So I doubt it'd be doing the same thing that the loop unrolling option does. They'd probably end up similar, I suspect it'd do it like so:

ptr0 = head, ptr1 = head + 1, ptr2 = head + 2 ...

And then increment them by the number of 'ptr's you have. Not saying that way is any worse than mine, just that mine does a different search order than it probably does.


Quzah.

[EvilGuru]

In the end I never needed the unjumble() function, I found that the best way to decrypt a file was to re-create the block array and then jumble it. Using a function I can then work out where an item is in the array so I know where to read the file from.