在给定时间内找到所有活着的人的快速算法？

Question

假设您有以下内容：

class Person {
  LocalDate bornOn;
  LocalDate diedOn;
}

假设您有一堆“Person”实例，可以按任何您喜欢的方式存储。

编写一个高效的函数以列出在给定时间内还活着的所有人，这是最好的方法是什么？

数据结构应该也能够有效地进行可变操作，特别是在添加新元素方面。

例如，概念上类似于：

List<Person> alive(List<Person> people, LocalDate date) {
  return people.stream().filter(x -> x.bornOn.compareTo(date) <= 0 && x.diedOn.compareTo(date) > 0).collect(Collectors.toList())
}

仅仅更有效率。

我的最初直觉是拥有两个NavigableMaps。

NavigableMap<LocalDate, Person> peopleSortedByBornOn;
NavigableMap<LocalDate, Person> peopleSortedByDiedOn;

可以使用给定日期的headMap() / tailMap()查询集合中的每个元素，这些查询的交集就是结果。

但是是否有更快或更方便的解决方案呢？也许甚至有一些广泛使用的Java 集合/映射类型可以支持这种操作吗？

- Bogey

---

如果您可以使用任何数据结构，并且唯一的目的是快速查询，则可以使用一个（排序的）哈希映射表，其中包含从第一个出生日期到最后一个死亡日期的所有日期作为键，以及人员的Set/List作为值。这是查询的最快方式。 - Tobias Otto

@TobiasOtto 谢谢，确实如此 - 我应该提到，结构也应该是高效可变的。 - Bogey

我能想到的每种优化方式都需要对另一个约束施加压力。以下是一些问题可能会有所帮助...您是否关心内存压力？当您说可变时，是指更改出生/死亡值还是添加新人员？算法应该是线程安全的，还是您总是希望使用单个线程进行过滤？您是否关心初始加载时间（创建结构可能很慢）？您是否关心删除/插入性能？ - Ioannis Deligiannis

@IoannisDeligiannis：1）添加新人，假设出生日期/去世日期对于一个人来说永远不会改变。2）单线程。3）假设您从未拥有任何数据，并且您在快速但不可预测的信息流中接收到Person对象。4）不需要删除；插入与前面的点相同。 - Bogey

@Bogey，你最多会有多少人？ - nice_dev

@vivek_23 我们可以设定最大不超过一千万。 - Bogey

Answer 1

我想提到几何数据结构，比如四叉树。这是为了理论目的。有 (born, died) 坐标: died >= born。

    d         b=d
    |    | - /
    | +  |  /
    |    | /
  D |____|/
    |   /:
    |- / :
    | /  :
    |/___:_____ b
         D

所有点都位于上三角区域，+ 是在日期 D 生活的人的矩形区域。该矩形左侧和顶部为开放式。

使用几何数据结构是可行的。并且有一些数据库可以处理这样的几何查询。

尽管我不敢打赌速度会更快，但我很想看到一个实现。也许是在处理巨大数字时。

- Joop Eggen

---

基于旧答案，即使是一个直接的实现也应该相当不错，而且使用PostGIS可以获得空间索引，我想性能会更好。 - Kayaman

Answer 2

鉴于约束条件的澄清，我会保持简单，并使用地图来为特定日期的在世人员保留引用，有效地创建一个索引。

Map<LocalDate,LinkedList<Person>> aliveMap;

对于map和LinkedList，put的时间复杂度为O(1)。另一方面，get的时间复杂度是最好的，为O(1)（假设哈希算法良好）。

就内存而言，你需要支付额外的“引用”成本，但这可能相当显著（对于64位虚拟机，每个人80年x365天x8字节或233,600字节）。

这种方法在get操作上会产生最佳性能，但在内存方面可能最差，并且在put操作上平均水平。

变化： 不必创建完整的索引，而可以创建桶，例如按年份划分，先获取给定年份中所有还活着的人，然后过滤掉死者。

Map<Integer,LinkedList<Person>> aliveMap;

注意：我假设你的数据跨越了100年，而不是涵盖整个人口（75亿）。如果你只关注50-100年的时间窗口，那么可能会有更有效的专业化。

- Ioannis Deligiannis

---

感谢您的建议！如果我正确理解了您的方法，可能会出现以下问题：假设没有人在2020年1月1日出生或死亡。您仍然可能想知道在这个日期谁还活着。但是，您可能没有相应的映射条目 - 除非您添加从现在到永远（或接下来的100多年）的每一天的条目，这将占用大量内存。目前，我正在使用类似的可导航映射，仅存储整体状态发生更改的日期（任何人出生或死亡），并查找最接近的小于或等于日期。 - Bogey

实际上是后者，即每天的存储。考虑到平均寿命约为80年，每个人大约会有80个条目（因此在上述计算中为80x）。这个想法是存储相同的对象实例，因此只产生指针的成本。正如我在上面的评论中提到的，我认为你可以优化的唯一方法是强调另一个资源，在这种情况下，那将是内存。然而，与对象内部的数据相比，指针占用的空间应该是微不足道的。 - Ioannis Deligiannis

啊。假设您查询的是每天的生存状态（而不是年份），我认为我们需要80 * 365个条目; 如果覆盖最大寿命而不是预期，则可能需要更多，大约为125 * 365。如果包括过去出生的人，可能还有更多。但是我同意 - 这肯定是内存与CPU压力之间的权衡。 - Bogey

你是对的...那时还是清晨，大脑还没有完全启动。该算法和特征对平均80-90岁的人比较敏感，而不是最高年龄的人。我会看看是否能稍后提供更好的代码示例。 - Ioannis Deligiannis

Answer 3

我能想到的唯一提高效率的方法是创建自己的定制数据结构。例如，在Java中创建自己的HashMap，可以重写“put”方法。这样，当您将Person对象插入映射时，您将从插入时就知道它是否存活。 在这里您可以找到一个创建自定义HashMap的示例。

- Andrei Tigau