java - 将 ID 列表与主列表进行比较，并根据找到/未找到创建或删除主列表记录

Question

我有一个 ID 列表:List<Integer> updatedIds .

我有一个主列表(比如说，取自数据库):List<Records> masterList .

我想做以下事情:

1. 对于 updatedIds 中的每个 ID , 检查它是否在 masterList 中.如果不是，则将记录添加到 masterList .
2. 对于 masterList 中的每条记录, 检查它是否在 updatedIds 中.如果不是，则它已过时，因此请将其从 masterList. 中删除

简单的代码如下:

for (Integer updId : updatedIds) {
    boolean hasMapping = false;
    for (Record rec : masterList) {
        if (rec.getId() == updId) { hasMapping = true; break; }
    }
    if (!hasMapping) {
        //TODO add updId to masterList
    }
}
for (Record rec : masterList) {
    boolean isObsolete = true;
    for (Integer updId : updatedIds) {
        if (rec.getId() == updId) { isObsolete = false; break; }
    }
    if (isObsolete) {
        //TODO remove rec from masterList
    }
}

第一个循环处理需求 1，第二个循环处理需求 2。看起来效率很低，我想我可能为此类任务使用了错误的数据结构。

是否有更有效的方法来实现上述算法？

Answer 1

如果您对两个列表进行排序(例如使用 Collections.sort)，updatedIDs 按自然顺序排序，而 masterList 按 ID 排序，您可以设置一个循环来遍历这两个列表。如果记录来自数据库，您可以检索排序的记录，然后跳过该步骤。

Collections.sort(masterList, myComparator);
Collections.sort(updatedIDs);

Iterator m_it = masterList.iterator();
Iterator u_it = updatedIDs.iterator();

// * Some code here to deal with the possibility that either list is empty

Record rec    = m_it.next();
int    u      = u_it.next();
bool   done   = false;

while (! done) {
  if (rec.getID() < u) {
    // rec's ID was missing from updatedIDs
    m_it.remove();

    if (m_it.hasNext()) {
      rec = m_it.next();
    } else {
      done = true;
      // * add u and all subsequent updated IDs to master list
    }
  } else if (rec.getID() > u) {
    // u is new - doesn't occur in masterList
    // * add u to masterList (or probably to a separate list that you
    //   later append to masterList)

    if (u_it.hasNext()) {
      u = u_it.next();
    } else {
      done = true;
      // * remove rec and all remaining records from the master list
    }
  } else {
    // rec's ID matches u: proceed to next pair of items
    bool m_nx = m_it.hasNext(), u_nx = u_it.hasNext();
    if (m_nx && u_nx) {
      rec = m_it.next();
      u = u_it.next();
    } else if ((! m_nx) && (! u_nx)) {
      done = true;
    } else if (m_nx && (! u_nx)) {
      done = true;
      // * remove all subsequent records from the master list
    } else if ((! m_nx) && u_nx) {
      done = true;
      // * add all subsequent integers in updatedIDs to the master list
    }
  }
}