python - 高效的元组列表比较

Question

我在这个问题上有点碰壁，我想知道是否有一些新鲜的头脑可以帮助我。

我有一个包含四个元素元组的大列表，格式如下:

(身份证号、类型、起始索引、结束索引)

在之前的代码中，我在数千个文本 block 中搜索了两种特定类型的子字符串。这些元组存储子字符串在哪个大块文本中找到，它是两种类型的子字符串中的哪一种，以及该子字符串的开始和结束索引。

最终目标是浏览此列表以找到在具有相同 ID 的文本 block 中第 1 类子字符串出现在第 2 类子字符串之前的所有实例。然后我想以(ID，类型 1，开始，结束，类型 2，开始，结束)的格式存储这些对象。

我曾试图摆弄一堆非常低效的东西。我将列表按 ID 排序，然后按开始索引排序，如果一直在尝试不同的方式将项目从列表中弹出以进行比较。我不得不想象有一个更优雅的解决方案。有没有聪明人愿意帮助我疲惫的大脑？？？

提前致谢

Answer 1

我不知道你有多少种。但是如果我们假设你只有类型 1 和类型 2，那么这听起来像是一个类似于归并排序的问题。使用归并排序，您可以单次遍历列表。

取两个索引，一个用于类型 1，一个用于类型 2 (I1, I2)。按id排序列表，start1。将 I1 作为 type1 的第一个实例启动，将 I2 作为零启动。如果 I1.id < I2.Id 则增加 I1。如果 I2.id < I1.id 则递增 I2。如果 I1.id = I2.id 然后检查 iStart。

I1 只能停在第一类记录上，I2 只能停在第二类记录上。继续增加索引，直到它落在适当的记录上。

您可以做出一些假设来加快速度。当你找到一个成功的 block 时，你可以将 I1 移动到下一个 block 。当 I2 < I1 时，您可以在 I1 + 1 处启动 I2(糟糕，请确保您不这样做，因为您会错过失败案例!)每当您检测到明显的失败案例时，将 I1 和 I2 移动到下一个 block (在适当的位置当然是建议)。