Effective implementation of multivariate weighted sort in Java
I am looking for an efficient implementation of weighted sort with multiple fields in Java. This question is somewhat similar to How to provide the most relevant results with multiple sorting with a weighting factor and Need help maximizing 3 factors in multiple, similar objects and ordering order . However, I ask for some guidance on effective implementation.
In this example below, the class Person
has fields age
and income
, and I would like to sort the arraylist persons
with lower combination age
and higher income
based on the given preference and in descending order. I gave equal preferences for age
and income
. The sum of preferences must be 1.
As you can see in this naive implementation, there are too many loops to iterate over and ultimately too expensive to run for a very large number of inputs. I've also looked into Guava ComparisonChain and Apache Commons CompareToBuilder , but they don't seem to fulfill my goals.
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.0), income (85.0 | 2.5th), combined rank (0.0)
Person-D, age (55 | 0.0), income (60.0 | 2.0th), combined rank (0.0)
Person-A, age (60 | 0.0), income (55.0 | 1.5), Combined rank (0.0)
Person-B, age (45 | 0.0), income (50.0 | 1.0), Combined rank (0.0)
Person-C, age (20 | 0.0), income (50.0 | 1.0), Combined rank (0.0)
List of faces sorted by age in ascending order:
Person-C, age (20 | 2.5), income (50.0 | 1.0), Combined rank (0.0)
Person-E, Age (30 | 2.0), Income (85.0 | 2.5th), Combo Rank (0.0)
Person-B, age (45 | 1.5), income (50.0 1.0), combined rank (0.0)
Person-D, Age (55 | 1.0), Income (60.0 | 2.0th), Combo Rank (0.0)
Person-A, Age (60 | 0.5), Income (55.0 | 1.5), Combo Rank (0.0)
List of faces sorted by their union in descending order:
Person-E, age (30 | 2.0), income (85.0 | 2.5th), combined rank (4.5)
Person-C, age (20 | 2.5), income (50.0 | 1.0), Combined rank (3.5)
Person-D, age (55 | 1.0), income (60.0 | 2.0th), combined rank (3)
Person-B, age (45 | 1.5), income (50.0 1.0), combined rank (2.5)
Person-A, Age (60 | 0.5), Income (55.0 | 1.5), Combo Rank (2.5)
source to share
You can save two TreeSets to store age and income information separately, so you can easily query the two trees for age rank and income when sorting.
We can call a method tailSet(int)
from the TreeSet to get a list of numbers that are greater than or equal to a specific number, in which case it will be the age / income rank.
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 per loop will be sufficient for all calculations.
This approach will be useful if you need to update the list of people regularly, since you don't need to sort by age and income and recalculate all the rank over and over when there are updates, you just need to update these two trees.
Please note : to use ageRank
and incomeRank
within the inner class Comparator
that is used to sort, they should be declared as final or as an instance variables.
source to share