有效地比较两个大的Java列表以找到唯一的项

Question

如何有效地比较Java中的两个大对象列表，并识别一个列表中存在而另一个列表中不存在的项?

的例子:

假设我有两个大型CSV文件，其中包含数千名员工的数据，其中包含姓名、部门和工资列。我需要比较这两个文件，并根据员工的姓名和部门，识别在一个文件中出现而在另一个文件中没有出现的员工。

public static void compareCSVFiles(String file1, String file2) {
List<Employee> list1 = readCSVFile(file1);
List<Employee> list2 = readCSVFile(file2);
List<Employee> uniqueTo1 = new ArrayList<>();
List<Employee> uniqueTo2 = new ArrayList<>();
for (Employee emp1 : list1) {
boolean found = false;
for (Employee emp2 : list2) {
if (emp1.getName().equals(emp2.getName()) && emp1.getDepartment().equals(emp2.getDepartment())) {
found = true;
break;
}
}
if (!found) {
uniqueTo1.add(emp1);
}
}
for (Employee emp2 : list2) {
boolean found = false;
for (Employee emp1 : list1) {
if (emp2.getName().equals(emp1.getName()) && emp2.getDepartment().equals(emp1.getDepartment())) {
found = true;
break;
}
}
if (!found) {
uniqueTo2.add(emp2);
}
}
System.out.println("Employees unique to " + file1 + ":");
for (Employee emp : uniqueTo1) {
System.out.println(emp.getName() + " (" + emp.getDepartment() + ")");
}
System.out.println("Employees unique to " + file2 + ":");
for (Employee emp : uniqueTo2) {
System.out.println(emp.getName() + " (" + emp.getDepartment() + ")");
}
}

• 代码逐行读取CSV文件，并将每行存储为字符串。对于大文件，这可能不具有内存效率或可伸缩性。
• 代码使用嵌套循环将一个列表中的每个员工与另一个列表中的每个员工进行比较，这对于大文件来说可能很慢且效率低下。
• 代码只标识一个列表中唯一的员工，而不标识另一个列表。它不识别出现在两个列表中的员工。

我认为我们可以更有效地编写这些代码。我想听听你对这件事的看法。

Answer 1

不使用列表，而是使用具有唯一标识符(例如员工ID)的映射然后运行第二个list/map，看看第一个map是否包含它。

这将为您节省大量的复杂性/时间

Answer 2

您可以将它们加载到集合中(基于相等标准实现hashcode/equals)和intersect/diff。如果内容适合内存，这将有效。
如果你想要一个可扩展的解决方案，你可以在磁盘上对它们进行排序，合并排序和逐行扫描。
最后，如果你想要一个真正可扩展的解决方案，那么我们使用Spark。

Answer 3

这是一种方法。开销不是那么大，因为移除工作是由散列的集合完成的。

List<Employee> list1 = List.of(
new Employee("John", "Fiance"), 
new Employee("Mary", "Engineering"), 
new Employee("John", "Engineering"), 
new Employee("Linda", "Engineering"), 
new Employee("Alice", "Personel")); 
List<Employee> list2 = List.of(
new Employee("John", "Personel"), 
new Employee("Mary", "Fiance"), 
new Employee("John", "Engineering"), 
new Employee("Linda", "Engineering"), 
new Employee("Alice", "Personel")); 
Set<Employee> uniqueTo1 = new HashSet<>(list1);
Set<Employee> uniqueTo2 = new HashSet<>(list2);
uniqueTo1.removeAll(list2);
uniqueTo2.removeAll(list1);
uniqueTo1.forEach(System.out::println);
System.out.println();
uniqueTo2.forEach(System.out::println);

打印

Employee[getName=Mary, getDepartment=Engineering]
Employee[getName=John, getDepartment=Fiance]
Employee[getName=Mary, getDepartment=Fiance]
Employee[getName=John, getDepartment=Personel]

指出:

• 我在这里使用了一个记录来方便演示。Equals和hashCode必须在Employee类中重写才能正常工作。这也允许你比较对象而不是字段。

• 如果你允许重复，你必须使用列表，因为集合不允许重复条目。

• 最好先读取至少一个列表，然后在读取第二个列表时创建排除列表。这有助于避免列表重复。但由于你的清单似乎不是那么大，这应该不是问题。

这是如何做到的。假定list1已读入。

Employee emp = null;
List<Employee> list2 = new ArrayList<>();
List<Employee> uniqueTo1 = list1; // could also make a copy
while (reading next of what would be list2) {
list2.add(emp);
if (!list1.contains(emp)) {
uniqueTo2.add(emp); // if not in list1, must be unique to list2
else {
list1.remove(emp); //  if it is in list1 it can't be unique so remove it.
}                      //  list1 is now becoming unique to list1.
}