3

Have a list of integers like

List<Integer> l = new ArrayList<Integer>();

I think calling l.contains is slow, how to sort the list. After sorting, will l.contains behave faster?

Is there any sortedList I can use directly?

Bhesh Gurung
  • 50,430
  • 22
  • 93
  • 142
user705414
  • 20,472
  • 39
  • 112
  • 155
  • 2
    `l.sort()` doesn't work? http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Collections.html#sort%28java.util.List%29 – Oliver Jan 16 '12 at 15:08
  • 3
    @Oliver `sort` is not defined on `Collection` – adarshr Jan 16 '12 at 15:09
  • You might find this useful also http://stackoverflow.com/questions/2661065/a-good-sorted-list-for-java – Marthin Jan 16 '12 at 15:10
  • I believe sorting the list will only make `.contains()` faster for lower numbers, and slower for higher numbers. It will remain O(n). Converting to a `Set`, on the other hand, will allow for faster lookups. – Wooble Jan 16 '12 at 15:13

7 Answers7

13

It can't get simpler than this.

Collections.sort(l);
adarshr
  • 61,315
  • 23
  • 138
  • 167
7

Sorting of list would not make contains operation faster. It still be O(n) in worst case.

However you can sort your list and perform the binary search on top of it.

Collections.sort(l);
Collections.binarySearch(l, a);

This will take O(lg(n)) time in worst case.

But if you want a high performance contains operation consider using HashSet instead of ArrayList. It takes nearly constant time.

Mairbek Khadikov
  • 7,939
  • 3
  • 35
  • 51
4

You can use Collections.sort(l);

fmucar
  • 14,361
  • 2
  • 45
  • 50
2

The sort() method from Collections can help you sort your ArrayList.

talnicolas
  • 13,885
  • 7
  • 36
  • 56
1

contains() on a ArrayList doesn't assume the array is sorted, even if it is. You'll want to use some sort of set (HashSet will give you the best find performance, and a LinkedHashSet will retain the order. Even a TreeList will give you better performance.)

0

TreeSet may be useful for you. 

SortedSet<Integer> s = new TreeSet<Integer>(l);
e-zinc
  • 4,491
  • 2
  • 20
  • 17
  • Note that this will also remove duplicates, which may not be what user705414 wanted. – Jesper Jan 16 '12 at 15:30
  • Yes, you are right, but the main aim of the problem is to make **l.contains** to be executed faster. – e-zinc Jan 16 '12 at 15:37
0

If Collections.sort(l) does not give the desired result, try Collections.sort(l, comparator) where "comparator" is something like this:

class MyComparator implements Comparator<Integer>
{
  public int compare(Integer lhs, Integer rhs)
  {
    // perform the desired comparison.
  }
}

Edit: I'll leave this up, but the answer by "Mairbek Khadikov" seems to be the best answer.

DwB
  • 37,124
  • 11
  • 56
  • 82