java - 对于下面描述的要求，从性能的角度来看，根据业务逻辑迭代列表的最佳方法是什么

Question

我有一个实体列表。这些是来自数据库的响应。我还有另一个很长的 list 。在实体列表中，每个实体对象都有一个名为id的字段。这些 id 将始终按升序排列。我需要按照长列表给出的顺序遍历实体列表。另外，我需要维护另一个响应对象列表，该列表的字段比实体列表中的字段多一些。我也不能使用 transient 。下面的代码将为您提供一个想法。

public List<ResponseObject> convert(List<EntityObject> entityList, List<Long> orderedIdList) {

    List<ResponseObject> responseList = new ArrayList<>();
    for (EntityObject object : entityList) {
        ResponseObject responseObject = new ResponseObject();
        responseObject.someSettermethod(object.someGettermethod());
        /* other setters in responseObject which are not present in the entity object */
        responseObject.otherSetters("some value"); 
        responseList.add(responseObject);
    };
    return sortInOrder(responseList, orderedIdList);
}

private List<ResponseObject> sortInOrder(List<ResponseObject> responseList,List<Long> orderedIdList) {
    List<ResponseObject> finalList = new ArrayList<>();
     for(Long id : orderedIdList){
         for(ResponseObject response : responseList){
             if(response.getId().equals(id)){
                 finalList.add(response);
             }
         }
     }
    return finalList;
}

这就是目前的实现方式。我想知道是否有更好的方法来增强性能以达到相同的输出。

Answer 1

sortInOrder 方法的执行速度比 O(N^2) 更快:

假设 Id 是唯一的(请告诉我这是否是错误的假设):

想法:

1. 通过迭代响应列表 O(n) 创建 Id 到 responseObject 的映射。
2. 迭代orderedIdList并检查map中的id，如果id存在，则将值添加到响应对象。

private List<ResponseObject> sortInOrder(List<ResponseObject> responseList,List<Long> orderedIdList) {
    List<ResponseObject> finalList = new ArrayList<>();
    Map<Long, ResponseObject> map = responseList.stream().collect(Collectors.toMap(ResponseObject::getId, respObj -> respObj));
    for(Long id : orderedList) {
      if(map.containsKey(id)) {
         finalList.add(map.get(id));
      }
    }
    return finalList;
}