3

我需要一种基于第三个对象的属性对对象集合进行排序的方法。我将尝试用一个简化的案例来描述它。

假设我们有一个 Person 对象

class Person {
    String firstName;
    String lastName;
    ...
}

我们想对与某个人相关的 Persons 集合进行排序。例如:John Doe 是我们想要找到的人,或者如果我们找不到,我们希望最“相似”的人位于排序集合的顶部。

相似性定义如下:如果只有名字匹配,那么它比只有姓氏匹配时更好。当然,如果两者都匹配,那就是宾果游戏。

我想出了一个解决方案,但我不确定它是否完美无缺。这个想法是使用如下的比较器:

public static class PersonComparator implements Comparator<Person> {
    String firstName;
    String lastName;

    public PersonComparator(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }

    @Override
    public int compare(Person p1, Person p2) {
        int p1Match = calcMatch(p1);
        int p2Match = calcMatch(p2);

        int result = p1Match - p2Match;
        if (result == 0) {
            //not very sure about this part
            result = p1.firstName.compareTo(p2.firstName);
            if (result == 0) {
                result = p1.lastName.compareTo(p2.lastName);
            }
        }
        return result;
    }

    public int calcMatch(Person p) {
        StringBuilder builder = new StringBuilder();
        builder.append(firstName.equals(p.firstName) ? "1" : "0");
        builder.append(lastName.equals(p.lastName) ? "1" : "0");
        return Integer.parseInt(builder.toString(), 2);
    }
}

因此,如果第一个人的名字匹配而姓氏不匹配,他会将二进制匹配“10”转换为整数 2,而如果第二个人的名字和姓氏都匹配,则二进制值将“11”转换为 3 . compareTo 然后将简单地返回 2 - 3 = -1 表示一个“小于”然后是两个。

但是,如果两个人的名字和姓氏都与我们正在寻找的不匹配,该怎么办。匹配的“二进制值”将是相同的,返回 0 将表示两个人彼此相等(例如,至少对于 TreeSet)。当在 TreeSet 中使用这样的比较器时,两个人中只有一个人会在结果集中持续存在。

不是期望的行为,因此,如果两人的结果相同,我会根据两人的字段比较来计算 compareTo 返回的值。

运行以下简单的测试用例显示了一个示例:

public static void main(String[] args) {
    List<Person> persons = new ArrayList<Person>();
    persons.add(new Person("Pietje", "Puk"));
    persons.add(new Person("Jan", "Jansen"));
    persons.add(new Person("John", "Doe")); 

    Comparator<Person> comparator = new PersonComparator("John", "Doe")
    int firstCompare = comparator.compare(persons.get(0), persons.get(1));
    int secondCompare = comparator.compare(persons.get(1), persons.get(2));
    int thirdCompare = comparator.compare(persons.get(0), persons.get(2));
    System.out.println(firstCompare + " vs " + secondCompare + " vs " + thirdCompare);

    TreeSet<Person> personsSet = new TreeSet<Person>(comparator);
    personsSet.addAll(persons);
    personsSet.add(new Person("Baby", "Doe"));
    personsSet.add(new Person("John", "Roe"));
    personsSet.add(new Person("Jane", "Doe"));

    int i = 0;
    for (Person person : personsSet) {
        System.out.println(i++ + ") " + person + " [" + comparator.calcMatch(person) + "]");
    }
}

执行上面的代码会导致:

6 对 -3 对 -3

0) 扬·詹森 [0]

1) 皮耶普克 [0]

2) 母鹿宝宝 [1]

3) 简·多伊 [1]

4) 约翰·罗 [2]

5) 约翰·多伊 [3]

第一次比较基于名字(Pietje Puk vs Jan Jansen),结果为 6。第二次比较基于姓氏与枢轴(Jan Jansen vs John Doe)比较,结果为 -3,而最后一个是也基于姓氏与枢轴相比(Pietje Puk vs John Doe),结果也为 -3。

正如代码中所述,我不确定compareTo 中问题的解决方案,其中两个字段匹配相似,但具有不同的值。由于“匹配”代码始终计算 0 到 3 之间的值,因此“字段比较”可以具有更高的值,我不确定“混合”这些数字是否是个好主意。

有没有人遇到过类似的问题,或者可以确认我的解决方案符合合同并且没有缺陷?理想情况下,我希望有一个 TreeSet 可以使用的比较器,因此如果人员真的不相等,compareTo 应该只返回 0。

我想到的另一个解决方案是将“pivot”作为“普通”“Person”对象放在树集中,并根据提供给 compareTo 方法的两个人的字段使用简单的比较器。对集合进行排序后,我可以搜索枢轴对象,然后我知道它附近的元素具有最高匹配度。然而,这个解决方案听起来并不优雅,并且可能并不总是适用。

4

5 回答 5

2

如果您将匹配的两个名字和两个姓氏中的每一个都作为独立的布尔值,则给出四个变量,具有 2 4 = 16 个组合。您可以在比较方法中检查这 16 种组合中的每一种。

public int compare(Person p1, Person p2) {
    boolean f1 = p1.firstName.equals(firstName));
    boolean f2 = p2.firstName.equals(firstName));
    boolean l1 = p1.lastName .equals(lastName));
    boolean l2 = p2.firstName.equals(lastName));

    if ( f1 &&  f2 &&  l1 &&  l2) { return  0; }
    if ( f1 &&  f2 &&  l1 && !l2) { return +1; }
    if ( f1 &&  f2 && !l1 &&  l2) { return -1; }
    if ( f1 &&  f2 && !l1 && !l2) { return p1.lastName.compareTo(p2.lastName); }
    if ( f1 && !f2 &&  l1 &&  l2) { return +1; }
    if ( f1 && !f2 &&  l1 && !l2) { return +1; }
    if ( f1 && !f2 && !l1 &&  l2) { return +1; }
    if ( f1 && !f2 && !l1 && !l2) { return +1; }
    if (!f1 &&  f2 &&  l1 &&  l2) { return -1; }
    if (!f1 &&  f2 &&  l1 && !l2) { return -1; }
    if (!f1 &&  f2 && !l1 &&  l2) { return -1; }
    if (!f1 &&  f2 && !l1 && !l2) { return -1; }
    if (!f1 && !f2 &&  l1 &&  l2) { return p1.firstName.compareTo(p2.firstName); }
    if (!f1 && !f2 &&  l1 && !l2) { return +1; }
    if (!f1 && !f2 && !l1 &&  l2) { return -1; }
    if (!f1 && !f2 && !l1 && !l2) { return p1.firstName.compareTo(p2.firstName); }
}

如果您随后结合一些类似的情况,您可以将其简化为一组更有意义的检查:

public int compare(Person p1, Person p2) {
    boolean f1 = p1.firstName.equals(firstName));
    boolean f2 = p2.firstName.equals(firstName));
    boolean l1 = p1.lastName .equals(lastName));
    boolean l2 = p2.firstName.equals(lastName));

    // Same names.
    if (f1 && f2 && l1 && l2) { return 0; }

    // One name matches and the other doesn't.
    if ( f1 && !f2) { return +1; }
    if (!f1 &&  f2) { return -1; }
    if ( l1 && !l2) { return +1; }
    if (!l1 &&  l2) { return -1; }

    // Both match first or both match last.
    if ( f1 &&  f2) { return p1.lastName .compareTo(p2.lastName);  }
    if ( l1 &&  l2) { return p1.firstName.compareTo(p2.firstName); }

    // Completely different names. Sort based on first name.
    return p1.firstName.compareTo(p2.firstName);
}
于 2013-08-16T21:55:38.847 回答
1

这种方法听起来是对的,但有两个警告。

  1. 为什么要使用 StringBuilder 和 parse 来计算匹配,而只需添加 0 和 1 就可以了?
  2. 如果两个不同的 Person 实例具有相同的名字和姓氏怎么办?您是否希望它们被您的比较器视为相等?如果不是,请考虑比较它们System.identityHashCode(),除非您拥有大量实例和巨大的内存,否则它们总是会有所不同。如果您想绝对确定,请使用 Guava 的Ordering.arbitrary()比较器来比较它们:这将保证两个人只有当他们是同一个实例时才相等。
于 2013-08-16T21:47:55.247 回答
1

在我看来,您不想对Persons 进行排序,而是对它们进行优先排序。

我建议把你Person的 s 放在一个PriorityQueue. 使用你Comparator那里,你应该能够得到你想要的结果。但是,您可能需要使用负值,因为队列的头部将是相对于指定排序具有最少元素的元素。

于 2013-08-16T21:49:37.660 回答
1

这种方法似乎很合理;这PersonComparator是通过“匹配分数”比较人,并且按字典顺序比较具有相同分数的人。从方法返回的值的大小compare无关紧要;只有标志可以。

但是,结果与首先按名字然后按姓氏与普通比较器进行比较并解决搜索算法中的其他要求(如获得最早的匹配)没有什么不同,就像您在最后一段中建议的那样。对我来说,它看起来更简单、更优雅,如果你必须在同一个集合中搜索多个人,它也会更有效。如果您打算使用TreeMap您已经有方法来获取具有与所需级别匹配的值的子图。

于 2013-08-16T22:26:11.053 回答
1

您的问题归结为:比较器是否会产生一个完全的排序(在精确的数学意义上)?

我相信确实如此。您首先将所有值映射到 0 到 3 之间的范围内。这是您要排序的最重要属性,因此您首先对其进行测试。现在,如果它们不同,则使用整数差异来指示“完全”好的排序。如果它们相同,则首先按名字排序,然后按姓氏排序。字典顺序当然是完全的。所以你又好了。

正如在其他答案中所说,其他一切都不重要。您不必担心比较器返回的 int 的实际大小。

非常重要但您没有在这里展示的是,当且仅当 compareTo 返回 0 时,您对 Person 的 equals 方法应该返回 true。如果两个 Person 具有相同的名字和姓氏,您的 compareTo 方法只能返回 0。因此,如果这是真的,那么 equals 也应该这样做。检查那个。好的。然后是另一个方向。检查没有其他情况下您的 equals 返回 0。完成。

最后,如果您不相信自己的推理,则存在一种相当好的测试方法。创建一个随机人员生成器,生成人员对和三人组,并测试数百万组合的总排序规则。即如果 a < b 则 !(b < a) 等等。如果我们确实遗漏了一些东西,那么这个设置的几次运行可能会指出我们推理中的缺陷。

于 2013-08-17T06:11:22.037 回答