What is the most efficient way to check if item exists in Arraylist?

Question

What is the most efficient way to do this ?

I have a ArrayList list called windowList.

GameWindow is bean having startTime and endTime.

For each object i recieve, I need to check the window of the object belongs to any of this windowList values. I need to do it for millions of values.

Please help me with most effeftive way to do this ....

Can you add class code for objects you receive and what "belongs" in your question means? — Tala, Jul 06 '13 at 10:40
Most efficient would be to have your elements in a sorted collection and performing hashed or binary search. — Michael Lang, Jul 06 '13 at 10:40
I have edited my answer; I think it should answer your need nicely — fge, Jul 06 '13 at 11:30
I disagree with the fact that this question is answered by the mentioned question, sorry... — fge, Jul 06 '13 at 11:31
Reason for the call to reopen: this is a XY problem; while OP asked to check the presence of an element in a list, in fact his problem is far different from that: it is a problem of intervals. — fge, Jul 06 '13 at 11:45

fge · Accepted Answer · 2013-07-06T11:26:52.017

Suggestion: drop your ArrayList and go with SortedMaps. We are supposing two things here:

your start and end times are long (note: code written for Java 7);
your GameWindow class implements .equals() and .hashCode() correctly.

Given these prerequisites, write a dedicated class (say, GameWindowList or something) in which you declare:

final SortedMap<Long, List<GameWindow>> startTimes = new TreeMap<>();
final SortedMap<Long, List<GameWindow>> endTimes = new TreeMap<>();

Adding a window is then:

public void addGameWindow(final GameWindow window)
{
    final long startTime = window.startTime();
    final long endTime = window.endTime();
    List<GameWindow> list;

    // Insert in start times
    list = startTimes.get(startTime);
    if (list == null) {
        list = new ArrayList<>();
        startTimes.put(startTime, list);
    }
    list.add(window);

    // Insert in end times
    list = endTimes.get(endTime);
    if (list == null) {
        list = new ArrayList<>();
        endTimes.put(endTime, list);
    }
    list.add(window);
}

Looking the windows for a given time is then:

public List<GameWindow> getWindowsForTime(final long time)
{
    // Submap of start times where the time is lower than or equal to
    // the requested time
    final SortedMap<Long, List<GameWindow>> validStartTimes 
        = startTimes.headMap(time);
    // Submap of end times where the time is greater than or equal to
    // the requested time
    final SortedMap<Long, List<GameWindow>> validEndTimes 
        = endTimes.tailMap(time);

    // Why GameWindow must implement equals and hashCode
    final Set<GameWindow> startSet = new HashSet<>();
    final Set<GameWindow> endSet = new HashSet<>();

    // Insert into the start set all game windows whose start time
    // is less than or equal to the requested time
    for (final List<GameWindow> list: startTimes.headMap(time).values())
        startSet.addAll(list);

    // Insert into the end set all game windows whose end time
    // is greater than or equal to the requested time
    for (final List<GameWindow> list: endTimes.tailMap(time).values())
        endSet.addAll(list);

    // Only retain the intersection of both sets
    startSet.retainAll(endSet);

    // Return the result
    return new ArrayList<>(startSet);
}

The two key elements are:

SortedMap's .{tail,end}Map() filter out immediately all windows whose either start or end time are not legal;
HashSet is used to retain only the intersection of windows for which both the start time and end time are legal; hence the importance of GameWindow implementing hashCode() and equals().

What is the most efficient way to check if item exists in Arraylist?

1 Answers1