Topic: What is the best way to search a List object?

What is the best way to search a List object?

2 posts in topic

Flat View

Thread View

Older Post First | Reply to Topic

TOPIC ACTIONS:

Print Topic

Posted By: Michael_Dinh
Posted On: Tuesday, December 10, 2002 09:52 PM

I'm curious about concepts. So, I have a User object that has a list of Menu objects. What is the best way to search for a particular menu object? Currently, I'm using a List and then iterate through it using the Iterator interface until I find the one that I need. I'm just curious about what is the preferred method? Here is a sample of what I'm currently using. public IMenu getMenu( int _menuID ) { Iterator _menus = this.getMenu(); while( _menus.hasNext() ) { IMenu _menu = ( IMenu )_menu.next(); if ( _menu.getID() == _menuID ) { return _menu; } } return null; } More>>

			

			public IMenu getMenu( int _menuID )
			

			{
			

			Iterator _menus = this.getMenu();
			

			

			while( _menus.hasNext() )
			

			{
			

			IMenu _menu = ( IMenu )_menu.next();
			

			if ( _menu.getID() == _menuID )
			

			{
			

			return _menu;
			

			}
			

			}
			

			

			return null;
			

			}

Thank you

<<Less

Report | Quote This | Send private message | Reply | Print

Re: What is the best way to search a List object?

Posted By: Matthew_McNeely
Posted On: Tuesday, December 17, 2002 04:22 PM

Michael,

Have you considered housing the Menu objects in a hash-based collection? This way access to the Menu object is guaranteed log(n).

The method could be replaced with:


   IMenu foo = (IMenu)_menuMap.get(new Integer(_menuID));

In order to mimic the ordering of a list, use a TreeMap.

Report | Quote This | Send private message | Reply | Print

Re: What is the best way to search a List object?

Posted By: Lasse_Koskela
Posted On: Wednesday, December 11, 2002 12:17 AM

If the items in the list are not ordered, that is the only way. If the items would be ordered based on some rule, e.g. names in alphabetical order, you could apply some classic search algorithm (quicksort for instance), which would limit the needed "iterations" to a fraction of the linear search you are using currently.

This is however applicable only for bigger lists. It's probably more efficient to just go through the 5-10 items in a list than to apply a search algorithm...

Report | Quote This | Send private message | Reply | Print