java - 如何保持列表不 fragment 化(阅读解释)

Question

我有以下问题(针对示例进行了简化)

我有 items 由其 id 标识

class Item {
   private int id;
   public int getId(){
      return id;
   }
}

我想将它们放在一个类中(我们将其命名为 ItemGroup)，并满足以下条件:

• ItemGroup.getItems()应该返回 List<Item> (不需要按项目 ID 排序的列表)
• 每次我向 ItemGroup 添加新项目时它应该只维护具有更高和连续 ID 的项目。一些例子可以更好地解释它:
  • 现有项目= [5,6]，itemsToAdd=[7,8]，结果=[5,6,7,8]
  • 现有项目= [5,6]，itemsToAdd=[8,9]，结果=[8,9]
  • 现有项目= [5,6]，itemsToAdd=[3,4]，结果=[3,4,5,6]
  • 现有项目= [5,6]，itemsToAdd=[1,2]，结果=[5,6]

目标是实现一个聊天，其中消息以小数据包的形式从服务器恢复，主要要求是线程拥有最后一条消息而没有 fragment 线程(丢失消息)。

例如，当客户端的版本为 5 而服务器的版本为 1000 时，就会出现主要问题。客户端恢复最后 10 条消息，找到 ID 为 (90-100) 的项目。在这种情况下，我想要丢弃旧消息，允许用户向上滚动，在需要时恢复以前的消息。

我怎样才能有效地实现它？我考虑过的选项是:

1. 使用 List<Items> ，每次添加新项目(或项目组)时运行 Collections.sort() 。然后递减地迭代列表，当我检测到 id 中的跳跃时，丢弃剩余的项目。
2. 使用 TreeSet，在集合修改后以相同的方式对列表进行 fragment 整理。方法getItems()返回 new ArrayList<Item>(treeSet)
3. 使用 List ，每次需要插入一个项目时，用二进制搜索查找正确的位置，在那里插入项目，然后对列表进行 fragment 整理。返回 getItems() 中未修改的列表方法
4. 更多解决方案？

谢谢

Answer 1

我不确定您的 ID 是否是唯一的，根据我假设的示例。我还假设插入列表和主列表最初都有相应的元素 如果是这样，算法将很简单:

1. 在插入之前对两个列表进行排序
2. 比较插入列表中最低(第一个)元素和主列表中最高(最后一个)元素，如果它们相差 1 - 插入末尾，如果它们相差更多 - 替换主列表，返回
3. 比较插入列表中的最高元素和主列表中的最低元素，如果它们相差 1 - 插入到开头，如果它们相差超过 1 - 丢弃插入列表。

该算法具有 O(n) 的最佳性能(值比较为 O(1)，元素插入为 O(n))，只要没有人弄乱列表并且列表始终已排序，这将始终实现。