我得到了大约 500000 个整数的列表，其中可能包含重复值。给定一些（其他）整数 k，我希望能够生成列表中严格小于 k 和大于 k 的整数的数量。
我可以对列表进行排序并使用二分搜索 - 两次，每个结果一次，或者一次，然后爬行列表，直到找到第一个大于 k 的值。这大约需要 log_2(500000) ~ 19 次操作。我需要执行这个操作大约五十万次。
是否有更好的方法来构造数据点以使操作更快？我对几乎所有东西都持开放态度，包括关联数组或其他任何东西。我很可能是用 Python 实现的，但这更像是一个数据结构问题，而不是编程问题。
假设你有一个包含 500,000 个整数的固定列表 L。给定另一个整数 K 列表，您需要一种快速方法来获取该列表中每个 k_i 的所有结果。对于每个 k_i，结果是两个数字 g_i 和 l_i，其中 g_i 表示 L 中严格大于 k_i 的整数的数量，l_i 是 L 中严格小于 k_i 的数字的数量。如何有效地解决这个问题取决于列表 K 中有多少个值。因为在这种情况下，列表 K 中有“大约一百万”个整数，依次查找每个整数可能效率不高，即使列表 L 已排序，或者在某些二叉搜索树等中。L 的“哈希映射”将是解决此类问题的现代方法，但即使这样，在实践中也可能不如传统的“排序和匹配”解决方案下面是因为内存缓存的工作方式，尽管只有基准测试才能证明这一点。无论如何，性能将取决于所使用硬件的缓存架构。 “排序和匹配”方法是解决此问题的老式方法，因为“批处理”大型机程序通常以这种方式处理顺序文件，因为内存通常太小且速度太慢，无法以任何其他方式进行处理。
我的建议是按升序对列表 K 和 L 进行排序，这样你就得到了有序列表 KS 和 LS。比较排序可以在 O(nlog n) 时间内完成，但整数也可以使用基数排序进行排序，即 O(mn)，其中 m 是“键”的宽度。在实践中，它可能会或可能不会比其他排序算法更快。
要获得所有结果，只需在每个列表上运行两个指针（或索引），执行“匹配”操作，以便两个指针保持“同步”。 LS 上的指针前进，直到遇到大于或等于 KS 中当前指向的元素的数字。这将为您提供该元素的 l_i 结果。一旦它达到大于 k_i 的数字或列表末尾，您就得到了 h_i。前进到下一个 k_i。重复此操作，直到处理完完整列表。
如果使用 O(nlog n) 算法完成排序，则处理数组的时间为 O(n)，因此总体来说为 O(nlog n)。如果使用基数排序，则时间复杂度为 O(n)，但也与键大小成正比。二叉搜索树中的单独查找或排序列表的二分查找也是 O(nlog n)，但在整个列表中进行，这实际上可能很慢，因为在任何时候只有少量列表可以存在于快速缓存中一度。空间要求取决于所使用的排序算法。列表可以就地排序，从而将空间需求保持在最低限度。这种“排序和匹配”方法不需要列表 L 是固定的。为 L 创建哈希映射可能比简单地对其进行排序要慢。
因为在这种情况下，K 中元素的数量级与 L 相同，所以在遍历两个排序列表时会非常频繁地找到结果，我怀疑这将使该方法难以以任何其他方式击败。