2

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

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

（ID 号、类型、开始索引、结束索引）

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

最终目标是查看此列表以查找具有相同 ID 的文本块中类型 1 子字符串出现在类型 2 子字符串之前的所有实例。然后我想以格式（ID、Type 1、Start、End、Type2、Start、End）存储这些对象。

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

提前致谢

4

5 回答 5

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 只能停在第二类记录上。继续增加索引，直到它落在适当的记录上。

您可以做出一些假设来加快速度。当您找到一个成功的块时，您可以将 I1 移动到下一个块。每当 I2 < I1 时，您可以在 I1 + 1 处启动 I2（请确保您不要这样做，因为您会错过失败案例！）每当您检测到明显的失败案例时，将 I1 和 I2 移动到下一个块（在适当的情况下）当然是推荐）。

于 2009-06-12T19:05:42.133 回答
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']

这为您提供了明确性并为您提供了一些持久的东西，因为您可以轻松地腌制字典。

于 2009-06-12T19:14:35.250 回答
1

解决方案：

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)

如果 Type1 和 Type2 在同一个文本 ID 中出现不止一次，则不清楚您想要什么结果。请明确说明。

于 2009-06-12T19:04:22.917 回答
0

Could I check, by before, do you mean immediately before (ie. t1_a, t2_b, t2_c, t2_d should just give the pair (t1_a, t2_b), or do you want all pairs where a type1 value occurs anywhere before a type2 one within the same block. (ie (t1_a, t2_b), (t1_a, t2_c), (t1_a, t2_d) for the previous example).

In either case, you should be able to do this with a single pass over your list (assuming sorted by id, then start index).

Here's a solution assuming the second option (every pair):

import itertools, operator

def find_t1_t2(seq):
    """Find every pair of type1, type2 values where the type1 occurs 
    before the type2 within a block with the same id.

    Assumes sequence is ordered by id, then start location.
    Generates a sequence of tuples of the type1,type2 entries.
    """
    for group, items in itertools.groupby(seq, operator.itemgetter(0)):
        type1s=[]
        for item in items:
            if item[1] == TYPE1: 
                type1s.append(item)
            elif item[1] == TYPE2:
                for t1 in type1s:
                    yield t1 + item[1:]

If it's just immediately before, it's even simpler: just keep track of the previous item and yield the tuple whenever it is type1 and the current one is type2.

Here's an example of usage, and the results returned:

l=[[1, TYPE1, 10, 15],
   [1, TYPE2, 20, 25],  # match with first
   [1, TYPE2, 30, 35],  # match with first (2 total matches)

   [2, TYPE2, 10, 15],  # No match
   [2, TYPE1, 20, 25],
   [2, TYPE1, 30, 35],
   [2, TYPE2, 40, 45],  # Match with previous 2 type1s.
   [2, TYPE1, 50, 55],
   [2, TYPE2, 60, 65],  # Match with 3 previous type1 entries (5 total)
   ]

for x in find_t1_t2(l):
    print x

This returns:

[1, 'type1', 10, 15, 'type2', 20, 25]
[1, 'type1', 10, 15, 'type2', 30, 35]
[2, 'type1', 20, 25, 'type2', 40, 45]
[2, 'type1', 30, 35, 'type2', 40, 45]
[2, 'type1', 20, 25, 'type2', 60, 65]
[2, 'type1', 30, 35, 'type2', 60, 65]
[2, 'type1', 50, 55, 'type2', 60, 65]
于 2009-06-12T20:53:47.460 回答
0

假设每个 ID 有很多条目，我会（伪代码）

    对于每个 ID：
        对于该 ID 的每个 type2 子字符串：
            将其存储在有序列表中，按起点排序
        对于该 ID 的每个 type1 子字符串：
            计算终点（或其他）
            在有序列表中查找
            如果右边有任何东西，你就成功了

因此，如果您可以控制初始排序，而不是 (ID, start)，您希望它们按 ID 排序，然后按类型（2 在 1 之前）。然后在类型中，按类型 2 的起点和要比较类型 1 的偏移量进行排序。我不确定“A在B之前”是指“A在B开始之前开始”还是“A在B开始之前结束”，但请做适当的事情。

然后，您可以通过遍历列表一次来完成整个操作。您不需要实际构建 type2s 的索引，因为它们已经按顺序排列。由于 type1 也已排序，因此您可以从前一次搜索的结果开始使用线性或二进制搜索进行每次查找。如果 type1 与 type2 相比有很多，则使用线性搜索（因此结果很接近），如果 type2 与 type1 相比有很多，则使用二分搜索（因此结果稀疏）。或者只是坚持使用线性搜索，因为它更简单——这种查找是内部循环，但它的性能可能并不重要。

如果您无法控制排序，那么我不知道为每个 ID 构建 type2 子字符串列表是否更快；或在开始按所需顺序之前对整个列表进行排序；或者只是为了使用你所拥有的，通过编写一个“查找”，在搜索 type2 时忽略 type1 条目（已经按要求排序）。测试它，或者只是做任何导致更清晰代码的事情。即使没有重新排序，您仍然可以使用合并式优化，除非“按起始索引排序”对于 type1s 来说是错误的。

于 2009-06-12T19:38:37.233 回答