如何对列表列表进行排序，并按间隔仅保留每个第一个元素的最大第二个元素？

Question

这是的一个更难的版本，但我无法有效地解决它（最好不需要导入库）。

假设我有一些清单：

lst = [[1,2],[1,4],[1,6],[2,6],[2,3],[3,5],[7,8]]

假设我有一个间隔列表：

intervals = [0,3,5,8]

我想在每个间隔中保留一个由第一个元素和具有最高第二个元素的子列表。在这个例子中，这意味着只有一个子列表，第一个元素在 0 和 3 之间，一个子列表，第一个元素在 3 和 5 之间，等等......所以结果将是：

result:
>>> [[1,6],[3,5],[7,8]]

需注意：

如果是 {0 =< x < 3} 或这样的方式，则不是很重要 {0 < x =< 3} 只要没有重复。
最好是，例如，[1,6] 和 [2,6] 在同一区间内将保留的是第一个元素最低的元素 ( [1,6] )

Answer 1

以下是三个解决方案，按性能排序：

为每个元素中的 first/second 个数字创建两个列表。它会增加内存使用量，但却是最快的选择。
在max中使用key参数获取秒数最大的元素。避免重复内存使用，但速度大约慢 30%。这可能是一个很好的中间立场。
使用 itertools.groupby 和 key function 获取每个元素中第一个数字的间隔。它可用于更健壮的应用程序，但效率不如它迭代 Intervals 直到找到匹配区间的每个元素。它几乎比第一个选项慢 3 倍。

选项 1：创建两个列表

将列表分成两个列表，每个元素的 first/second 个数。

# sort and separate lst
lst = sorted(lst)
first = [e[0] for e in lst]
second = [e[1] for e in lst]

# iterate upper limits of intervals and get max of each sublist
i = k = 0
keep = []
while lst[i][0] < Intervals[0]:
    i += 1
for upper in Intervals[1:]:
    k = sum(f < upper for f in first[i:])
    keep.append(i + second[i:i+k].index(max(second[i:i+k])))
    i += k

result = [lst[i] for i in keep]
print(result)

输出

[[1, 6], [3, 5], [7, 8]]

选项 2：使用 max(lst, key)

用max(lst, key=lambda x: x[1])可以得到秒数最大的元素。这是间隔的实现。

lst = sorted(lst)

i = k = 0
result = []
for upper in Intervals:
    i += k
    # old solution summed a generator
    # k = sum(e[0] < upper for e in lst[i:])
    # this one uses a while-loop to avoid checking the rest of the list on each iteration
    # a good idea if `lst` is long and `Intervals` are many
    k = 0
    while i + k < len(lst) and lst[i+k][0] < upper: 
        k += 1
    if upper == Intervals[0]:
        continue
    result.append(max(lst[i:i+k], key=lambda x:x[1]))

输出

[[1, 6], [3, 5], [7, 8]]

选项 3：itertools.groubpy(lst, key)

from itertools import groupby

def get_bin(element, bins):
    x = element[0]
    if x < bins[0]:
        return -1
    elif x in bins:
        return bins.index(x)
    else:
        for i, b in enumerate(bins[1:]):
            if x < b:
                break
        return i
        

result = sorted([
    max(items, key=lambda x: x[1])
    for _, items in groupby(lst, lambda x: get_bin(x, Intervals))
])

输出

[[1, 6], [3, 5], [7, 8]]

Answer 2

为简单起见：

lst = [[1,2],[1,4],[1,6],[2,6],[2,3],[3,5],[7,8]]
intervals = [0,3,5,8] #usually, variables starts lowercase

初始版本（尚未回答）

我将演示如何通过 intervals 中的索引将列表分成几组 ，然后在此处 return 每个组的最大项目。您可以使用一个技巧，我想将其称为数组的“shift”：

def get_groups(lst, intervals): return [lst[i:j] for i,j in zip(intervals[:-1], intervals[1:])]

这是构建切片元组的好方法：(0, 3)、(3, 5)、(5, 8)。现在你有：

>>> groups = get_groups(lst, interval) >>> groups [[[1, 2], [1, 4], [1, 6]], [[2, 6], [2, 3]], [[3, 5], [7, 8]]]

然后在按第二列排序时提取最大元素：

>>> [max(n, key = lambda x: x[1]) for n in groups] [[1, 6], [2, 6], [7, 8]]

如果区分第二列具有相同值的两个项目很重要：

[max(n, key = lambda x: (x[1], x[0])) for n in groups]

最终版本

OP 需要，相比之下，根据落入 intervals 的值将列表分成几组。如果列表是预排序的，那么可以在第一个结果之上构建一个算法，并且我们正在对数组进行一次搜索，以便找到应该插入元素以保持顺序的索引。在那种情况下 get_groups 应该重新定义如下：

def get_groups(lst, intervals): lst = sorted(lst) firstcolumn = [n[0] for n in lst] intervals = searchsorted(first_column, intervals) return [lst[i:j] for i,j in zip(intervals[:-1], intervals[1:])]

目前您还可以使用 RichieV 答案的改编版本：

def searchsorted(array, intervals): idx, i, n = [], 0, len(array) for upper in intervals: while array[i] < upper: i += 1 if i == n: idx.append(n) return idx else: idx.append(i) return idx >>> searchsorted([1,1,1,2,2,3,7], [0,3,5,8]) [0, 5, 6, 7]

请注意，get_groups 不是最佳选择，因为 first_column 和 lst 都被迭代了两次。

用法：

def simple_sol(lst, intervals): return [max(n, key=lambda x: x[1]) for n in get_groups(lst, intervals)] #Output: [[1, 6], [3, 5], [7, 8]]

进一步优化

我写了一个 searchsorted 的定义，灵感来自替代方法 np.searchsorted which is based on binary search instead. It's also more efficient ( O(m log(n)) vs O(mn)). For Python version see also docs and source code of bisect.bisect_left and related answer about binary search. This is double win, C-level + binary search (pretty much the same as my ):

def binsorted(lst, intervals): lst = np.array(lst) lst = lst[np.argsort(lst[:,0])] #sorting lst by first row idx = np.searchsorted(lst[:,0], intervals) if idx[-1] == len(lst): return np.maximum.reduceat(lst, idx[:-1], axis=0) else: return np.maximum.reduceat(lst, idx, axis=0) #Output: [[2, 6], [3, 5], [7, 8]]

基准测试

我比较了 option1、option2、option3、simple_sol 和 binsorting 样本：

lst = np.random.randint(1000, size = (1000000, 2)).tolist() intervals = np.unique(np.random.randint(1000, size = 100)).tolist() + [1000]

和timeit是：

18.4 s ± 472 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 4.21 s ± 386 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 10.3 s ± 410 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 4.12 s ± 202 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 1.38 s ± 97.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

如何对列表列表进行排序，并按间隔仅保留每个第一个元素的最大第二个元素？

How to sort a list of lists and and to keep only the maximal 2nd element of each of the 1st elements by intervals?

python

sorting

list

intervals

初始版本（尚未回答）

最终版本

进一步优化

基准测试