java - 在受约束的多对多数据集中有效地查找重复项？

Question

我必须为我们的 webapp 编写一个批量操作版本
允许您从 UI 进行更有限的操作。所需
操作是将对象分配给一个类别。一个类别可以有
多个对象，但一个给定的对象只能属于一个类别。

任务的工作流程是:

1) 使用浏览器，上传如下格式的文件:

# ObjectID, CategoryID
Oid1, Cid1
Oid2, Cid1
Oid3, Cid2
Oid4, Cid2
[etc.]

该文件很可能有几十到几百行，但是
肯定可以有数千行。

在理想的世界中，给定的对象 ID 只会在文件中出现一次
(反射(reflect)一个对象只能归于一个类别)
但由于文件是在我们控制之外创建的，因此无法保证
这实际上是正确的，并且处理必须处理这种可能性。

2)服务器将接收文件，解析它，预处理它
并显示一个页面，例如:

723 objects to be assigned to 126 categories
142 objects not found
 42 categories not found

Do you want to continue?

[Yes]     [No]

3) 如果用户点击 Yes 按钮，服务器将
实际做工作。

由于我不想在步骤 (2) 和 (3) 中解析文件，因为
(2) 的一部分，我需要构建一个可以跨越的容器
请求并保存数据的有用表示，这将使我
轻松提供数据以填充“预览”页面，让我
有效地完成实际工作。 (虽然显然我们有 session ，但我们
通常保持很少的内存 session 状态。)

有一个现有的

assignObjectsToCategory(Set<ObjectId> objectIds, CategoryId categoryId)

通过 UI 完成分配时使用的函数。这是
非常希望批量操作也使用此 API，因为它
除了简单的之外，还做了一堆其他的业务逻辑
分配，我们需要在批量处理时运行相同的业务逻辑
分配完成。

最初，如果文件“非法”指定
给定对象的多个类别 - 可以分配
任意反对文件关联的类别之一
和。

所以我最初认为在步骤 (2) 中我经历了
我将建立并放入跨请求容器的文件 Map<CategoryId, Set<ObjectId>>(特别是 HashMap 用于快速
查找和插入)，然后当我可以做这项工作时
只需在 map 上迭代，并为每个 CategoryId 拉出
关联 Set<ObjectId> 并将它们传递给 assignObjectsToCategory() 。

但是，如何处理重复的 ObjectId 的要求发生了变化。
他们现在将被处理如下:

如果 ObjectId 在文件中多次出现并且
所有时间都与相同的 CategoryId 相关联，分配
该类别的对象。

如果 ObjectId 在文件中多次出现并且
与不同的 CategoryId 相关联，请考虑
一个错误并在“预览”页面上提及它。

这似乎搞乱了我的 Map<CategoryId, Set<ObjectId>> 策略
因为它没有提供检测 ObjectId I 的好方法
刚刚读出的文件已经与一个 CategoryId 相关联。

所以我的问题是如何最有效地检测和跟踪这些
重复的 ObjectId s？

想到的是同时使用“正向”和“反向”映射:

public CrossRequestContainer
{
    ...

    Map<CategoryId, Set<ObjectId>> objectsByCategory;  // HashMap
    Map<ObjectId, List<CategoryId>> categoriesByObject; // HashMap
    Set<ObjectId> illegalDuplicates;

    ...
}

然后当读入每个 (ObjectId, CategoryId) 对时，它会
放入两张 map 。一旦文件被完全读入，我
能做:

for (Map.Entry<ObjectId, List<CategoryId>> entry : categoriesByObject.entrySet()) {
    List<CategoryId> categories = entry.getValue();
    if (categories.size() > 1) {
        ObjectId object = entry.getKey();
        if (!all_categories_are_equal(categories)) {
            illegalDuplicates.add(object);
            // Since this is an "illegal" duplicate I need to remove it
            // from every category that it appeared with in the file.
            for (CategoryId category : categories) {
                objectsByCategory.get(category).remove(object);
            }
        }
    }
}

当这个循环结束时， objectsByCategory 将不再包含任何“非法”
重复， illegalDuplicates 将包含所有“非法”重复
根据需要报告回来。然后我可以迭代 objectsByCategory ，获取每个类别的 Set<ObjectId> ，然后调用 assignObjectsToCategory() 来完成分配。

但是虽然我认为这会奏效，但我担心将数据存储两次，尤其是
当输入文件很大时。而且我还担心我错过了一些东西:效率
这将非常缓慢。

有没有办法做到这一点，不会使用双倍内存但仍然可以快速运行？
我是否错过了即使使用双倍内存仍会运行很多的东西
比我预期的要慢？

Answer 1

鉴于您给出的限制，我没有办法使用更少的内存来做到这一点。

不过，一种可能的优化是仅维护列在多个类别中的对象的类别列表，否则只需将对象映射到类别，即:

Map<CategoryId, Set<ObjectId>> objectsByCategory;  // HashMap
Map<ObjectId, CategoryId> categoryByObject; // HashMap
Map<ObjectId, Set<CategoryId>> illegalDuplicates;  // HashMap

是的，这又添加了另一个容器，但它(希望)只包含几个条目；此外，categoryByObject 映射的内存需求减少(每个条目减少一个列表开销)。

当然，逻辑稍微复杂一些。当最初发现重复项时，应从 categoryByObject 映射中删除该对象，并将其添加到非法重复项映射中。在将任何对象添加到 categoryByObject 映射之前，您需要先检查非法重复映射。

最后，在构建其他两个映射之后在单独的循环中构建 objectsByCategory 映射可能不会影响性能，并且会稍微简化代码。