将Python列表投射到现有值（使用生成器的生成器）

Question

给定一个常量，一个排序的浮点数列表和一个2元素浮点数列表

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]] 

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

我需要在[CONST,a]的列表上“投影”list2：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]])

Answer 2

我想我找到了一个有趣的方法：一个发电机的发电机！Python太棒了！这大约是以前代码的两倍。你知道吗

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]]

def gen_generator(lst1):
    #Create iterators to form consecutive pairs
    it1_1, it1_2 = iter(lst1), islice(lst1+[float('inf')], 1, None)
    #Create iterator over items to insert and initialize p
    gen_generator.it2 = iter(sorted(lst2, key=itemgetter(1)))
    gen_generator.p=next(gen_generator.it2)
    for t1, t2 in zip(it1_1, it1_2):
        #Calculate the mid point of the pair t1, t2
        sup = (t1+t2)/2 if t2 != float('inf') else float('inf')
        #Create a generator for each item in lst1
        def generator():
            #All the previously inserted items have disappeared
            #So yield any p such that p[1] < sup
            while gen_generator.p is not None and gen_generator.p[1] < sup:
                yield gen_generator.p[0]
                #Move to next or None
                gen_generator.p = next(gen_generator.it2, None)
            #Add the constant
            yield CONST
        yield generator

res = [[sum(gen()), t] for gen, t in zip(gen_generator(lst1), lst1)]
return res