python - 将 python 列表投影到现有值上(使用生成器的生成器)

Question

给定一个常量、一个排序的 float 列表和一个 2 元素 float 列表的列表，

CONST = 1.
lst1 = [1.2, 2.4, 3.1] #sorted
lst2 = [[2.0, 0.9], [3.1, 1.5], [1.0, 3.0], [2.5, 2.0]] 

我为 lst1 的所有元素构建了一个包含 [CONST, a] 对的新列表

我需要将list2“投影”到[CONST,a]列表上:lst2中的对的第二个值将更改为 list1 中最接近的值，并且该对的第一个值将是相同的第二个值的所有第一个值的总和。

因此给出的示例的结果将是:

[[6.1, 1.2], [3.5, 2.4], [2.0, 3.1]]

到目前为止，我有类似的东西:

from itertools import groupby
from bisect import bisect
from operator import itemgetter

for t in lst2:
    i = bisect(lst1, t[1])
    bounds = lst1[i-1:i+1] if i else [lst1[0]]
    t[1] = min(bounds, key=lambda x: abs(x-t[1]))

lst2 += [[CONST, a] for a in lst1]
lst2 = sorted(lst2, key=itemgetter(1))
res = [[sum([t[0] for t in group]), keys] for keys, group in groupby(lst2, itemgetter(1))]

但是列表(尤其是lst1)可能很长(1e5+)，我有一种感觉，在那里我可以有更好的效率。有什么想法吗？

Answer 1

由于排序主导了运行时间，因此很难做得更快，但这里有一个不需要使用 lst1 的版本。但它确实会迭代 lst1:

sorted_lst2 = sorted(lst2, key=itemgetter(1))
i = 0
res = []
k = 0
while i + 1 < len(lst1):
    before = lst1[i]
    const = CONST
    while i + 1 < len(lst1) and before == lst1[i + 1]:
        const += CONST
        i += 1
    after = lst1[i + 1]
    mid = before + (after - before) / 2
    sum_before = 0
    while k < len(sorted_lst2) and sorted_lst2[k][1] <= mid:
        sum_before += sorted_lst2[k][0]
        k += 1
    res.append([const + sum_before, before])
    i += 1
sum_before = 0
while k < len(sorted_lst2):
    sum_before += sorted_lst2[k][0]
    k += 1
res.append([CONST + sum_before, lst1[-1]])