python - 对多条线上的点进行排序

Question

鉴于我们在图表上有两条线(我刚刚注意到我颠倒了 Y 轴上的数字，这是一个错误，它应该从 11-1 开始)

我们只关心 X 轴交点的整数

我们需要将这些点从最高 Y 值到最低 Y 值排序，无论它们在 X 轴上的位置如何(请注意，这些图片是我手工制作的，因此它们可能无法完美对齐)。

我有几个问题:

1) 我必须假设这是一个已知问题，但它有特定的名称吗？

2)处理数百亿(或数亿)行时是否存在已知的最佳解决方案？我们当前手动计算每个点然后将其与一个巨大列表进行比较的过程需要几个小时的处理时间。尽管我们可能有一亿行，但我们通常只需要前 100 或 50,000 个结果，其中一些结果远远“低于”其他行，因此无需计算它们的点。

Answer 1

1. 您的数据结构是 set元组数

   lines = {(y0, Δy0), (y1, Δy1), ...}
   

2. 您只需要 ntop点，因此构建 set只含有 顶部ntop yi值，只需一次传递数据

   top_points = choose(lines, ntop)
   

   编辑---选择ntop我们必须跟踪最小的 一，这是有趣的信息，所以让我们也返回这个值 来自choose ，我们还需要初始化decremented

   top_points, smallest = choose(lines, ntop)
   decremented = top_points
   

   并开始循环...

   while True:
   

3. 生成 set递减值

   <罢工> 递减 = {(y-Δy, Δy) for y, Δy in top_points}

       decremented = {(y-Δy, Δy) for y, Δy in decremented if y>smallest}
       if decremented == {}: break
   

4. 生成一组候选者

       candidates = top_lines.union(decremented)
   

5. 生成一组新的顶点

       new_top_points, smallest = choose(candidates, ntop)
   

   以下不再需要

6. 检查是否 new_top_points == top_points

       if new_top_points == top_points: break
       top_points = new_top_points</strike>
   

   当然，我们处于循环之中......

困难的部分是choose功能，但我认为 this answer对这个问题 How can I sort 1 million numbers, and only print the top 10 in Python? 可以帮助你。