从另一个列表更新一个列表

Question

我有一个本地用户列表，需要定期从远程用户列表中更新。基本上：

1. 如果远程用户已经存在于本地，则更新其字段。
2. 如果远程用户在本地不存在，则添加该用户。
3. 如果本地用户不在远程列表中，则停用或删除。
4. 如果本地用户也出现在远程列表中，则更新其字段。 (与1相同)

例如， 远程列表：User(1, true), User(2, true), User(4, true), User(5, true)

本地列表：User(1, true), User(2, false), User(3, true), User(6, true)

新的本地列表：User(1, true), User(2, true), User(3, false), User(4, true), User(5, true), User(6, false),

只是简单地同步本地列表。是否有比以下纯Java更好的方法？看着自己的代码感觉很恶心。

public class User {
    Integer id;
    String email;
    boolean active;

    //Getters and Setters.......

    public User(Integer id, String email, boolean active) {
        this.id = id;
        this.email = email;
        this.active = active;
    }

    @Override 
    public boolean equals(Object other) {
        boolean result = false;
        if (other instanceof User) {
            User that = (User) other;
            result = (this.getId() == that.getId());
        }
        return result;
    }

}




public static void main(String[] args) {

    //From 3rd party
    List<User> remoteUsers = getRemoteUsers();

    //From Local store
    List<User> localUsers =getLocalUsers();     

    for (User remoteUser : remoteUsers) {
        boolean found = false;
        for (User localUser : localUsers) {
            if (remoteUser.equals(localUser)) {
                found = true;
                localUser.setActive(remoteUser.isActive());
                localUser.setEmail(remoteUser.getEmail());
                //update
            } 
            break;
        }
        if (!found) {
            User user = new User(remoteUser.getId(), remoteUser.getEmail(), remoteUser.isActive());
            //Save
        }
    }

    for(User localUser : localUsers ) {
        boolean found = false;
        for(User remoteUser : remoteUsers) {
            if(localUser.equals(remoteUser)) {
                found = true;
                localUser.setActive(remoteUser.isActive());
                localUser.setEmail(remoteUser.getEmail());
                //Update
            }
            break;
        }
        if(!found) {
            localUser.setActive(false);
            // Deactivate
        }
    }
}

- Langali

---

1和4只需要做一次，它们是同一件事情。 - Lombo

你可以提取一些方法（例如在User类中的update(User user)，它会将user的字段设置为this）。你也可以在for-comprehensions中使用java.util.Collections.binarySearch(list, user)。 - BorisOkunskiy

Answer 1

最好的方法是切换到不同的数据结构。一个 Map<Integer, User> 是最好的选择，因为用户有唯一标识ID。你可以选择使用 HashMap (基本操作的期望时间复杂度为 O(1)) 或者 TreeMap (期望时间复杂度为 O(log N)) 作为 Map 的实现。

重要提示: 如果你在覆盖 equals(Object) 方法时没有同时覆盖 hashCode() 方法，这是很危险的！你应该养成不覆盖它们中的任何一个或者同时覆盖它们两个的习惯！（参见：Java中覆盖equals和hashCode方法）

所以，假设你有 Map<Integer, User> remoteUsers 和 Map<Integer, User> localUsers。

1.) 如果远程用户已经存在于本地，更新其字段。
4.) 如果一个本地用户也出现在远程列表中，则更新其字段。 （和1一样）
2.) 如果远程用户不存在于本地，请添加该用户。

查找一个来自 remoteUsers 的 User 是否在 localUsers 中，可以通过简单的 containsKey 和 get 方法在 O(1) 或者 O(log N) 时间复杂度内完成。

for (int id : remoteUsers.keys()) {
   User local;
   if (localUsers.containsKey(id)) {
      local = localUsers.get(id);
   else {
      localUsers.put(id, local = new User(id));
   }
   local.updateFrom(remoteUsers.get(id));
}

3.) 如果本地用户在远程列表中没有出现，就停用或删除。

以下解决方案展示了这些更高级的数据结构可以有多么强大：

Set<Integer> toDeactivate = new TreeSet<Integer>();
toDeactivate.addAll(localUsers.keySet());
toDeactivate.removeAll(remoteUsers.keySet());

for (int id : toDeactivate) {
   User local = localUsers.get(id);
   local.deactivate();
   localUsers.remove(id);
}

此外，如果您被限制使用 List<User>，您仍然可以使用 Map<Integer, User> 作为中间数据结构进行处理（基本上将 List<User> 转换为 Map<Integer, User> 然后再转回 List<User>）。这样做的速度仍然会更快，因为它是 O(N log N) 或 O(N)，相对于您现在拥有的 O(N^2)。

如果您坚持只使用列表，则可能需要考虑将其排序为 Collections.sort 的列表，以便您可以在其上执行 Collections.binarySearch。您需要提供一个 Comparator<User>，或使 User 实现 Comparable<User>，按 id 自然排序。这也将是 O(N log N)。

- polygenelubricants

---

дёҚиғҪжҖ»жҳҜеңЁListе’ҢSetд№Ӣй—ҙеҲҮжҚўпјҢиҝҷеҸ–еҶідәҺйўҶеҹҹжЁЎеһӢгҖӮ - BorisOkunskiy

你仍然可以使用 Set 作为中介。它仍然更快，因为它是 O(N) 或 O(N log N)，而不是 O(N^2)。 - polygenelubricants

请看上面的代码行：local = localUsers.get(remote);list.get只接受整数索引而不是对象。 - Langali

@Langali，那段代码是针对localUsers和remoteUsers为Set<User>而不是List<User>的情况。请仔细阅读整个答案：如果可能的话，我建议切换数据结构或使用中间件。 - polygenelubricants

好的，我意识到Set没有get，所以我改用了Map，这样更有意义。 - polygenelubricants

Answer 2

你可以使用 List.indexOf() 代替对列表的迭代：

for (User remoteUser : remoteUsers) {
    int index = localUsers.indexOf(remoteUser);
    if (index >= 0) {
        User localUser = localUsers.get(index);
        localUser.setActive(remoteUser.isActive());
        localUser.setEmail(remoteUser.getEmail());
        //update
    } else {
        User user = new User(remoteUser.getId(), remoteUser.getEmail(), remoteUser.isActive());
        //Save
    }
}

- Péter Török

---

但是如果没有列表推导或迭代，我该如何获取更新参数呢？ - Langali

本地用户变量未定义？ - Langali

Answer 3

Langali:

假设Id唯一标识一个用户，我有几个建议给你：

• 创建一个User.Key类（作为User类的内部类），并将id字段移动到其中。将其设置为final。在User.Key类上重写hashcode和equals方法，只使用id：

    public User {
       private final Key key;
       ... 其他变量
 public static class Key {
       private final int id;
          public Key(final int id) {
}
          // hashcode（可以是id）
          // equals（如你已经实现的那样）
       }
    }

• 创建一个map来保存你的用户。

  Map<User.Key, User>

  ；
• 使用这个map来保存你的用户，然后使用get和containsKey方法来查找你需要的内容。

List.contains的问题在于，在ArrayList上，它会对列表内容进行完整扫描。如果你对第二个列表的每个项目都这样做，那么你的性能就是O(n^2)，这意味着当你增加项目时，运行方法所需的时间将乘以四倍。而HashMap的性能为O(log(n))，这意味着如果你有1000个对象，运行所需的时间只会慢10倍（大约）。

- Ravi Wallau