0

IDのリストがあります：List<Integer> updatedIds。

私はマスターリストを持っています（たとえば、DBから取得）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番目のループは要件2を処理します。これは非常に非効率に見え、この種のタスクに間違ったデータ構造を使用している可能性があります。

上記のアルゴリズムを実装するより効率的な方法はありますか？

4

3 に答える 3

1

を使用しますHashSet。それはあなたに一定時間のルックアップを与えるでしょう。ただし、セット内の各アイテムは一意である必要があります。次に、その番号をハッシュコードとして使用することもでき、O(1)ルックアップがありますが、リストではO(n)ルックアップ時間があります。

于 2012-10-31T05:03:12.467 に答える
1

HashMap<Integer,Records>の代わりにできますList<Records>。あなたが一定のルックアップを得るところO(1)。HashMap->Integer-idおよびRecords-対応するレコード。

于 2012-10-31T05:08:18.497 に答える
1

両方のリストを並べ替える場合（たとえば、Collections.sortを使用）、updatedIDを自然な順序で並べ替え、masterListをIDで並べ替える場合は、両方を通過する単一のループを設定できます。レコードがDBからのものである場合は、ソートされた順序でレコードを取得し、そのステップをスキップすることができます。

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 に答える