Most performant way to find object in list from two attributes-CodePudding

Let's say we have a list of Houses and that list has 10,000 elements. Would Loop be the most performant way to find an object based on two attributes on it?

enum Color {
    RED,
    BLUE,
    YELLOW,
    PINK
}

class House {
    public String owner;
    public Color color;

    House(String owner, Color color) {
        this.owner = owner;
        this.color = color;
    }
}

public class Manager {
    public List<House> houses;

    Manager() {
        this.houses = new ArrayList<>();
    }

    public static void main(String[] args) {
        String owner = "Robert";
        String color = "RED";

        for (House h : houses) {
            if (h.owner.equals(owner) && Object.equals(color, h.color.name()))
            {
                System.out.println("Found it!");
            }
        }
    }
}

CodePudding user response：

Using parallel stream to iterate through the long list may help provide better performance than with usual single-threaded search:

public static void findHouses(String owner, String colorName, List<House> houses) {
    Color color = Color.valueOf(colorName);

    houses.stream()
          .parallel()
          .filter(h -> color == h.getColor() && owner.equals(h.getOwner()))
          .forEach(h -> System.out.println("Found it!"));
}

CodePudding user response：

As a comment stated:

Since 1) your list is not sorted in any way and 2) you want to get all objects matching criteria, then iterating entire list is the only way.

I think this is true. Also iterating the List is only O(n) which is not bad. If you however want a faster way and dont care about memory (and dont have to expand it that often), consider using a HashTable or something in that direction to store your data.

You can use a combined instance of your two perks as key as long as their combination of attributes is UNIQUE. If not you ran into overwriting issues.

CodePudding user response：

Assuming that your collection doesn't change much while searching, I think a hash based search will win most of the times (like @Florian_Becker mentioned). However, if you know your data well, refinements are possible.

To improve speed, you must reduce the search space. Hence, let us assume you have a data structure of this kind: HashMap<Color, List<House>>. then you can first reduce your search space by color and then iterate only within the houses of that color. If the data contains houses spread well across the colors, this will be really helpful. However, if the data has houses skewed more towards a couple of colors, searches for those houses may still be faster but not by much.

Further refinement is possible if the houseOwner values are unique across houses. You can have this: HashMap<Color, HashMap<String, House>>, where the String parameter is the house owner. However, in realtime cases, there may be multiple people with the same name.

CodePudding user response：

You can use HashMap which can help you do a constant time search.

public class Manager {
    public HashMap<String, House> houses;

    Manager() {
        this.houses = HashMap<>();
    }
    
    void insertHouse(House h) {
        // Store Owner   Color as key for this house.
        // Value will be house object
        this.houses.put(h.owner   "_"   h.color.name(), h);
    }
    void containsHouse(String owner, String color) {
        // Make key:
        String key = owner   "_"   color;
        if(houses.containsKey(key)) {
            System.out.println("house exists");
            return;
        }
    }

    public static void main(String[] args) {
        String owner = "Robert";
        String color = "RED";

        containsHouse(owner, color);
    }
}