Algorithm to compare to arrays of int

Discussion in 'C Programming' started by Devrobcom, May 18, 2004.

  1. Devrobcom

    Devrobcom Guest

    Hi
    I have an array with 30 int and another array with 1000 int.
    If any of the 30 intergers can be found in the 1000 int array I shall return
    true.
    The contents of the arrays will also change over time.
    I'm looking for a way to do this with good performance.

    One way could be to:

    bool any_match(int smal[], int smal_sz, int large[], int large_sz)
    {
    for(int i = 0; i < smal_sz; i++)
    {
    if ( binary_search(large, large_sz, smal) >= 0) return true;
    }
    return false;
    }

    void my_main_thread()
    {
    //
    int large_array[1000];
    int smal_array[30]

    //
    // sort large array when updated
    //

    // check if any id can be found
    if (any_match(smal_array, 30, large_array, 1000) )
    {
    dowork();
    }
    }

    Since I will do this very frequently I need something that takes little cpu.
    The memory size is not a problem.

    /Dev
     
    Devrobcom, May 18, 2004
    #1
    1. Advertising

  2. Devrobcom

    Allan Bruce Guest

    "Devrobcom" <> wrote in message
    news:40a9cbe9$...
    > Hi
    > I have an array with 30 int and another array with 1000 int.
    > If any of the 30 intergers can be found in the 1000 int array I shall

    return
    > true.
    > The contents of the arrays will also change over time.
    > I'm looking for a way to do this with good performance.
    >
    > One way could be to:
    >
    > bool any_match(int smal[], int smal_sz, int large[], int large_sz)
    > {
    > for(int i = 0; i < smal_sz; i++)
    > {
    > if ( binary_search(large, large_sz, smal) >= 0) return true;
    > }
    > return false;
    > }
    >
    > void my_main_thread()
    > {
    > //
    > int large_array[1000];
    > int smal_array[30]
    >
    > //
    > // sort large array when updated
    > //
    >
    > // check if any id can be found
    > if (any_match(smal_array, 30, large_array, 1000) )
    > {
    > dowork();
    > }
    > }
    >
    > Since I will do this very frequently I need something that takes little

    cpu.
    > The memory size is not a problem.
    >


    If speed is an issue, then consider using a hashtable. Have the hashtable
    store the int as your index and a char as the data. If the data returned is
    non-null then your number is located in the hashtable. You must remember to
    remove items from the hashtable this way tho.
    Allan
     
    Allan Bruce, May 18, 2004
    #2
    1. Advertising

  3. Devrobcom

    Stephen L. Guest

    Devrobcom wrote:
    >
    > Hi
    > I have an array with 30 int and another array with 1000 int.
    > If any of the 30 intergers can be found in the 1000 int array I shall return
    > true.
    > The contents of the arrays will also change over time.
    > I'm looking for a way to do this with good performance.
    >
    > One way could be to:
    >
    > bool any_match(int smal[], int smal_sz, int large[], int large_sz)
    > {
    > for(int i = 0; i < smal_sz; i++)
    > {
    > if ( binary_search(large, large_sz, smal) >= 0) return true;
    > }
    > return false;
    > }
    >
    > void my_main_thread()
    > {
    > //
    > int large_array[1000];
    > int smal_array[30]
    >
    > //
    > // sort large array when updated
    > //
    >
    > // check if any id can be found
    > if (any_match(smal_array, 30, large_array, 1000) )
    > {
    > dowork();
    > }
    > }
    >
    > Since I will do this very frequently I need something that takes little cpu.
    > The memory size is not a problem.
    >
    > /Dev


    You imply that you program has knowledge when
    a position in the "large" array is updated.
    Why not, for each position changed in this "large"
    array, search the "small" array for a match.

    Since you haven't mentioned how the "large" array
    is updated (round-robin, etc.), doing the above
    may eliminate the need for keeping the "large"
    array sorted (if its only purpose is for a later
    binary search). Saving a 1000 item sort has gotta
    provide a performance boost...

    HTH,

    Stephen
     
    Stephen L., May 18, 2004
    #3
  4. Devrobcom

    buda Guest

    Hashing seems to be the only way to make this really fast IMHO.


    "Devrobcom" <> wrote in message
    news:40a9cbe9$...
    > Hi
    > I have an array with 30 int and another array with 1000 int.
    > If any of the 30 intergers can be found in the 1000 int array I shall

    return
    > true.
    > The contents of the arrays will also change over time.
    > I'm looking for a way to do this with good performance.
    >
    > One way could be to:
    >
    > bool any_match(int smal[], int smal_sz, int large[], int large_sz)
    > {
    > for(int i = 0; i < smal_sz; i++)
    > {
    > if ( binary_search(large, large_sz, smal) >= 0) return true;
    > }
    > return false;
    > }
    >
    > void my_main_thread()
    > {
    > //
    > int large_array[1000];
    > int smal_array[30]
    >
    > //
    > // sort large array when updated
    > //
    >
    > // check if any id can be found
    > if (any_match(smal_array, 30, large_array, 1000) )
    > {
    > dowork();
    > }
    > }
    >
    > Since I will do this very frequently I need something that takes little

    cpu.
    > The memory size is not a problem.
    >
    > /Dev
    >
    >
     
    buda, May 18, 2004
    #4
  5. Devrobcom

    Severian Guest

    On Tue, 18 May 2004 10:40:08 +0200, "Devrobcom"
    <> wrote:

    >Hi
    >I have an array with 30 int and another array with 1000 int.
    >If any of the 30 intergers can be found in the 1000 int array I shall return
    >true.
    >The contents of the arrays will also change over time.
    >I'm looking for a way to do this with good performance.
    >
    >One way could be to:
    >
    >bool any_match(int smal[], int smal_sz, int large[], int large_sz)
    >{
    > for(int i = 0; i < smal_sz; i++)
    > {
    > if ( binary_search(large, large_sz, smal) >= 0) return true;
    > }
    > return false;
    >}
    >
    >void my_main_thread()
    >{
    >//
    >int large_array[1000];
    >int smal_array[30]
    >
    >//
    >// sort large array when updated
    >//
    >
    >// check if any id can be found
    >if (any_match(smal_array, 30, large_array, 1000) )
    >{
    > dowork();
    >}
    >}
    >
    >Since I will do this very frequently I need something that takes little cpu.
    >The memory size is not a problem.


    If the range of integers in large_array is reasonably constrained, you
    could use a bit to represent each possibile value, making setting and
    checking very fast. If the range is not limited, create a hash table.

    --
    Sev
     
    Severian, May 18, 2004
    #5
  6. Devrobcom

    Case Guest

    Devrobcom wrote:
    > Hi
    > I have an array with 30 int and another array with 1000 int.
    > If any of the 30 intergers can be found in the 1000 int array I shall return
    > true.
    > The contents of the arrays will also change over time.
    > I'm looking for a way to do this with good performance.
    >
    > One way could be to:
    >
    > bool any_match(int smal[], int smal_sz, int large[], int large_sz)
    > {
    > for(int i = 0; i < smal_sz; i++)
    > {
    > if ( binary_search(large, large_sz, smal) >= 0) return true;


    Is binary_search a standard C library function?

    > }
    > return false;
    > }
    >
    > void my_main_thread()
    > {
    > //
    > int large_array[1000];
    > int smal_array[30]
    >
    > //
    > // sort large array when updated
    > //
    >
    > // check if any id can be found
    > if (any_match(smal_array, 30, large_array, 1000) )
    > {
    > dowork();
    > }
    > }
    >
    > Since I will do this very frequently I need something that takes little cpu.
    > The memory size is not a problem.


    It depends how often your arrays are updated compared to how
    often you do the match. So, could you give details about how
    many items at a time and how often you update each array...
    Also interesting to know might be the sizeof the ints (or the
    range of values); small int/range might 'allow' other strategies.

    Kees
     
    Case, May 18, 2004
    #6
  7. Devrobcom

    Grumble Guest

    Devrobcom wrote:

    > I have an array with 30 int and another array with 1000 int.
    > If any of the 30 integers can be found in the 1000 int array
    > I shall return true.
    > The contents of the arrays will also change over time.
    > I'm looking for a way to do this with good performance.


    comp.programming could probably help you out.
     
    Grumble, May 18, 2004
    #7
  8. Devrobcom

    Alex Guest

    "Case" <> wrote in message
    news:40aa0b2f$0$65124$4all.nl...
    > Is binary_search a standard C library function?


    No, but bsearch() is.

    Alex
     
    Alex, May 18, 2004
    #8
  9. Devrobcom

    Devrobcom Guest

    Thank you all!
    I have been away from my computer the whole day and haven't been able to
    join.
    I will check if I can use a hash table.
    /Dev
     
    Devrobcom, May 19, 2004
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Schnoffos
    Replies:
    2
    Views:
    1,221
    Martien Verbruggen
    Jun 27, 2003
  2. Hal Styli
    Replies:
    14
    Views:
    1,646
    Old Wolf
    Jan 20, 2004
  3. arun
    Replies:
    8
    Views:
    457
    Dave Thompson
    Jul 31, 2006
  4. aling
    Replies:
    8
    Views:
    958
    Jim Langston
    Oct 20, 2005
  5. Replies:
    4
    Views:
    906
    James Kanze
    Oct 29, 2008
Loading...

Share This Page