一种组合可变尺寸列表的算法优化

Question

我创建了一个算法，它将来自不同列表的数据组合成一个单独的列表。这个问题是关于设计这个算法的一个有效的/优化的版本。

背景：

输入包括包含(值、提交时间)对的元组列表。这些可以被认为是二维数组。以下是示例输入：

l1 = [(value-11, time-11),(value-12, time-12),(value-13, time-13),(value-14, time-14),(value-15, time-15)]
l2 = [(value-21, time-21),(value-22, time-22)]
l3 = [(value-31, time-31),(value-32, time-32),(value-33, time-33),(value-34, time-34)]
l4 = [(value-41, time-41),(value-42, time-42),(value-43, time-43),(value-44, time-44),(value-45, time-45)]
l5 = [(value-51, time-51)]
.
.
.
ln = [(value-n1, time-n1),(value-n2, time-n2),....(value-nm, time-nm)]

请注意：

• 列表的大小是可变的。
• 按提交时间计算，列表为sorted。
• 最近的元组出现在最左边的位置。
• 每个元组中的时间是将所述元组提交到列表中的实际时间。
• 这些名单没有一一填写。也就是说，time-21不一定比time-15晚。

需求：

我正试图从给定的输入中生成一个综合列表。结果是包含所有输入列表中的最新k元组。现在让我们设置k=20。

当前方法：

我从每个列表中检索多达20个元素。我将它们合并成一个单数列表，按每个元组的提交时间排序。然后我只从这个结果中选择前20个元素。

不用说，这是一种很残忍的方法。它不像列表规模的数量那样能很好地缩放。我以为我能做得更好，但到目前为止我还没有想出任何办法。如果能从专家那里得到一个说明性的例子，说明如何尽可能有效地进行这种操作，那就太好了。

如果重要的话，我个人的偏好是python。

附注：我们可以用一种方法来解决这个问题。这就是始终保持一个综合的全球列表。就这个问题而言，让我们忽略这一点。

Answer 1

下面是一种高效的方法，使用heapq.merge允许您懒洋洋地合并排序列表。

(编辑:我刚刚意识到我误解了问题的一部分-最近的一些项目，所以时间越长的项目就在左边，在列表的开头，而不是我想象的结尾。)所以，同样的事情，但我们甚至不必按相反的顺序迭代列表)：

from heapq import merge
from itertools import islice
from operator import itemgetter

l1 = [("a1", 40),("b1", 30),("c1", 20),("d1", 10)]
l2 = [("a2", 32),("b2", 24),("c2", 9)]
l3 = [("a3", 35),("b3", 18),("c3", 16)]

data = [l1, l2, l3]

out = list(islice(merge(*data, key=itemgetter(1), reverse=True), 5))

print(out)
# [('a1', 40), ('a3', 35), ('a2', 32), ('b1', 30), ('b2', 24)]

我们将我们的列表交给merge，它将懒洋洋地迭代它们，每次使用具有较大time的元组。

时间是每个元组中索引1处的值，因此是key=itemgetter(1)。

merge的默认行为是接受最小值的项，因此我们必须使用reverse=True来告诉它选择最大的项。

然后，我们使用islice从其中获取第一个(此处为5个)项，并将其转换为一个列表。

因此，由于一切都是基于迭代器的，所以只从列表中检索必要的项。

如果元组按相反的顺序排序，就像我最初想象的那样，最近的顺序是列表的末尾:我们必须以相反的顺序在列表上迭代：

from heapq import merge
from itertools import islice
from operator import itemgetter

l1 = [("a1", 10),("b1", 20),("c1", 30),("d1", 40)]
l2 = [("a2", 9),("b2", 24),("c2", 32)]
l3 = [("a3", 16),("b3", 18),("c3", 35)]

data = [l1, l2, l3]

out = list(islice(merge(*map(reversed, data), key=itemgetter(1), reverse=True), 5))

print(out)
# [('d1', 40), ('c3', 35), ('c2', 32), ('c1', 30), ('b2', 24)]

为了回答您的最后一个评论，下面是一个在引入key和reverse关键字参数到heapq.merge之前，用于3.5年以上的Python版本的解决方案。

其想法仍然是与迭代器和生成器表达式一起工作，以便每次访问和处理一个数据片段。关键并不是什么大问题，但是替换reverse要复杂一些，因为merge希望它收到的列表将按递增顺序排序。

一种解决方案是通过添加第一个字段来修饰从列表中读取的每个元组，该字段将与时间顺序相反。因为我们不能使用“负时间”，所以我们可以使用timedelta datetime.max - time。在返回元组之前，我们只需删除第一个字段。

我创建了一个生成器，它在列表上迭代并生成修饰的元组。我将生成器表达式分隔开，以避免一行很长、很难读的内容：

# Before Python 3.5, merge doesn't support key and reverse

from heapq import merge
from itertools import islice
from datetime import datetime

def decorated_with_reverse_datetime(lst):
    for value, time in lst:
        yield (datetime.max - time, value, time)


l1 = [("a1", datetime(2020, 12, 13, 12, 40)),
      ("b1", datetime(2020, 12, 13, 12, 30)),
      ("c1", datetime(2020, 12, 13, 12, 20)),
      ("d1", datetime(2020, 12, 13, 12, 10))]

l2 = [("a2", datetime(2020, 12, 13, 12, 32)),
      ("b2", datetime(2020, 12, 13, 12, 24)),
      ("c2", datetime(2020, 12, 13, 12, 9))]

l3 = [("a3", datetime(2020, 12, 13, 12, 35)),
      ("b3", datetime(2020, 12, 13, 12, 18)),
      ("c3", datetime(2020, 12, 13, 12, 16))]

data = [l1, l2, l3]

sorted_tuples = merge(*map(decorated_with_reverse_datetime, data))
undecorated = (tup[1:] for tup in sorted_tuples)
out = list(islice(undecorated, 5))

print(out)
[('a1', datetime.datetime(2020, 12, 13, 12, 40)),
 ('a3', datetime.datetime(2020, 12, 13, 12, 35)),
 ('a2', datetime.datetime(2020, 12, 13, 12, 32)),
 ('b1', datetime.datetime(2020, 12, 13, 12, 30)),
 ('b2', datetime.datetime(2020, 12, 13, 12, 24))]

您可以想象出链式生成器(如管道)，其中输出在需要时从链中提取数据，因此只有最小的必要数据操作才会发生。要了解更多关于生成器使用的信息和想法，请阅读来自这份报告的戴维·比兹利。