根据具有公共字段的其他对象列表对对象列表进行排序

Question

我有一个随机的未排序对象ArrayListA，它们具有对象B的公共字段，以及另一个ArrayList的对象B。

我想根据这些公共字段对对象AArrayList中的元素进行排序。

我的代码：

public class Protocol {
@Override
public String toString() {
return "Protocol [referenceName=" + referenceName + ", value=" + value + "]";
}
private String referenceName = "314596";
private String value = "12345";
public Protocol(String referenceName, String value) {
super();
this.referenceName = referenceName;
this.value = value;
}
public String getValue() {
return value;
}
public String getReferenceName() {
return referenceName;
}
// other stuff
}

public class Sensor {
private String referenceName = "314596";
private String value = "12345";
public Sensor(String referenceName, String value) {
this.referenceName = referenceName;
this.value = value;
}
public String getValue() {
return value;
}
public String getReferenceName() {
return referenceName;
}
@Override
public String toString() {
return "Sensor [referenceName=" + referenceName + ", value=" + value + "]";
}
// other stuff
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
public class SortingTest {
public static void main(String[] args) {
Protocol protocol1 = new Protocol("31543678", "09866546534");
Protocol protocol2 = new Protocol("343443678", "09866567897874334");
Protocol protocol3 = new Protocol("41563678", "0663846546534");
Protocol protocol4 = new Protocol("9876543", "009876546546534");
List<Protocol> protocolList = new ArrayList<>();
protocolList.add(protocol4);
protocolList.add(protocol1);
protocolList.add(protocol3);
protocolList.add(protocol2);

for (int i =0; i < protocolList.size(); i++) {
System.out.println(protocolList.get(i));
}
System.out.println("*******************************************************");
Sensor sensor1 = new Sensor("31543678", "09866546534");
Sensor sensor2 = new Sensor("343443678", "09866567897874334");
Sensor sensor3 = new Sensor("41563678", "0663846546534");
Sensor sensor4 = new Sensor("9876543", "009876546546534");

List<Sensor> sensorList = new ArrayList<>();
sensorList.add(sensor1);
sensorList.add(sensor3);
sensorList.add(sensor2);
sensorList.add(sensor4);

List<Sensor> sensorList1 = new ArrayList<>(sensorList);
for(int i =0; i < sensorList.size(); i++) {
System.out.println(sensorList.get(i));
}
System.out.println("*******************************************************");
for (int i = 0; i < sensorList.size(); i++) {
for (int j = 0; j < protocolList.size(); j++) {
if (sensorList.get(i).getReferenceName() == protocolList.get(j).getReferenceName()) {
if (sensorList.get(i).getValue() == protocolList.get(j).getValue()) {
sensorList1.set(j, sensorList.get(i));
}
}
}
}

for (int i = 0; i < sensorList1.size(); i++) {
System.out.println(sensorList1.get(i));
}
}
}

预期输出 ：

Protocol [referenceName=9876543, value=009876546546534]
Protocol [referenceName=31543678, value=09866546534]
Protocol [referenceName=41563678, value=0663846546534]
Protocol [referenceName=343443678, value=09866567897874334]
*******************************************************
Sensor [referenceName=31543678, value=09866546534]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=343443678, value=09866567897874334]
Sensor [referenceName=9876543, value=009876546546534]
*******************************************************
Sensor [referenceName=9876543, value=009876546546534]
Sensor [referenceName=31543678, value=09866546534]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=343443678, value=09866567897874334]

根据公共字段，我想对ObjectBList进行排序，以便序列与ObjectAList匹配。

这个逻辑可以正常工作，但我觉得可能会有一些更快或更简单的方法可以做到这一点。

映射方法的唯一问题是：

Given:
Protocol [referenceName=343443678, value=09866567897874334, random=TEST]
Protocol [referenceName=9876543, value=009876546546534, random=TEST]
Protocol [referenceName=31543678, value=09866546534, random=TEST]
Protocol [referenceName=41563678, value=0663846546534, random=TEST]
Protocol [referenceName=343443678, value=09866567897874334, random=TEST]
Protocol [referenceName=343443678, value=09866567897874334, random=TEST]
Sensor [referenceName=31543678, value=09866546534]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=343443678, value=09866567897874334]
Sensor [referenceName=9876543, value=009876546546534]
Sensor [referenceName=343443678, value=09866567897874334]
Sensor [referenceName=343443678, value=09866567897874334]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=67534567, value=66565656]
expected  output:
Sensor [referenceName=343443678, value=09866567897874334]
Sensor [referenceName=9876543, value=009876546546534]
Sensor [referenceName=31543678, value=09866546534]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=343443678, value=09866567897874334]
Sensor [referenceName=343443678, value=09866567897874334]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=67534567, value=66565656]
Output:
Sensor [referenceName=9876543, value=009876546546534]
Sensor [referenceName=67534567, value=66565656]
Sensor [referenceName=31543678, value=09866546534]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=343443678, value=09866567897874334]
Sensor [referenceName=343443678, value=09866567897874334]
Sensor [referenceName=343443678, value=09866567897874334]

问题是它在最后对相同的对象进行分组，并没有真正保留重复的顺序。

在以下情况下，还有一件事会起作用： 协议假设有 4 个字段，而不是两个引用名称和值以及引用名称 1 和值 1。传感器与前两个相同。 例： 协议(字符串引用名称，字符串值，字符串引用名称1和字符串值1) 和 传感器(字符串引用名称，字符串值)

传感器可以使用 (引用名称和值) 或 (引用名称 1 和值 1) 的组合匹配协议。如果将这两个字段传递给getKey方法，它会起作用吗？传感器和协议之间在(引用名称和值)或(引用名称 1 和值 1)的组合上始终存在匹配，请记住它们中的任何一个都可以为 null。

Answer 1

这个逻辑工作正常，但我觉得可能会有一些更快或更简单的方法可以做到这一点。

您当前的解决方案采用蛮力方法，多次重复检查每个协议的位置(不会更改)，并且时间复杂度为O(n * m)。

我们可以通过索引列表中每个协议的位置来改进它。

更新 - 线性时间解

(涵盖包含最近问题更新中添加的重复项的示例)

此解决方案基于本答案前面提供的最简单的案例解决方案。它将以线性时间运行。

当前解决方案涵盖以下情况：

• 传感器列表可以大于协议列表;
• 两个列表中都可能出现重复项;
• 传感器在协议列表中可能没有匹配对，反之亦然。

生成的传感器列表应包含具有匹配对的所有传感器，根据协议列表中其对的索引进行排序，以及根据其初始顺序在列表末尾分组的匹配对的传感器。

重复情况的假设(基于问题中的示例数据)：

• 让我们考虑有5传感器和2协议具有相同的属性。2传感器将根据2协议的索引进行订购。其余的3传感器将被视为没有匹配对，并将被放置在列表的末尾。

为了满足这些条件，传感器阵列应初始化为两个列表的最大大小。填充数组中的某些位置可以保存必须过滤null值。

以及在最简单的情况下，解决方案位置将存储在地图中。

为了便于处理重复项，我们需要将每个协议的所有位置存储在队列中。所以地图的类型是Map<String,Queue<Integer>>.然后，在将传感器放入阵列时，将从队列中逐个提取所需的位置。如果队列为空或没有匹配的协议(对映射的调用将返回null)，则传感器将被添加到一个单独的列表中，然后附加到结果列表的末尾。

实现：

负责创建地图的方法。

public static Map<String, Queue<Integer>> getPositions(List<Protocol> protocols) {
Map<String, Queue<Integer>> positionByKey = new HashMap<>();
for (int i = 0; i < protocols.size(); i++) {
Protocol next = protocols.get(i);
String key = getKey(next.getReferenceName(), next.getValue());

positionByKey.computeIfAbsent(key, k -> new ArrayDeque<>()).add(i);
}
return positionByKey;
}

main()

public static void main(String[] args) {
List<Protocol> protocols =
List.of(new Protocol("343443678", "09866567897874334"),
new Protocol("9876543", "009876546546534"),
new Protocol("31543678", "09866546534"),
new Protocol("41563678", "0663846546534"),
new Protocol("343443678", "09866567897874334"),
new Protocol("343443678", "09866567897874334"));

List<Sensor> sensors =
List.of(new Sensor("31543678", "09866546534"),
new Sensor("41563678", "0663846546534"),
new Sensor("343443678", "09866567897874334"),
new Sensor("9876543", "009876546546534"),
new Sensor("343443678", "09866567897874334"),
new Sensor("343443678", "09866567897874334"),
new Sensor("41563678", "0663846546534"),
new Sensor("41563678", "0663846546534"),
new Sensor("67534567", "66565656"));

Map<String, Queue<Integer>> positionByKey = getPositions(protocols);
Sensor[] orderedSensors = new Sensor[Math.max(sensors.size(), protocols.size())];
List<Sensor> sensorsWithNoPair = new ArrayList<>();

for (Sensor next : sensors) {
String key = getKey(next.getReferenceName(), next.getValue());
Queue<Integer> positions = positionByKey.get(key);

if (positions == null || positions.isEmpty()) { // matching protocol doesn't exist at all, or we run out of indices in the queue
sensorsWithNoPair.add(next);
continue;
}

int position = positionByKey.get(key).remove();
orderedSensors[position] = next;
}
List<Sensor> result = new ArrayList<>();

for (Sensor next : orderedSensors) {
if (next != null) result.add(next);
}

result.addAll(sensorsWithNoPair);
// printing the result
result.forEach(System.out::println);
}

输出：

Sensor [referenceName=343443678, value=09866567897874334]
Sensor [referenceName=9876543, value=009876546546534]
Sensor [referenceName=31543678, value=09866546534]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=343443678, value=09866567897874334]
Sensor [referenceName=343443678, value=09866567897874334]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=67534567, value=66565656]

在线演示的链接

最简单的情况

让我们从与您提供的数据示例相对应的最简单案例开始：

• Protocol列表和Sensor列表大小相同;
• 每个传感器在协议列表中都有一个匹配的对(按referenceName和value);
• referenceName和value的每种组合都是独一无二的。

在这种情况下，可以在线性时间O(n)内进行排序。

我们需要对协议列表进行一次迭代，以索引每个协议的位置。我们可以将其存储在地图中。

为此，我们需要一个用作键的中间对象。获取密钥的最简单方法是连接referenceName和value。更通用的方法是为此目的使用记录(或类)。现在，我将使用最简单的一个 - 映射Map<String,Integer>，按键索引每个协议。

下一步是根据索引图对传感器进行排序。我们可以创建一个长度等于传感器列表大小的数组，然后通过将每个传感器放置在从地图检索到的位置来迭代传感器列表。

为了将传感器数组转换为列表，我们可以使用 Java 9 中可用的静态方法List.of()，或者Arrays.asList()早期版本。

这就是它的样子：

public static void main(String[] args) {
List<Protocol> protocols =
List.of(new Protocol("343443678", "09866567897874334"),
new Protocol("41563678", "0663846546534"),
new Protocol("31543678", "09866546534"),
new Protocol("9876543", "009876546546534"));
List<Sensor> sensors =
List.of(new Sensor("31543678", "09866546534"),
new Sensor("343443678", "09866567897874334"),
new Sensor("41563678", "0663846546534"),
new Sensor("9876543", "009876546546534"));
Sensor[] orderedSensors = new Sensor[sensors.size()];
Map<String, Integer> positionByKey = new HashMap<>();
for (int i = 0; i < protocols.size(); i++) {
Protocol next = protocols.get(i);
positionByKey.put(getKey(next.getReferenceName(), next.getValue()), i);
}
for (Sensor next: sensors) {
int position = positionByKey.get(getKey(next.getReferenceName(), next.getValue()));
orderedSensors[position] = next;
}

List<Sensor> result = List.of(orderedSensors); // or for Java 8 and earlier Arrays.asList(orderedSensors);
}
public static String getKey(String first, String second) {
return first + ":" + second;
}

一般情况

一般情况解决方案不需要任何假设，即它应该能够处理以下情况：

• 列表的大小可能不相等;
• referenceName和value的组合不保证是唯一的;
• 传感器在协议列表中可能没有匹配对。

整体方法保持不变：我们需要索引每个协议的位置并将其存储在映射中。

但是我们不会直接访问此地图，而是由比较器使用。在此解决方案中，自定义对象将用作键。为了避免覆盖equals和hashCode的必要性，它被实现为Java 16record：

public record Key(String first, String second) {

public Key(Sensor item) {
this(item.getReferenceName(), item.getValue());
}

public Key(Protocol item) {
this(item.getReferenceName(), item.getValue());
}
}

要创建一个比较器，首先我们必须构建一个映射，然后我们可以利用静态方法Comparator.comparingInt：

public static Comparator<Sensor> compareByKey(List<Protocol> base) {

Map<Key, Integer> orderByKey = new HashMap<>();

for (int i = 0; i < base.size(); i++) {
Protocol next = base.get(i);
orderByKey.put(new Key(next), i);
}

return Comparator.comparingInt((Sensor item) ->
orderByKey.getOrDefault(new Key(item), -1)); // sensors that have no matching pair in the list of protocols will be grouped at the beginning of the resulting list
}

主方法只需要一行即可完成排序，因为比较器会完成所有繁重的工作。因为现在我们正在处理排序，所以时间复杂度将是线性对数的。

public static void main(String[] args) {
List<Protocol> protocols = // initializing the list of protocols
List<Sensor> sensors =     // initializing the list of sensors

List<Sensor> orderedSensors = new ArrayList<>(sensors); // making a defensive copy, omit this line it's not required to preserve the unsorted list of sensors
orderedSensors.sort(compareByKey(protocols);
}

注意：此方法可以通过使用泛型类型参数进一步推广，以便可以将其应用于任何一对对象。这需要使Key类成为通用的，并且应该为负责生成比较器以便能够从任意对象中提取所需属性的方法提供几个函数。

Answer 2

关键是从protocolList获取订单策略

1.为协议实现 equals 和 hashCode，例如，

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Protocol)) return false;
Protocol protocol = (Protocol) o;
return Objects.equals(getReferenceName(), protocol.getReferenceName()) && Objects.equals(getValue(), protocol.getValue());
}
@Override
public int hashCode() {
return Objects.hash(getReferenceName(), getValue());
}

2.使用自定义比较器对传感器列表进行排序

sensorList.sort(Comparator.comparingInt(one -> protocolList.indexOf(new Protocol(one.getReferenceName(), one.getValue()))));

P.S.hashCode() 是可选的，如果你不把协议放入哈希集合中