高效的元组列表比较

Question

我在这个问题上遇到了一些困难，想请教一下大家的意见。

我有一个很大的列表，里面是四个元素的元组，格式是：

(ID号码, 类型, 开始索引, 结束索引)

之前在代码中，我搜索了成千上万的文本块，找到了两种特定类型的子字符串。这些元组记录了在哪个大文本块中找到了子字符串，它属于哪种类型，以及这个子字符串的开始和结束位置。

我的最终目标是查看这个列表，找出在同一个ID的文本块中，类型1的子字符串出现在类型2的子字符串之前的所有情况。然后我想把这些信息存储成格式为(ID, 类型1, 开始, 结束, 类型2, 开始, 结束)的对象。

我尝试了很多方法，但效率都很低。我把列表按ID和开始索引排序，然后试着用不同的方法从列表中取出项目进行比较。我觉得应该有更优雅的解决方案。有没有聪明的人愿意帮帮我这个疲惫的脑袋呢？？？

提前谢谢大家！

Answer 1

我最近做过类似的事情。可能我没有完全理解你的问题，但我还是试试看。

我会使用一个字典：

from collections import defaultdict:
masterdictType1=defaultDict(dict)
masterdictType2=defaultdict(dict)


for item in myList:
   if item[1]=Type1
       if item[0] not in masterdictType1:
           masterdictType1[item[0]]['begin']=item[2] # start index
           masterdictType1[item[0]]['end']=item[-1] # end index
   if item[1]=Type2
       if item[0] not in masterdictType2:
           masterdictType2[item[0]]['begin']=item[2] # start index
           masterdictType2[item[0]]['end']=item[-1] # end index

joinedDict=defaultdict(dict)

for id in masterdictType1:
    if id in masterdictType2:
        if masterdictType1[id]['begin']<masterdictType2[id]['begin']:
            joinedDict[id]['Type1Begin']=masterdictType1[id]['begin']
            joinedDict[id]['Type1End']=masterdictType1[id]['end']
            joinedDict[id]['Type2Begin']=masterdictType2[id]['begin']
            joinedDict[id]['Type2End']=masterdictType2[id]['end']

这样做可以让你的代码更清晰，而且字典很耐用，因为你可以很方便地把字典保存下来。

Answer 2

我不知道你有多少种类型的数据。不过，如果我们假设你只有类型1和类型2，那这个问题听起来有点像归并排序。用归并排序的方法，你可以一次性遍历整个列表。

你可以设置两个索引，一个用来指向类型1（我们叫它I1），另一个用来指向类型2（叫它I2）。先根据ID对列表进行排序，从开始的地方开始。把I1设置为类型1的第一个实例，把I2设置为0。如果I1的ID小于I2的ID，那就把I1往后移动一步。如果I2的ID小于I1的ID，那就把I2往后移动一步。如果I1的ID等于I2的ID，那就检查一下iStart。

I1只能停在类型1的记录上，而I2只能停在类型2的记录上。一直移动索引，直到它们停在合适的记录上。

你可以做一些假设来加快这个过程。当你找到一个成功的区块时，可以把I1移动到下一个区块。每当I2小于I1时，可以把I2设置为I1的下一个位置（注意不要这样做，因为你可能会错过失败的情况！）。每当你发现明显的失败情况时，就把I1和I2都移动到下一个区块（当然是要停在合适的记录上）。

Answer 3

解决方案：

result = [(l1 + l2[1:]) 
          for l1 in list1 
          for l2 in list2 
          if (l1[0] == l2[0] and l1[3] < l2[2])
          ]

... 这里是测试代码：

list1 = [(1, 'Type1', 20, 30,),
         (2, 'Type1', 20, 30,),
         (3, 'Type1', 20, 30,),
         (4, 'Type1', 20, 30,),
         (5, 'Type1', 20, 30,),
         (6, 'Type1', 20, 30,), # does not have Type2

         (8, 'Type1', 20, 30,), # multiple
         (8, 'Type1', 25, 35,), # multiple
         (8, 'Type1', 50, 55,), # multiple
         ]

list2 = [(1, 'Type2', 40, 50,), # after
         (2, 'Type2', 10, 15,), # before
         (3, 'Type2', 25, 28,), # inside
         (4, 'Type2', 25, 35,), # inside-after
         (4, 'Type2', 15, 25,), # inside-before
         (7, 'Type2', 20, 30,), # does not have Type1

         (8, 'Type2', 40, 50,), # multiple
         (8, 'Type2', 60, 70,), # multiple
         (8, 'Type2', 80, 90,), # multiple
         ]

result = [(l1 + l2[1:]) 
          for l1 in list1 
          for l2 in list2 
          if (l1[0] == l2[0] and l1[3] < l2[2])
          ]

print '\n'.join(str(r) for r in result)

目前不太清楚，如果在同一个文本ID中同时出现多个Type1和Type2，你希望得到什么结果。请具体说明一下。