CODEWITHSUNDEEP
javaarraysarraylist
Zakozak90
Zakozak90

Reputation: 31

Optimise to find objects with the highest field value in array list

I made a function that returns an array list with the people having the highest number field. But I'm pretty sure that this can be optimized

public  ArrayList<Membre> findOlder(){
    ArrayList<Membre>olderPersonnes = new ArrayList<Membre>();
    int higher = 0;
    for (Membre membre : membresDeLaFamille) {
        if (membre.getNumber() > higher) {
            higher = membre.getNumber();
        }
    }
    for (Membre membre: membresDeLaFamille) {
        if (membre.getNumber() == higher) {
            olderPersonnes.add(membre);
        }
    }
    return olderPersonnes;
}

Upvotes: 0

Views: 199

Answers (3)

Nowhere Man
Nowhere Man

Reputation: 19565

Basically, the list of multiple family members with the maximum number may be retrieved in the one pass if the input list membresDeLaFamille is unsorted, and as soon as the new "max" is found, current list should be cleared:

public List<Membre> findOlder() {
    List<Membre> olderPersonnes = new ArrayList<>();
    int higher = 0;
    for (Membre membre : membresDeLaFamille) {
        if (membre.getNumber() >= higher) {
            if (membre.getNumber() > higher) {
                higher = membre.getNumber();
                olderPersonnes.clear();
            }
            olderPersonnes.add(membre);
        }
    }
    return olderPersonnes;
}

If the input list happens to be already sorted by the values returned by Membre::getNumber, then the max value(s) is/are surely placed at some end of the input list (depending on the ascending or descending order of sorting).

Upvotes: 0

plalx
plalx

Reputation: 43718

You can't do better than O(1) runtime complexity (unless the list is sorted already), so this is already optimized.

In terms of readability you could do better (arguably) using declarative (and functional concepts) vs imperative programming, but it certainly wouldn't be faster.

e.g.

public static List<Member> findOlder() {
    return membresDeLaFamille.stream()
        .map(Member::getNumber)
        .max(Integer::compare)
        .map(maxAge -> membresDeLaFamille.stream().filter(m -> maxAge.equals(m.getNumber())))
        .orElseGet(Stream::empty)
        .collect(Collectors.toList());
}

Upvotes: 1

Tom Elias
Tom Elias

Reputation: 782

optimize? depends on what you're optimizing for.

complexity - this is an O(n) loop, it is already the least "complex" it can be. (findmax in an unsorted array of size n -> O(n))

running time - can be improved if instead of the second loop you just keep a reference to the "membre" that you find inside the first loop, and return that.

Upvotes: 1

Related Questions