SortedList, searching for items efficiently 
Author Message
 SortedList, searching for items efficiently

Greetings,

    I have a list of sorted items. For the sake of simplicity, let's say
that these items are of type 'int' and are stored in a SortedList. The list
contains about 10,000 ints. Now, what is the fastest way for me to find the
index of the *first* item in the list that is greater than or equal to
5,654?  What is the fastest way for me to find the *latest* index
corresponding to a value less than or equal to 3,331?

    Right now I'm handling this the "brute" force way. I'm simply iterating
through the entire list and examining each item. Since the items are sorted,
it seems that there should be a more efficient way. None of the SortedList
methods seem to be what I'm looking for.

--
If you need to reach me by email, use dsworde1 AT san DOT rr DOT com

David



Wed, 30 Mar 2005 04:43:45 GMT  
 SortedList, searching for items efficiently
I don't think there are any standard .NET functions to do what you're asking
for, so you'd have to write the code yourself.

The more "general purpose" approach would be to just do a binary search.  If
you have 10,000 ints, take the middle one at position 5000 and test it.  If
it's higher than the number you want, then look at the first 5000 numbers.
If it's lower than the number you want, look at the second 5000.  Then
repeat the process on that set.  ie, the next number you look at would be
#2500 or #7500 depending on the result of your test on #5000

You have the additional requirement that you want to find the first or last
occurance of that number.  To do that when you find the number you want, you
need to do additional searches until you identify the exact boundary of two
consecutive entries where one is the number that you want, and the other is
too small (if you're looking for the first) or too large (if you're looking
for the last).  Then you'll know you've found the "first" entry.

Wyatt

"David Sworder (formerly known as "Rev. Dr. Hulio Manuel Sanchez-Cruz")"

Quote:

> Greetings,

>     I have a list of sorted items. For the sake of simplicity, let's say
> that these items are of type 'int' and are stored in a SortedList. The
list
> contains about 10,000 ints. Now, what is the fastest way for me to find
the
> index of the *first* item in the list that is greater than or equal to
> 5,654?  What is the fastest way for me to find the *latest* index
> corresponding to a value less than or equal to 3,331?

>     Right now I'm handling this the "brute" force way. I'm simply
iterating
> through the entire list and examining each item. Since the items are
sorted,
> it seems that there should be a more efficient way. None of the SortedList
> methods seem to be what I'm looking for.

> --
> If you need to reach me by email, use dsworde1 AT san DOT rr DOT com

> David



Wed, 30 Mar 2005 05:00:16 GMT  
 SortedList, searching for items efficiently



Quote:
> I don't think there are any standard .NET functions to do what you're
asking
> for, so you'd have to write the code yourself.

    Hi Wyatt... I was considering taking the approach that you described,
but I was hoping that the .NET framework had already done the work for me.
:(

David



Wed, 30 Mar 2005 05:07:09 GMT  
 SortedList, searching for items efficiently
    Actually, there is a method called Array.BinarySearch() which is pretty
close to what I'm looking for.


Wed, 30 Mar 2005 05:20:35 GMT  
 SortedList, searching for items efficiently
I don't think you can use BinarySearch() because of your requirement that
you want to find the first or the last instance, whereas BinarySearch as it
is now will only let you find "an" instance.

For a moment I thought you could write an IComparer that took into account
an element's neighbours when doing a comparison, but that's not directly
possible because the IComparer.Compare function only takes the 2 values and
doesn't pass in the indexes that those elements are at.

"David Sworder (formerly known as "Rev. Dr. Hulio Manuel Sanchez-Cruz")"

Quote:

>     Actually, there is a method called Array.BinarySearch() which is
pretty
> close to what I'm looking for.



Wed, 30 Mar 2005 05:54:39 GMT  
 SortedList, searching for items efficiently

Quote:
> I don't think you can use BinarySearch() because of your requirement that
> you want to find the first or the last instance, whereas BinarySearch as
it
> is now will only let you find "an" instance.

    Yeah, this is true. However, BinarySearch() gives me a decent starting
point to begin searching for the appropriate record. It's much faster than
my "brute force" method of examining each and every item in the list.

    Thanks for the tip. Had you not mentioned the concept of a "binary
search", I never would have thought to look for a BinarySearch() method.

David



Wed, 30 Mar 2005 07:07:20 GMT  
 SortedList, searching for items efficiently
The Array.BinarySearch method stops at the first element whose
IComparable.CompareTo results in a value of zero or higher.  If the compare
result is zero, BinarySearch returns the index.  If the compare is greater
than zero, BinarySearch returns the -1 * index.  (Strange, but hey, I didn't
write it.)

Therefore, when you call BinarySearch, you need to check the value returned
to see what the result is.  Note that in the example below, FindObj assumes
the array is sorted.  If you need to sort your array, there is a sort method
provided.

- - -

using System;
public class Demo
{
    public static void FindObj( Array ary, Object obj )
    {
        int i = Array.BinarySearch( ary, obj );
        if ( i < 0 )
        {
            i = ~i;
            Console.WriteLine( "The object to search for ({0}) is not
found.", obj);
            if (i < ary.GetUpperBound(0))
                Console.WriteLine( "\tThe next larger object is at index
{0}.", i );
            else
                Console.WriteLine( "\tThere is no larger object");
            if (i > ary.GetLowerBound(0))
                Console.WriteLine( "\tThe next smaller object is at index
{0}.", --i );
            else
                Console.WriteLine( "\tThere is no smaller object");
        }
        else
            Console.WriteLine( "The object to search for ({0}) is at index
{1}.", obj, i );
    }

    public static void Main()
    {
        Array myIntAry = Array.CreateInstance( typeof(Int32), 50 );
        for ( int i = myIntAry.GetLowerBound(0); i <=
myIntAry.GetUpperBound(0); ++i )
            myIntAry.SetValue( i*2, i ); // Fill with even numbers 0 through
100
        myIntAry.Sort();

        FindObj(myIntAry, 50); // Should find
        FindObj(myIntAry, 51); // Not present, but there is one that is
larger and one that is smaller
        FindObj(myIntAry, -3); // Not present, but there is one that is
larger
        FindObj(myIntAry, 101); // Not present, but there is one that is
smaller
    }

Quote:
}

- - -

Robert L. Ayers

"David Sworder (formerly known as "Rev. Dr. Hulio Manuel Sanchez-Cruz")"

Quote:

>     Actually, there is a method called Array.BinarySearch() which is
pretty
> close to what I'm looking for.



Wed, 30 Mar 2005 12:24:24 GMT  
 SortedList, searching for items efficiently

Quote:
> result is zero, BinarySearch returns the index.  If the compare is greater
> than zero, BinarySearch returns the -1 * index.  (Strange, but hey, I
didn't
> write it.)

    Yeah, the whole "ones complement" thing struck me as kind of weird
too -- but hey, it works beautifully. I wish I would have known about this
method a long time ago.

David



Thu, 31 Mar 2005 01:08:51 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. SortedList with duplicate items?

2. SortedList Collection

3. Odd problem with System.Collections.SortedList

4. deriving from SortedList?

5. SortedList sorted by value.

6. SortedList!!

7. Please Help with SortedList!!!

8. SortedList, Why Parenthesis instead of Brackets?

9. Collections.SortedList

10. SortedList Key as DateTime Class?

11. Dealing with pointers and castings efficiently

12. copying n consecutive bits efficiently

 

 
Powered by phpBB® Forum Software