?
Solved

How to sort Arraylist that contains objects?

Posted on 2006-03-22
24
Medium Priority
?
532 Views
Last Modified: 2010-04-16
Hi all.
I have an ArrayList that contains objects which then contain strings as names.
I want to sort the ArrayList by the names of the obejcts. Any clever fast method?

Example code:
ArrayList thisList = new ArrayList();
MyOwnClass myClass = new MyOwnClass("myName", 1,2,3,4);
thisList.add(myClass);
...

Now I want to get a thisList that is sorted by myClass.getName().
0
Comment
Question by:Smoerble
  • 6
  • 6
  • 4
  • +2
21 Comments
 
LVL 5

Expert Comment

by:Divinity
ID: 16256481
You should implement the IComparable interface on your MyOwnClass. It would look something like this:

            public int CompareTo(object obj)
            {
                  if (obj is MyOwnClass)
                  {
                        MyOwnClass other = (MyOwnClass)obj;
                        return this.getName().CompareTo(other.getName());
                  }
                  else
                  {
                        throw new ArgumentException();
                  }
            }

Now you can simply call the Sort() method on the ArrayList theList.
0
 
LVL 12

Expert Comment

by:AGBrown
ID: 16256547
Its also good, if you are using a sorted arraylist, to maintain your arraylist as sorted so that you don't have to call Sort. This is much, much faster so you should do it if you are worried about performance. You do this by implementing IComparable as Divinity says, and then using BinarySearch to do the insert:

int intBinary = this.myArrayList.BinarySearch(myObject);
if (intBinary >= 0)
    // already exists in list according to IComparable
else
{   // otherwise insert into the list at the complement of the integer returned, which maintains the sort
    int intInsertAt = ~intBinary;
    this.myArrayList.Insert(intInsertAt, myObject);
}

As BinarySearch is O(log2 n), and Contains is O(n), if you maintain a sorted list it can help a lot with performance when you are doing a lot of object location in your list.

Andy
0
 
LVL 21

Expert Comment

by:MogalManic
ID: 16256567
There are two methods to tackle this.  Both use the ArrayList's Sort() method.

Method 1:
  Make my class implement the IComparable interface:

    public class MyOwnClass : System.Collections.IComparable
    {
       ...My Class Stuff...
       #region IComparable Implementation
            int CompareTo(object obj)
            {
                   MyOwnObject otherObj=obj as MyOwnObject;
                   If (obj==null)
                        throw new UnsupportedException("object is null or not an instance of MyOwnObject");
                  //..Implement code to compare 'this' against 'otherObj', returning :
                  //             Less than zero            This instance is less than obj.
                  //             Zero                       This instance is equal to obj.
                  //             Greater than zero      This instance is greater than obj.
            }
       #end region
   }
 

Then you can call thisList.sort();  to sort the array

Method 2

Implement another class that implements IComparer
   public class MyOwnClassComparer : System.Collections.IComparer
   {
       int Compare(object x, object y)
       {
             MyOwnClass obj1=x as MyOwnClass;
             MyOwnClass obj2=y as MyOwnClass;
              If (obj1==null || obj2==null)
                    throw new UnsupportedException("object is null or not an instance of MyOwnObject");
                  //..Implement code to compare 'obj1' against 'obj2', returning :
                  //             Less than zero            This instance is less than obj.
                  //             Zero                       This instance is equal to obj.
                  //             Greater than zero      This instance is greater than obj.
        }
    }

You would use method 2 if you did not want(or could not) to modify the class being sorted, or you want to vary the sort based on context(e.g. change sort columns and/or sort direction).  Method 1 would probably sort the class only by one specific way.
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:Smoerble
ID: 16256943
Ok, thanks guys. The concept of iComparer is new to me. Will look into it and try to get it working. Expect an answer in a few hours :)
0
 
LVL 5

Expert Comment

by:Divinity
ID: 16257043
Wow, AGBrown, I never thought of it that way. Thanks for sharing that information.
0
 

Author Comment

by:Smoerble
ID: 16257184
Stupid question now:
If I use this ArrayList I can't access the objects directly. To do this I need to use a Hashtable. Any way to combine the get-element-by-id-feature of a Hashtable with the sorted functinallity from an ArrayList?
0
 
LVL 5

Expert Comment

by:Divinity
ID: 16257244
A hashtable, by definition, isn't sorted. But could you tell us, what you are trying to achieve ? As things are right now, I think you want to do theList[name] to get the object, but theList has to be sorted as well ? Why does it need to be sorted, if you are fetching the items from it by their name ?

Or maybe I'm missing something ?
0
 
LVL 5

Expert Comment

by:Divinity
ID: 16257263
By the way, I assume you know you can get an item from an ArrayList with theList[0]. This will get the object in the first position directly.
0
 
LVL 5

Expert Comment

by:Divinity
ID: 16257308
I just keep on spamming, don't I.

If you really want to access the object by it's name, while still keeping it sorted, you should take a look at System.Collections.SortedList. This object works like a Hashtable if you look at the get-element-by-id part, but it also sorts all items by the keys of the objects. It should work for you.
0
 

Author Comment

by:Smoerble
ID: 16257390
That sounds good. Will look into it too.

The reason for my question is about caching. I have a large list of objects I want to keep in the RAM of the server and access them fast. That's why I wanted to use Hashtables.

But in some cases I need to list all of them (or some) sorted by their name (or any other property they also have). That's why I was looking for this sort thing. Sure I could access all thos things sorted from the DB, but as mentioned I want to do all from the cache that I build.
0
 
LVL 30

Accepted Solution

by:
Alexandre Simões earned 1000 total points
ID: 16257625
Hi!

You can create your own collection object.
Inehriting from the CollectionBase will let you manage the way the collection behaves and most important it will let you sepcify the Item[index] return value type.
You can then apply the IComparer implementation as stated above.

Note 1:
myObject is a sample object I created for this demo...
it can be whatever you need... custom classes, strings, ints... whatever.

Note 2:
As you have your own collection object, you can create an overload of the default property to receive the string you're looking for instead of the index.

Sample code:

    public class myObject
    {
        public string Name;
    }

    public class myCollection : System.Collections.CollectionBase
    {

        public int Add(myObject item) { return base.List.Add(item); }
        public void Remove(myObject item) { base.List.Remove(item); }
        public myObject this[int index]
        {
            get { return ((myObject)base.List[index]); }
            set { base.List[index] = value; }
        }
        public myObject this[string name]
        {
            get
            {
                return GetObjectByName(name);
            }
            set
            {
                // In this case the Set doesn't make much sence to me but you may
                //  need to do something with it...
                myObject obj = this.GetObjectByName(name);
                obj = value;
            }
        }


        private myObject GetObjectByName(string name)
        {
            if (name == null) return null;

            myObject retval = null;
            for (int i = 0; i < base.List.Count; i++)
            {
                if (this[i].Name == name) { retval = this[i]; break; }
            }
            return retval;
        }

    }

Alex :p
0
 

Author Comment

by:Smoerble
ID: 16257719
Cool. Sorry for a stupid question again... what is the better approach for my issue then? Using SortedList or creating an own collection object?

(Damn, I should be able to give away more than 500 pts!)
0
 
LVL 5

Expert Comment

by:Divinity
ID: 16257867
Well, from an OO standpoint, you just gotta love AlexCode's method. Making your own collections is just cool ;)

But since you are using this stuff to get items fast, I wouldn't recommend his function, simply because it loops through each item and checks its Name property for the given name. I don't know how SortedList works internally, but I hope they came up with something better/faster than that.
0
 
LVL 12

Assisted Solution

by:AGBrown
AGBrown earned 1000 total points
ID: 16257979
Alex's solution is a good one, so is the sorted list, or you could maintain an ArrayList of sorted names strings, and compliment it with a HashTable using the name as the key.

Use what you think is the simplest for you to maintain, as long as you can see ways to alter it in future without breaking your code. The sorted list works slower for inserts than a hashtable or unsorted ArrayList as it has to maintain the sort, but the same would be true of maintaining a sort on an ArrayList using BinarySearch. However, although the typed collection has the same effect as the sorted list, SortedList.Item/SortedList["name"] is fast O(log_2 n), and the typed collection search will be linear and slower i.e. O(n).

Are you going to be maintaing large lists (1000s of items) where performance is a problem? If not then just go for the SortedList, you can always go to your own object (typed collection) to implement fancy operations later on, once you have performance tested your code.

Andy

PS Divinity - its just another way of looking at it, and whether you use it or not depends on the predominant use of your ArrayList and so where your performance is going to be a problem. I think I picked the method up out of the OReilly C# cookbook.
0
 
LVL 12

Expert Comment

by:AGBrown
ID: 16257989
Divinity: I'm guessing that sorted list takes advantage of a binary search to return an item by index - that would make performance sense.
0
 
LVL 30

Expert Comment

by:Alexandre Simões
ID: 16258042

You have to choose...
SortedList isn't that fast either since it has to reorder the items on Add... but you also have to do that on this custom collection if you want an automated sortedlist... maybe a BubbleSort approach.

This depends on how many object you need to deal with.
With about 100 obejct it works fine... maybe more... you can teste it simply creating a loop to add items to a collection and then quering it.


You can also create a TypedDataSet and deal with a typed Table object.
The name of the objects will also be available thru intellisense and you can manage it, sort it and whatever as if it really was a DataBase object...




Alex :p
0
 
LVL 12

Expert Comment

by:AGBrown
ID: 16258068
For performance, I think a typed Dataset will be worse than all of the other options.
0
 
LVL 30

Expert Comment

by:Alexandre Simões
ID: 16258934

I never user Datasets... either kind...
They are slow and do too much work behind the scenes and are slow... slower than any other approach...

But I must admit that it makes certain things easier to accomplish (in-memory queries, sorts, links between objects, (de)serialization)...

The important thing is to have a good knowledge about either the tools the prog language provides and the need we have.

Alex :p
0
 
LVL 12

Expert Comment

by:AGBrown
ID: 16259540
True. Maybe a summary?

-IComparable and IComparer can be used to sort any object of a given type with respect to another object of the same type (or even a different type if you so wish to dig that hole).
-Sorted object - if they are .NET objects, such as ArrayList or SortedList, it's likely they will use the same mechanism behind the scenes to maintain the sort as you add objects. Therefore maintaining a sorted arraylist with your own BinarySearch is the same as adding an object to SortedList.
-Therfore, adding an item to a sorted object has an overhead, as underneath everything in the array frmo that point on needs to be shifted on one. Getting an item out is fast due to the BinarySearch that can be used to find an object.
-Unsorted objects (Hashtable) are fast to add objects to, but slower to get objects out of by name/non-numeric index than sorted objects.
-A sorted ArrayList + Hashtable is a poor man's solution, as you are maintaining a lot of objects by the time you get to the bottom of it all.
-SortedList will be slow to insert, fast to retrieve by name, therefore might be your best solution.
-Hashtable will be fast to insert, slower to retrieve by name. You can't sort it without extra objects (such as a sorted arraylist).
-Typed Collection based on CollectionBase will behave the same as a Hashtable, but it will be typed, and you can present a "sorted" facade to it, therefore is the best in terms of design patterns, but only necessary once you need extra performance or functionality you couldn't get out of a .NET object.
-Datasets are a RAD-based solution to typed collections, but are very heavyweight objects

And none of that really matters if you only have O(100) objects, so you decide.

I would say SortedList for you. Anyone else want to weigh in? One vote each only lol :-)

Andy
0
 
LVL 30

Expert Comment

by:Alexandre Simões
ID: 16260256

Facts & Problems regarding SortedList:

Facts 1:
SortedLists are based on HashTables... it's just a sortable HashTable.
HashTables items have 2 things: one key and one velue.

Fact 2:
The key is unique...
So you can't enter 2 keys with the same value.

Fact 3:
SortedList sorts based on the keys.

Problem 1:
On adding a new item to the SortedList collection we must specify 2 values (key & object) instead of simply giving 1 object.

Problem 2:
We can't have 2 objects that have the same value on the same property we want to sort by.

Problem 3:
The return value is always of type object... we always need to cast it.

-- // --

This is why I like the custom collection inherited from CollectionBase...
It's easier to maintain and behaves just like we want to.

If you're using the .net Framework 2.0 use the Generic Collections :))

Once again, if none of the problems I mentioned apply to you then use the SortedList, otherwise create a custom collection.




Alex :p
0
 
LVL 12

Expert Comment

by:AGBrown
ID: 16331812
Smoerble,

Did you have any luck with any of the ideas we posted? I know I would be interested to know how you got on, I'm sure the others would. :-)

Andy
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Entity Framework is a powerful tool to help you interact with the DataBase but still doesn't help much when we have a Stored Procedure that returns more than one resultset. The solution takes some of out-of-the-box thinking; read on!
This article aims to explain the working of CircularLogArchiver. This tool was designed to solve the buildup of log file in cases where systems do not support circular logging or where circular logging is not enabled
Despite its rising prevalence in the business world, "the cloud" is still misunderstood. Some companies still believe common misconceptions about lack of security in cloud solutions and many misuses of cloud storage options still occur every day. …
With just a little bit of  SQL and VBA, many doors open to cool things like synchronize a list box to display data relevant to other information on a form.  If you have never written code or looked at an SQL statement before, no problem! ...  give i…

839 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question