java - Java多因子加权排序的高效实现

Question

我正在寻找一种在 Java 中使用多个字段进行加权排序的有效实现。这个问题有点类似于 How to provide most relevant results with Multiple Factor Weighted Sorting和 Need help maximizing 3 factors in multiple, similar objects and ordering appropriately .但是，我要求提供一些有关有效实现的指南。

在下面的例子中，Person 类有 age 和 income 字段，我想对数组列表 persons 进行排序 具有较低的 age 和较高的 income 组合，基于给定的偏好并按降序排列。我为 age 和 income 提供了相同的偏好。偏好的总和应为 1。

正如您在这个简单的实现中看到的那样，有太多循环需要迭代，最终运行大量输入的成本太高。我还探索了 Guava 的 ComparisonChain 和 Apache Commons CompareToBuilder，但它们似乎没有实现我的目标。

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+")");
}
}

控制台输出

按收入降序排列的人员名单:

人-E，年龄(30|0.0)，收入(85.0|2.5)，综合排名(0.0)

D人，年龄(55|0.0)，收入(60.0|2.0)，综合排名(0.0)

人-A，年龄(60|0.0)，收入(55.0|1.5)，综合排名(0.0)

B人，年龄(45|0.0)，收入(50.0|1.0)，综合排名(0.0)

Person-C，年龄(20|0.0th)，收入(50.0|1.0th)，综合排名(0.0)

按年龄升序排列的人员列表:

Person-C，年龄(20|2.5th)，收入(50.0|1.0th)，综合排名(0.0)

人-E，年龄(30|2.0)，收入(85.0|2.5)，综合排名(0.0)

人-B，年龄(45|1.5th)，收入(50.0|1.0th)，综合排名(0.0)

D人，年龄(55|1.0)，收入(60.0|2.0)，综合排名(0.0)

人-A，年龄(60|0.5th)，收入(55.0|1.5th)，综合排名(0.0)

按组合排名偏好降序排列的人员列表:

人-E，年龄(30|2.0)，收入(85.0|2.5)，综合排名(4.5)

Person-C，年龄(20|2.5th)，收入(50.0|1.0th)，综合排名(3.5)

D人，年龄(55|1.0)，收入(60.0|2.0)，综合排名(3)

B人，年龄(45|1.5th)，收入(50.0|1.0th)，综合排名(2.5)

人-A，年龄(60|0.5th)，收入(55.0|1.5th)，综合排名(2.5)

Answer 1

你可以维护两个TreeSet用于分别存储年龄和收入信息，因此您可以在排序时轻松地从这两棵树中查询年龄和收入的排名。

我们可以从 TreeSet 中调用 tailSet(int) 方法来获取大于或等于特定数字的数字列表，在这种情况下，它将是年龄/收入的排名。

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  

        }
});

采用这种方法，一个排序一个for循环就足以完成所有计算。

如果您需要定期更新人员名单，这种方法会派上用场，因为您不需要对年龄和收入进行排序，也不需要在出现变化时一次又一次地重新计算所有排名更新，你只需要更新这两棵树。

注意:为了在用于排序的内部Comparator类中使用ageRank和incomeRank，他们需要声明为最终变量或实例变量。