K 个最近的元素
K nearest elements
这是一道面试题。
宇宙中有数十亿颗恒星。您将使用哪种数据结构来回答查询
"Give me the k stars nearest to Earth".
我想到了堆。因为我们可以在 O(n) 中进行堆化并在 O(logn) 中得到 n_smallest。有没有更好的数据结构适合这个目的？
您要 运行 解决的第一个问题是规模。仅银河系中就有 1000 亿到 4000 亿颗恒星。估计有 100 亿个星系。如果我们假设每个星系平均有 1000 亿颗恒星，那么宇宙中就有 10^19 颗恒星。你不太可能有那样的记忆。即使你有足够的记忆力，你也可能没有时间。假设您的 heapify 操作每秒可以进行十亿次迭代，则需要一万亿秒（31,700 年）。然后你必须加上从堆中移除最小的 k 所需的时间。
您不太可能通过使用多线程或进程来构建堆来获得显着改进。
此处的关键是 pre-process 数据并将其存储在可让您快速消除大多数可能性的形式中。最简单的方法是有一个排序的恒星列表，按照它们与地球的距离排序。所以 Sol 将排在列表的顶部，Proxima Centauri 将排在其后，等等。然后，获取最近的 k 颗星将是一个 O(k) 操作：只需从列表中读取前 k 项。
不过，排序列表很难更新。更好的选择是 k-d tree。更容易更新，并且获取 k 个最近的邻居仍然相当快。
假设输入不能同时全部存储在内存中（这将是一个挑战！），而是宇宙中恒星的 流 - - 就像你会得到一个迭代器或其他东西一样 - 你可以从使用最大堆（而不是可能首先想到的最小堆）中受益。
一开始你只需将星星推入堆中，以它们与地球的距离为键，直到你的堆有 k 个条目。
从那时起，当新星星的距离大于堆的根部时，您将忽略它。当它比 root-star 更近时，用那个新星替换根并向下筛选以恢复堆 属性.
您的堆不会增长超过 k 个元素，并且始终由 k 个离您最近的星星组成已处理。
一些备注：
因为它是最大堆，你不知道哪个是最近的星（在常数时间内）。当你停止算法，然后一个接一个地拉出根节点时，你会得到 k 个最近的星星，按距离递减的顺序排列。
由于可观测 (!) 宇宙估计有 1021 颗恒星，您需要最好的超级计算机之一 (1 exaFLOPS ) 希望在合理的时间内处理所有这些星星。但至少这个算法只需要在内存中保留k颗星。
这是一道面试题。
宇宙中有数十亿颗恒星。您将使用哪种数据结构来回答查询 "Give me the k stars nearest to Earth".
我想到了堆。因为我们可以在 O(n) 中进行堆化并在 O(logn) 中得到 n_smallest。有没有更好的数据结构适合这个目的？
您要 运行 解决的第一个问题是规模。仅银河系中就有 1000 亿到 4000 亿颗恒星。估计有 100 亿个星系。如果我们假设每个星系平均有 1000 亿颗恒星，那么宇宙中就有 10^19 颗恒星。你不太可能有那样的记忆。即使你有足够的记忆力，你也可能没有时间。假设您的 heapify 操作每秒可以进行十亿次迭代，则需要一万亿秒（31,700 年）。然后你必须加上从堆中移除最小的 k 所需的时间。
您不太可能通过使用多线程或进程来构建堆来获得显着改进。
此处的关键是 pre-process 数据并将其存储在可让您快速消除大多数可能性的形式中。最简单的方法是有一个排序的恒星列表，按照它们与地球的距离排序。所以 Sol 将排在列表的顶部，Proxima Centauri 将排在其后，等等。然后，获取最近的 k 颗星将是一个 O(k) 操作：只需从列表中读取前 k 项。
不过，排序列表很难更新。更好的选择是 k-d tree。更容易更新，并且获取 k 个最近的邻居仍然相当快。
假设输入不能同时全部存储在内存中（这将是一个挑战！），而是宇宙中恒星的 流 - - 就像你会得到一个迭代器或其他东西一样 - 你可以从使用最大堆（而不是可能首先想到的最小堆）中受益。
一开始你只需将星星推入堆中，以它们与地球的距离为键，直到你的堆有 k 个条目。
从那时起，当新星星的距离大于堆的根部时，您将忽略它。当它比 root-star 更近时，用那个新星替换根并向下筛选以恢复堆 属性.
您的堆不会增长超过 k 个元素，并且始终由 k 个离您最近的星星组成已处理。
一些备注：
因为它是最大堆，你不知道哪个是最近的星（在常数时间内）。当你停止算法，然后一个接一个地拉出根节点时，你会得到 k 个最近的星星，按距离递减的顺序排列。
由于可观测 (!) 宇宙估计有 1021 颗恒星，您需要最好的超级计算机之一 (1 exaFLOPS ) 希望在合理的时间内处理所有这些星星。但至少这个算法只需要在内存中保留k颗星。