如何有效地计算 Java 中间隔列表中点列表的命中数？
How to efficiently count hits of a list of points in a list of intervals in Java?
我有一个包含 0 到 250,000,000 之间大约 50,000 个点的列表和一个包含大约 10,000,000 个区间的列表。间隔存储在 MySQL 数据库中的 12 个表中。
我想计算每个点周围有多少间隔。我尝试了几种方法来做到这一点，但我总是遇到问题。如果我想构建一个区间树，它需要很多内存并且简单地遍历列表需要很多时间。
我需要在获得点数列表后大约 10 秒内得到结果。此外，准备数据库或创建数据结构也不是问题。所以在这个准备只需要做一次的情况下，如果时间再长一点就好了。
有什么想法吗？
我会用文件来做。
- 创建一个包含 2000 万条记录的文件，列出端点的位置，以及从左到右是 +1 间隔（间隔开始）还是 -1 间隔（间隔结束）
- 按位置排序此文件。
- 运行 遍历文件一次，并为每个位置发出一条记录，其中包含该位置、其左侧有多少个端点，以及如果您在该点有多少个端点。
- 将该文件的内容放入数据库中，使用 BTREE 索引。
现在对于每个点，您可以使用索引来查找最后位置大于或等于您的点的记录。然后根据它访问正确的字段。
如果你不能及时哄MySQL做这件事，你可以使用BerkeleyDB实现BTREE，然后就去做。或者哎呀，你可以 可能 只对你的点进行排序，然后与 2000 万个点文件并行扫描该文件。 （我会先尝试 BerkeleyDB。）
没有简单的解决方案。没有（我相信）不扫描每个 table 的至少一半就没有直接的方法来执行查询。 "half" 来自 INDEX(Start), INDEX(End) 并希望优化器动态选择更好的索引。这是 "Order(N)".
桶。通过发明 "buckets" 并确定哪些间隔位于哪个桶（或多个桶）中，您可以通过询问它位于哪个桶中来搜索点，然后仅在该桶内扫描开始...结束。 INDEX(bucket, start), INDEX(bucket, end)。但是，它确实需要复制一些行（因为一个间隔可能跨越多个桶）。它是对性能的部分改进，并且涉及插入和选择的一些复杂性。桶的数量成为速度和 space.
之间的权衡
非重叠。如果你能把它变成非重叠的间隔，那么有一个更好的方法，那就是 Order(1)。 Reference。它确实涉及插入和选择的复杂性，但存储例程可以隐藏这些。
第 13 table。如果您使用存储桶或不重叠，可能 最好使用第 13 个 table 进行搜索，从而将复杂性限制在 table 而不会弄乱与现有的 12.
我有一个包含 0 到 250,000,000 之间大约 50,000 个点的列表和一个包含大约 10,000,000 个区间的列表。间隔存储在 MySQL 数据库中的 12 个表中。
我想计算每个点周围有多少间隔。我尝试了几种方法来做到这一点，但我总是遇到问题。如果我想构建一个区间树，它需要很多内存并且简单地遍历列表需要很多时间。
我需要在获得点数列表后大约 10 秒内得到结果。此外，准备数据库或创建数据结构也不是问题。所以在这个准备只需要做一次的情况下，如果时间再长一点就好了。
有什么想法吗？
我会用文件来做。
- 创建一个包含 2000 万条记录的文件，列出端点的位置，以及从左到右是 +1 间隔（间隔开始）还是 -1 间隔（间隔结束）
- 按位置排序此文件。
- 运行 遍历文件一次，并为每个位置发出一条记录，其中包含该位置、其左侧有多少个端点，以及如果您在该点有多少个端点。
- 将该文件的内容放入数据库中，使用 BTREE 索引。
现在对于每个点，您可以使用索引来查找最后位置大于或等于您的点的记录。然后根据它访问正确的字段。
如果你不能及时哄MySQL做这件事，你可以使用BerkeleyDB实现BTREE，然后就去做。或者哎呀，你可以 可能 只对你的点进行排序，然后与 2000 万个点文件并行扫描该文件。 （我会先尝试 BerkeleyDB。）
没有简单的解决方案。没有（我相信）不扫描每个 table 的至少一半就没有直接的方法来执行查询。 "half" 来自 INDEX(Start), INDEX(End) 并希望优化器动态选择更好的索引。这是 "Order(N)".
桶。通过发明 "buckets" 并确定哪些间隔位于哪个桶（或多个桶）中，您可以通过询问它位于哪个桶中来搜索点，然后仅在该桶内扫描开始...结束。 INDEX(bucket, start), INDEX(bucket, end)。但是，它确实需要复制一些行（因为一个间隔可能跨越多个桶）。它是对性能的部分改进，并且涉及插入和选择的一些复杂性。桶的数量成为速度和 space.
非重叠。如果你能把它变成非重叠的间隔，那么有一个更好的方法，那就是 Order(1)。 Reference。它确实涉及插入和选择的复杂性，但存储例程可以隐藏这些。
第 13 table。如果您使用存储桶或不重叠，可能 最好使用第 13 个 table 进行搜索，从而将复杂性限制在 table 而不会弄乱与现有的 12.