Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have a list of opened nodes, with each step about 3000 nodes are opened and I want to put to the opened list only those nodes that are not already there. For now I'm just comparing each new one to all of the ones already in the opened list and only add it if it's not there. But that is around n*3000^2 comparisons for the nth step and makes the progress slower and slower each step. Is there a way to do it faster. Or at least is there a structure that would be better than ArrayList.

This is part of the bigger code, but basically the method I use:

public void addEverything() {
    List<gameState> list = current.neighbours;
    for (gameState state : list) {
        if (!isOpened(state)) {
            opened.add(state);
        }
    }
}
public boolean isOpened(gameState state) {
    for (int i = 0; i < opened.size(); i++) {
        if (state.isSame(opened.get(i)))
            return true;
    }
    return false;
}

As for the isSame() method from the gameState class, it just returns true when the two gameStates are considered the same.

share|improve this question

2 Answers 2

up vote 10 down vote accepted
  1. Instead of implementing isSame implement equals and hashCode. After that you could use a HashSet (or LinkedHashSet if the order of elements is important). Set is a collection that contains no duplicate elements and inserting/searching is much faster than searching in a list.

    Set<GameState> opened = new LinkedHashSet<GameState>();
    
    public void addEverything() {
        List<GameState> list = current.neighbours;
        for (GameState state : list) {
            opened.add(state);
        }
    }
    

    If you need a list, you can convert it back after the loop:

    List<GameState> openedList = new ArrayList<GameState>(opened);
    

    See also: Overriding equals and hashCode in Java

  2. According to the Java Code Conventions, class names in Java usually starts with uppercase letters.

share|improve this answer
    
+1. Conceptually two objects where "isSame" is true should also be "equals". If this would not be true, I would not change the "equals" semantics (and hashCode) just for performance issues. –  robermann Mar 18 at 14:08
    
One more question about this: Whenever a.equals(b), then a.hashCode() must be same as b.hashCode(). The opposite doesn't hold right? So would there be any consecunces if I were to implement hashCode() to always return 1 for example? –  Sunny Mar 18 at 14:52
    
@Sunny: Yes, you're right. hashCode could be constant but performance will suffer (it won't be faster than the original code) so don't do it. You can generate good hashCode methods with Eclipse easily but there are libraries for that too. (See the linked Stack Overflow question.) –  palacsint Mar 18 at 15:05

palacsint's answer is good, but it's missing just a few things.

All in-built Java collection classes I can think of has copy-constructors, and an addAll method. So your addEverything method can be a one liner, when using a Set<GameState>:

public void addEverything() {
    opened.addAll(current.neighbours);
}

Or, if you would like to reset the contents and create an entirely new Set, use the copy-constructor:

public void replaceEverything() {
    opened = new LinkedHashSet<GameState>(current.neighbours);
}

Since it can become a one-liner, you might not need to have it in it's own method.

Most importantly, if you are not interested in the order of the opened set, use a HashSet rather than a LinkedHashSet.

share|improve this answer
    
+1, nice catch :) –  palacsint Mar 18 at 14:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.