Searching An Array

This is a discussion on Searching An Array within the C Programming forums, part of the General Programming Boards category; I need to search an array of integers for a value and then return its offset. I currently use this: ...

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    42

    Searching An Array

    I need to search an array of integers for a value and then return its offset. I currently use this:
    Code:
    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.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,417
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Apr 2005
    Posts
    42
    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:
    Code:
    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);
    }

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Code:
    	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?
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,417
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Loop unrolling! Make four checks per iteration. Sure, that sounds fun!
    Code:
    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.
    Last edited by quzah; 10-15-2005 at 02:55 PM. Reason: Making it nice and tidy.
    Hope is the first step on the road to disappointment.

  8. #8
    Registered User
    Join Date
    Apr 2005
    Posts
    42
    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?

  9. #9
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,417
    How often do you unjumble(), because that malloc/free can be pretty expensive compared to everything else going on in that function.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by 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?
    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:
    Code:
    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.
    Last edited by quzah; 10-15-2005 at 05:22 PM.
    Hope is the first step on the road to disappointment.

  11. #11
    Registered User
    Join Date
    Apr 2005
    Posts
    42
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 07-11-2008, 07:39 AM
  2. 2d array question
    By gmanUK in forum C Programming
    Replies: 2
    Last Post: 04-21-2006, 12:20 PM
  3. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 04:15 AM
  4. Help with an Array
    By omalleys in forum C Programming
    Replies: 1
    Last Post: 07-01-2002, 08:31 AM
  5. searching thru a c++ class array
    By stanleyw in forum C++ Programming
    Replies: 1
    Last Post: 05-29-2002, 09:15 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21