0

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

我有一个主列表（比如说，取自数据库）List<Records> masterList：。

我想做以下事情：

  1. 对于 中的每个 ID updatedIds，检查它是否在 中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。它看起来非常低效，我想我可能为这类任务使用了错误的数据结构。

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

4

3 回答 3

1

你可以HashMap<Integer,Records>代替List<Records>. 你会在哪里得到不断的查找O(1)。HashMap -> Integer - id 和 Records - 对应的记录。

于 2012-10-31T05:08:18.497 回答
1

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

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
    }
  }
}
于 2012-10-31T14:12:18.277 回答
1

使用HashSet. 这会给你一个恒定的时间查找。但是，您的集合中的每个项目都应该是唯一的。那么您也可以将该数字用作哈希码，并且您可以进行O(1)查找，而在 List 中您有O(n)查找时间。

于 2012-10-31T05:03:12.467 回答