高效地比较两个大型 Java 列表以查找唯一项目-解网

问：

如何有效地比较 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 文件，并将每一行存储为字符串。对于大型文件，这可能不节省内存或可伸缩。
代码使用嵌套循环将一个列表中的每个员工与另一个列表中的每个员工进行比较，这对于大文件来说可能很慢且效率低下。
该代码仅标识一个列表唯一的员工，而不标识另一个列表唯一的员工。它不会识别两个列表中都存在的员工。

我认为我们可以更有效地编写这些代码。我想知道你对此的看法。

Java 列表性能对象比较

假设您可以在内存中容纳所有内容（或者愿意使用一些内存来权衡以提高速度），通常会使用（或者如果您想做更多的事情而不仅仅是检查存在），因为这将允许在恒定时间内进行有效的查找。然后，遍历另一个数据集，对于每个条目，检查查找表中是否有具有相同标识的条目。总而言之，这将花费您线性时间，而不是幼稚的双循环方法。HashSetMapO(1)O(n)O(n²)

1赞 markspace 4/11/2023

像 Mushroomator 一样，我的第一个想法是使用哈希来有效地存储和检索数据。实现了两个集合的非对称集合差异，这就是我认为您希望在任一集合中找到唯一条目的原因。只要您只有“数千”个条目而不是“数百万个”条目，您就应该能够将数据存储在大多数系统的内存中。HashSetremoveAll()

答：

0赞 raiton 4/11/2023 #1

不要使用列表，而是使用具有唯一标识符的地图（例如员工 ID）然后运行第二个列表/映射以查看第一个映射是否包含它。

仅此一项就可以为您节省大量的复杂性/时间

0赞 khachik 4/11/2023 #2

您可以将它们加载到集合中（根据相等标准实现哈希码/等号）并相交/差异。如果内容适合内存，这将起作用。
如果需要可扩展的解决方案，可以在磁盘上对它们进行排序、合并、排序和逐行扫描。
最后，如果您想要一个真正可扩展的解决方案，那么我们 Spark。

0赞 WJS 4/12/2023 #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]

笔记：

我在这里使用了一条记录来促进演示。并且必须在 Employee 类中重写才能正常工作。这也允许您比较对象而不是字段。EqualshashCode
如果允许重复项，则必须使用列表，因为集不允许重复项。
最好先阅读至少一个列表，然后在阅读第二个列表时创建排除列表。这有助于避免列表重复。但是，由于您的列表似乎没有那么大，这应该不是问题。

这是如何做到的。假设已读入。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.
}

上一个：Java 框架，用于在运行时验证值（在运行时标识的类型）和条件（如何比较 2 个值）

下一个：插入排序算法需要多长时间才能对 6 个元素的列表进行排序？

高效地比较两个大型 Java 列表以查找唯一项目

Efficiently comparing two large Java lists to find unique items

评论