Efficient implementation of multi-factor weighted sorting in Java

Question

I'm looking for an efficient implementation of weighted sorting with multiple fields in Java. This question is somehow similar to How to provide most relevant results with Multiple Factor Weighted Sorting and Need help maximizing 3 factors in multiple, similar objects and ordering appropriately. However, I'm asking for some guideline on efficient implementation.

In this below example, the Person class has the age and income fields and I would like to sort the arraylist persons with lower age and higher income combination based on the given preference and in descending order. I've provided equal preferences for the age and income. The sum of the preferences should be 1.

As you can see in this naive implementation there are too many loops to iterate and eventually its too costly to run for a very large number of inputs. I also explored Guava's ComparisonChain and Apache Commons CompareToBuilder but it seemed they are not fulfilling my objectives.

package main.java.utils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class SortingTest {

static double income_preference = 0.5;
static double age_preference = 1 - income_preference;

public static void main(String args[]) {
    ArrayList<Person> persons = new ArrayList<Person>();

    persons.add(new Person("A", 60, 55.0));
    persons.add(new Person("B", 45, 50.0));
    persons.add(new Person("C", 20, 50.0));
    persons.add(new Person("D", 55, 60.0));
    persons.add(new Person("E", 30, 85.0));

    // Sort the array list by income (descending order)
    Collections.sort(persons, new Comparator<Person>(){
        @Override
        public int compare(Person p1, Person p2) {              
            return (((double)p1.income > (double)p2.income) ? -1 : 
                ((double)p1.income < (double)p2.income) ? 1 : 0);               
        }
    });

    // Rank based on income
    int income_rank = persons.size();
    for(int i = 0; i < persons.size(); i++) {
        if(i != 0)
            if(persons.get(i).income != persons.get(i-1).income)
                --income_rank;

        persons.get(i).income_rank = income_rank * income_preference;
    }

    System.out.println("List of persons sorted by their income in descending order: ");
    for(Person p : persons) 
        System.out.println(p.toString());       

    // Sort the array list by age (ascending order)
    Collections.sort(persons, new Comparator<Person>(){
        @Override
        public int compare(Person p1, Person p2) {              
            return (((double)p2.age > (double)p1.age) ? -1 : 
                ((double)p2.age < (double)p1.age) ? 1 : 0);             
        }
    });

    // Rank based on age
    int age_rank = persons.size();
    for(int i = 0; i < persons.size(); i++) {
        if(i != 0)
            if(persons.get(i).age != persons.get(i-1).age)
                --age_rank;

        persons.get(i).age_rank = age_rank * age_preference;
    }       

    System.out.println();
    System.out.println("List of persons sorted by their age in ascending order: ");
    for(Person p : persons) 
        System.out.println(p.toString());       

    // Assign combined rank     
    for(Person p : persons)
        p.combined_rank = (p.age_rank + p.income_rank);

    // Sort the array list by the value of combined rank (descending order)
    Collections.sort(persons, new Comparator<Person>(){
        @Override
        public int compare(Person p1, Person p2) {              
            return (((double)p1.combined_rank > (double)p2.combined_rank) ? -1 : 
                ((double)p1.combined_rank < (double)p2.combined_rank) ? 1 : 0);             
        }
    });

    System.out.println();
    System.out.println("List of persons sorted by their combined ranking preference in descending order: ");
    for(Person p : persons) 
        System.out.println(p.toString());
}
}

class Person {  
String name;
int age; // lower is better
double income; // higher is better
double age_rank;
double income_rank;
double combined_rank;

public Person(String name, int age, double income) {
    this.name = name;
    this.age = age;
    this.income = income;
    this.age_rank = 0.0;
    this.income_rank = 0.0;
    this.combined_rank = 0.0;
}

@Override
public String toString() {
    return ("Person-"+this.name+", age("+this.age+"|"+this.age_rank+"th), income("+this.income+"|"+this.income_rank+"th), Combined Rank("+this.combined_rank+")");
}
}

Console Output

List of persons sorted by their income in descending order:

Person-E, age(30|0.0th), income(85.0|2.5th), Combined Rank(0.0)

Person-D, age(55|0.0th), income(60.0|2.0th), Combined Rank(0.0)

Person-A, age(60|0.0th), income(55.0|1.5th), Combined Rank(0.0)

Person-B, age(45|0.0th), income(50.0|1.0th), Combined Rank(0.0)

Person-C, age(20|0.0th), income(50.0|1.0th), Combined Rank(0.0)

List of persons sorted by their age in ascending order:

Person-C, age(20|2.5th), income(50.0|1.0th), Combined Rank(0.0)

Person-E, age(30|2.0th), income(85.0|2.5th), Combined Rank(0.0)

Person-B, age(45|1.5th), income(50.0|1.0th), Combined Rank(0.0)

Person-D, age(55|1.0th), income(60.0|2.0th), Combined Rank(0.0)

Person-A, age(60|0.5th), income(55.0|1.5th), Combined Rank(0.0)

List of persons sorted by their combined ranking preference in descending order:

Person-E, age(30|2.0th), income(85.0|2.5th), Combined Rank(4.5)

Person-C, age(20|2.5th), income(50.0|1.0th), Combined Rank(3.5)

Person-D, age(55|1.0th), income(60.0|2.0th), Combined Rank(3)

Person-B, age(45|1.5th), income(50.0|1.0th), Combined Rank(2.5)

Person-A, age(60|0.5th), income(55.0|1.5th), Combined Rank(2.5)

Pham Trung · Accepted Answer · 2015-05-26T04:33:40.863

You can maintain two TreeSet for storing age and income information separately, so you can easily query from those two trees the rank of age and income when sorting.

We can call tailSet(int) method from TreeSet to get the list of numbers greater than or equals a specific number, and in this case, it will be the rank of age/income.

TreeSet ageRank = new TreeSet();
TreeSet incomeRank = new TreeSet();

for(Person p : persons){
   ageRank.add(p.getAge());
   incomeRank.add(p.getIncome());
}

Collections.sort(persons, new Comparator<Person>(){
        @Override
        public int compare(Person p1, Person p2) {              
             int ageRank1 = ageRank.tailSet(p1.getAge()).size();
             int ageRank2 = ageRank.tailSet(p2.getAge()).size();
             int incomeRank1 = incomeRank.tailSet(p1.getIncome()).size();
             int incomeRank2 = incomeRank.tailSet(p2.getIncome()).size();
             //Calculate the combined_rank and return result here. Code omitted  

        }
});

With this approach, one sorting one for loop will be enough for all calculation.

This approach will come in handy if you need to update the list of person regularly, as you don't need to sort age and income and recalculate all the rank again and again when there is an update, you just need to update these two trees.

Notice: in order to use ageRank and incomeRank inside the inner Comparator class used for sorting, they need to be declared as final or as instance variables.

Nice answer and it worked well. I only need to change the `tailset` to `headset` for incomeRank as the condition was lower age and higher income combination is prefered. Many thanks. — Joarder Kamal, May 26 '15 at 05:31
Just as a remark, this solution has the problem of returning incorrect results if the sizes of the sets `ageRank` and `incomeRank` are not same. In that case, one needs to adjust rank values (i.e. ageRank1/2, incomeRank1/2) with the difference between the sizes to get the correct result. — Joarder Kamal, Jun 09 '15 at 02:02
Now we have method references this can be made simpler by using: ``` var ageRank = new TreeSet(Person::getAge) var incomeRank = new TreeSet(Person::getIncome) ``` — dannrob, Jun 16 '23 at 12:33

Efficient implementation of multi-factor weighted sorting in Java

1 Answers1