Results 1 to 5 of 5
  1. #1
    Dark's Avatar
    Dark is offline Senior Member
    Join Date
    Apr 2011
    Location
    Camp Lejuene, North Carolina
    Posts
    643
    Rep Power
    4

    Default ArrayList and .contains() question

    Ok so in another topic I was discussing about how it might be more efficient to use .contains() to search through an arraylist, however I wasn't sure how exactly.

    This is entirely hypothetical and here is the code I suggested to search through an arraylist to find an object.

    Java Code:
    for (int i=0; i<myArray.size();i++)
    {
         if((myArray.get(i).getName()).equals(location))
              myArray.get(i).addMileage(2000);
    }
    myArray is the array list.
    getName() is a method that returns a string from the object.
    location is an inputed string from the user
    addMileage() is a method that adds an integer to the objects mileage variable.

    So my question is, how could you make this more efficient. While its fine for short arrays, but if I was making an inventory program for a car dealership that had 3000-4000 cars on the lot at any given time this would be rather inefficient as every search would have to go through every car.

    This is what Norm suggested, and I am curious for a further explanation.
    The contains() method uses the equals() method which can look for the same object vs an object with the same contents. With a large number of items, a Map might be a better container for quick look ups.
    Or you could override the class's equals() method. That can be tricky if the object is used in some containers that use hashcode.

    For student exercises, none of this matters.
    I suggested to the OP of the previous topic that .contains() might be more efficient but I couldn't figure out how in my head. Is this true? If it is then can someone explain how I would use it in a more efficient manner?

    Does anyone who has a bit more knowledge than myself have an idea as to how I could make this more efficient?
    • Use [code][/code] tags when posting code. That way people don't want to stab their eyes out when trying to help you.
    • +Rep people for helpful posts.

  2. #2
    doWhile is offline Moderator
    Join Date
    Jul 2010
    Location
    California
    Posts
    1,641
    Rep Power
    7

    Default

    Use a Set (for example a HashSet), which is specifically designed as containing unique elements (defined by the hashcode/equals method of the contained objects). Rather then linearly searching over a full array (as your example demonstrates), finding objects in this manner in a Set or Map is much faster as they rely on using the hashCode and a hashFunction to determine where to place the object (or where the object has been placed), reducing a linear time data structure to approximately constant time for this operation. See the following for a more detailed explanation Hash table - Wikipedia, the free encyclopedia
    Last edited by doWhile; 07-08-2011 at 09:17 PM.

  3. #3
    Dark's Avatar
    Dark is offline Senior Member
    Join Date
    Apr 2011
    Location
    Camp Lejuene, North Carolina
    Posts
    643
    Rep Power
    4

    Default

    Ok, I figured that something like that would be more efficient. However would .contains be any more efficient then the way I wrote the arraylist search? I don't really see how it would be unless it does something that I don't know about.
    • Use [code][/code] tags when posting code. That way people don't want to stab their eyes out when trying to help you.
    • +Rep people for helpful posts.

  4. #4
    doWhile is offline Moderator
    Join Date
    Jul 2010
    Location
    California
    Posts
    1,641
    Rep Power
    7

    Default

    Quote Originally Posted by Dark View Post
    Ok, I figured that something like that would be more efficient. However would .contains be any more efficient then the way I wrote the arraylist search? I don't really see how it would be unless it does something that I don't know about.

    Contains for a Set is much faster than an ArrayList. Try the following example, of course you can adjust the max value more appropriate to your system:
    Java Code:
    public static void main(String[] args) {
    		final int max = 50000;
    		List<Integer> list = new ArrayList<Integer>();
    		Set<Integer> set = new HashSet<Integer>();
    		for ( int i = 0; i < max; i++ ){
    			list.add(i);
    			set.add(i);
    		}
    		System.out.println("Time for List: " + getTime(list, max));
    		System.out.println("Time for Set: " + getTime(set, max));
    	}
    	
    	private static long getTime(Collection<Integer> c, int max){
    		long start = System.currentTimeMillis();
    		for ( int i = 0; i < max; i++ ){
    			if ( c.contains(i) ){
    				//demo only
    			}
    		}
    		return System.currentTimeMillis() - start;
    	}
    Last edited by doWhile; 07-08-2011 at 09:30 PM.

  5. #5
    Dark's Avatar
    Dark is offline Senior Member
    Join Date
    Apr 2011
    Location
    Camp Lejuene, North Carolina
    Posts
    643
    Rep Power
    4

    Default

    Hmm, I will have to play around with that. Gives me a project to work on tomorrow, thank you much sir.
    • Use [code][/code] tags when posting code. That way people don't want to stab their eyes out when trying to help you.
    • +Rep people for helpful posts.

Similar Threads

  1. add method from Arraylist - question
    By Adomini in forum New To Java
    Replies: 6
    Last Post: 10-21-2010, 07:08 PM
  2. Question about arraylist
    By Metastar in forum New To Java
    Replies: 7
    Last Post: 10-01-2010, 11:53 PM
  3. ArrayList question
    By spatel14 in forum New To Java
    Replies: 4
    Last Post: 07-07-2010, 10:02 PM
  4. Beginner question about ArrayList
    By kesi in forum New To Java
    Replies: 3
    Last Post: 09-19-2009, 11:30 PM
  5. arraylist question
    By lisa.lipsky in forum JavaServer Pages (JSP) and JSTL
    Replies: 1
    Last Post: 09-16-2009, 11:07 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •