对集合性能提示列表进行排序

Question

我有一个包含对的集合列表，我应该保持列表按它的集合对键的字母顺序排序，我当前的解决方案是通过覆盖 add 方法来保持列表排序，就像下面的代码一样。

注意：列表集合对键始终相同

(汽车，1)(汽车，1)

(熊，1)

所以我只需要获取集合的第一对密钥即可使其对列表进行排序

List<Collection<Pair<String, Integer>>> shufflingResult;
public void init() {
shufflingResult = new ArrayList<>() {
public boolean add(Collection<Pair<String, Integer>> c) {
super.add(c);
Collections.sort(shufflingResult, new Comparator<Collection<Pair<String, Integer>>>() {
@Override
public int compare(Collection<Pair<String, Integer>> pairs, Collection<Pair<String, Integer>> t1) {
return pairs.iterator().next().getKey().compareTo(t1.iterator().next().toString());
}
});
return true;
}
};
}

这是完成我正在寻找的最佳性能方法吗？

Answer 1

性能是一件棘手的事情。最好的排序算法在很大程度上取决于数据的数量和类型，以及它的随机程度。有些算法在部分排序数据时是最好的，而另一些算法则适用于真正的随机数据。

一般来说，在确定工作代码性能不足之前，请担心优化。首先让事情顺利进行，然后确定瓶颈在哪里。它可能不是排序，而是别的东西。

Java提供了良好的通用排序算法。您正在使用一个与 Collections.sort() 一起使用的。Java 中没有 SortedList，但 javafx.base 包含一个 SortedList，它包装了提供的 List，并根据实例化时提供的 Comparator 进行排序。这将防止您不必重写 List 实现的基本行为。

虽然您的代码似乎可以工作，但这里有一些建议：

1. pairs.iterator().next().getKey() 如果对为空，则会抛出一个 NPE。
2. pairs.iterator().next().getKey() 如果对为空，则会抛出 NoSuchElementException。
3. pairs.iterator().next().getKey() 将抛出一个 NPE，如果第一个 Pair 有一个空键为空。
4. 所有这些对于 t1 也是如此。
您正在比较pairs.iterator().next().
5. getKey()与t1.iterator().next().toString()。一个是对的字符串表示形式，另一个是对中的键。这是对的吗？

虽然您的代码可以确保这些情况永远不会发生，但有人可能会在以后对其进行修改，从而导致不愉快的意外。您可能希望向 add 方法添加验证，以确保不会发生这些情况。当参数无效时抛出 IllegalArgumentException 通常是很好的做法。

另一个想法：由于您的集合内容始终相同，并且如果没有两个集合具有相同类型的对，您应该能够使用 SortedMap<String、Collection>>>而不是 List。如果您按键进行比较，则此类地图将为您排序。您将使用第一对密钥作为映射/条目密钥put集合。地图的keySet()、values()和entrySet()都将返回按排序顺序迭代的集合。

Answer 2

如果集合已经排序，并且您要做的就是添加。 进行二分搜索，然后每次要插入时都使用list.add(index,element);排序是不好的。 您应该执行一次，然后保持良好的插入顺序。

添加一些代码以显示 bsearch。 因为集合的那个只会返回匹配项。 只需提供列表。 新对象。 以及按所需方式对列表进行排序的比较器。 如果添加许多项目，其中 N> 列表的当前大小可能最好全部添加然后排序。

private static void add(List<ThingObject> l, ThingObject t, Comparator<ThingObject> c) {
if (l != null) {
if (l.size() == 0) {
l.add(t);
} else {
int index = bSearch(l, t, c);
l.add(index, t);
}
}
}
private static int bSearch(List<ThingObject> l, ThingObject t, Comparator<ThingObject> c) {
boolean notFound = true;
int high = l.size() - 1;
int low = 0;
int look = (low + high) / 2;
while (notFound) {
if (c.compare(l.get(look), t) > 0) {
// it's to the left of look
if (look == 0 || c.compare(l.get(look - 1), t) < 0) {
//is it adjacent?
notFound = false;
} else {
//look again.
high = look - 1;
look = (low + high) / 2;
}
} else if (c.compare(l.get(look), t) < 0) {
// it's to the right of look
if (look == l.size() - 1 || c.compare(l.get(look + 1), t) > 0) {
//is it adjacent?
look = look + 1;
notFound = false;
} else {
//look again.
low = look + 1;
look = (low + high) / 2;
}
} else {
notFound = false;
}
}
return look;
}