经常查询的对象列表的最佳数据结构

Question

我有一个对象列表说,列表.Entity类有一个equals方法,在少数属性(业务规则)上区分一个Entity对象与另一个Entity对象.

我们通常在此列表中执行的任务是删除所有重复项,如下所示:

List<Entity> noDuplicates = new ArrayList<Entity>();
for(Entity entity: lstEntities)
{
    int indexOf = noDuplicates.indexOf(entity);
    if(indexOf >= 0 )
    {
            noDuplicates.get(indexOf).merge(entity);
    }
    else
    {
            noDuplicates.add(entity);
     }
}

现在,我一直在观察的问题是,一旦列表中的对象超过10000,代码的这一部分就会大大减慢.我理解arraylist正在进行ao(N)搜索.

有没有更快的选择,使用HashMap不是一个选项,因为实体的唯一性是建立在它的4个属性的基础上,将密钥本身放入地图是很繁琐的？将更快的查询排序设置帮助？

谢谢

Answer 1

现在，我一直观察到的问题是，一旦列表中的对象超过 10000 个，这部分代码的速度就会大大减慢。我知道 arraylist 正在执行 ao(N) 搜索。

你发布的算法实际上比 O(N) 更糟糕

• 迭代输入列表lstEntities- O(N)
• 在此循环中，您调用ArrayList.indexOf(T)它必须再次扫描列表 - O(N)

您的算法实际上是 O(N^2)，因为您可能在循环内扫描列表两次。

听起来你想要做的实际上是两个操作：

1. 从输入中List删除所有重复项
2. 当您发现重复项时，“合并”实体。

您可以通过仅扫描列表一次来完成此操作，而不是在嵌套循环中。我建议分解您的Entity字段，将“标识”实体的字段移至另一种类型，例如ID，或者至少添加一个getID()可以将这些字段分组为单一类型的方法。通过这种方式，您可以轻松地在两种类型之间构建映射，以便能够合并具有“重复”身份的实体。这可能看起来像这样：

Map<ID, Entity> map = new HashMap<ID, Entity>(inputList.size());
for (Entity e : inputList) {
    Entity existing = map.get(e.getID());
    if (existing == null) {
        //not in map, add it
        map.put(e.getID(), e);
    } 
    else {
        existing.merge(e);
    }
}

迭代列表的时间复杂度为 O(n)，同时HashMap.get(K)是一个常数时间操作。