展开元组列表

Question

我有一个很大的元组列表（20-3000 万个条目）。每个子元组都有三条信息

(start, end, value)

，并且应该只代表序列中的一个位置。但是，如果值相同，则生成此数据的程序已连接相邻位置的一些值。因此它们看起来像这样：

[..., (71, 72, -0.2998250126838684),
      (72, 73, -0.2858070135116577),
      (73, 74, -0.29049500823020935),
      (74, 75, -0.3044680058956146),
      (75, 76, -0.28386199474334717),
      (76, 80, -0.27730199694633484), # PROBLEM: end - start > 1
      (80, 81, -0.2726449966430664),
      (81, 82, -0.26151400804519653),
      (82, 84, -0.2679719924926758),  # PROBLEM: end - start > 1
      (84, 85, -0.24273300170898438),
      (85, 86, -0.23799900710582733),
      (86, 87, -0.24745100736618042),
      (87, 88, -0.2568419873714447),
      (88, 89, -0.2585819959640503), ...]

为了解决这个问题，我想在列表中创建新条目，将代表多个位置的这些元组分隔成仅代表一个位置的新元组。 因此我希望有这样的输出：

(..., (71, 72, -0.2998250126838684),
      (72, 73, -0.2858070135116577),
      (73, 74, -0.29049500823020935),
      (74, 75, -0.3044680058956146),
      (75, 76, -0.28386199474334717),
      (76, 77, -0.27730199694633484), # New
      (77, 78, -0.27730199694633484), # New
      (78, 79, -0.27730199694633484), # New
      (79, 80, -0.27730199694633484), # New
      (80, 81, -0.2726449966430664),
      (81, 82, -0.26151400804519653),
      (82, 83, -0.2679719924926758),  # New
      (83, 84, -0.2679719924926758),  # New
      (84, 85, -0.24273300170898438),
      (85, 86, -0.23799900710582733),
      (86, 87, -0.24745100736618042),
      (87, 88, -0.2568419873714447),
      (88, 89, -0.2585819959640503), ...)

为此，我使用名为

bwList

的元组列表执行了以下操作：

replacementTuple = ()

for t in bwList:
    if t[1] - t[0] == 1:
        replacementTuple = replacementTuple + (t,)
    else:
        numNewTuples = t[1] - t[0]
        st, ed = range(t[0], t[1]), range(t[0] + 1, t[1] + 1)
        for m in range(numNewTuples):
            replacementTuple = replacementTuple + ((st[m], ed[m], t[2]) ,) 

这里的输出是元组的元组，而不是列表。无论如何我都不太介意。

这种方法似乎有效，但速度很慢！

有没有办法加快速度？

Answer 1

使用列表而不是元组作为结果。然后您可以就地追加到它，而不是每次添加时都复制元组，这使得您的算法为 O(n^2)。

您不需要

if

语句 -

end = start+1

只是一种限制情况，循环将正确处理它。

replacementList = []

for start, end, value in bwList:
    for i in range(start, end):
        replacementList.append((i, i+1, value))

您还可以使用生成器来构造元组。

replacementTuple = tuple((i, i+1, value) for start, end, value in bwList for i in range(start, end))