如何高效分组首元素连续且次元素相同的二元组？

需求概述 #

我有一个二元组列表，每个二元组的首元素是整数，等价于键值对（由list(d.items())生成）。键保证唯一，存在大量值相同且键为连续整数的键值对（后一个键等于前一个键加1）。需要将这些键值对分组为三元组：(起始键, 结束键, 对应值)。

逻辑示例 #

• 输入：[(0, 0), (1, 0), (2, 0)]，输出：[(0, 2, 0)]
• 输入：[(0, 0), (1, 0), (2, 0), (3, 1), (4, 1)]，输出：[(0, 2, 0), (3, 4, 1)]
• 输入：[(0, 0), (1, 0), (2, 0), (3, 1), (4, 1), (5, 2), (7, 2), (9, 2)]，输出：[(0, 2, 0), (3, 4, 1), (5, 5, 2), (7, 7, 2), (9, 9, 2)]（5、7、9非连续，故单独分组）

测试用例 #

输入

[(3, 0),
 (4, 0),
 (5, 0),
 (6, 2),
 (7, 2),
 (8, 2),
 (9, 2),
 (10, 2),
 (11, 2),
 (12, 2),
 (13, 1),
 (14, 1),
 (15, 3),
 (16, 3),
 (17, 3),
 (18, 3),
 (19, 3),
 (20, 3),
 (21, 3),
 (22, 3),
 (23, 3),
 (24, 3),
 (25, 3),
 (26, 3),
 (27, 1),
 (28, 1)]

预期输出

[(3, 5, 0), (6, 12, 2), (13, 14, 1), (15, 26, 3), (27, 28, 1)]

现有实现及问题 #

现有代码能得到正确输出，但效率不足：

def group_numbers(numbers):
    l = len(numbers)
    i = 0
    output = []
    while i < l:
        di = 0
        curn, curv = numbers[i]
        while i != l and curn + di == numbers[i][0] and curv == numbers[i][1]:
            i += 1
            di += 1
        output.append((curn, numbers[i - 1][0], curv))
    return output

测试用例生成代码：

import random

def make_test_case(num, lim, dat):
    numbers = {}

    for _ in range(num):
        start = random.randrange(lim)
        end = random.randrange(lim)
        if start > end:
            start, end = end, start
        x = random.randrange(dat)
        numbers |= {n: x for n in range(start, end + 1)}

    return sorted(numbers.items())

优化需求 #

如何更高效实现该功能？比如使用itertools.groupby？要求输出与现有正确方法完全一致。

补充说明 #

• 输入中可能存在无值的间隙，此类间隙不应被填充
• 输入不会出现重复键，若遇到需抛出异常

内容的提问来源于stack exchange，提问作者Ξένη Γήινος