Эффективные сравнения списка кортежей

Question

Я как бы бьюсь об эту проблему, и мне было интересно, могут ли мне помочь свежие мозги.

У меня большой список из четырех элементарных кортежей в формате:

(идентификационный номер, тип, начальный индекс, конечный индекс)

Ранее в коде я искал тысячи блоков текста для двух конкретных типов подстрок. Эти кортежи хранят информацию о том, в каком большом фрагменте текста была найдена подстрока, какой из двух типов подстрок она есть, а также начальный и конечный индекс этой подстроки.

Конечная цель состоит в том, чтобы просмотреть этот список и найти все случаи, когда подстрока типа 1 встречается перед подстрокой типа 2 в блоке текста с тем же идентификатором. Затем я хотел бы сохранить эти объекты в формате (идентификатор, тип 1, начало, конец, тип 2, начало, конец).

Я пытался возиться с кучей вещей, которые были супер неэффективными. У меня список отсортирован по ID, затем Start Index, и если я пытаюсь по-разному вытолкнуть элементы из списка для сравнения. Я должен представить, что есть более элегантное решение. Любые блестящие люди хотят помочь моему уставшему мозгу ???

Заранее спасибо

Answer 1

Я не знаю, сколько у вас типов. Но если мы предположим, что у вас есть только тип 1 и тип 2, то это похоже на проблему, подобную сортировке слиянием. Делая это с сортировкой слиянием, вы делаете один проход по списку.

Взять два индекса, один для типа 1 и один для типа 2 (I1, I2). Сортировать список по идентификатору, start1. Запустите I1 как первый экземпляр типа 1, а I2 как ноль. Если I1.id

I1 может останавливаться только на записи типа 1, а I2 может останавливаться только на записи типа 2. Продолжайте увеличивать индекс, пока он не попадет на соответствующую запись.

Вы можете сделать некоторые предположения, чтобы сделать это быстрее. Когда вы найдете успешный блок, вы можете переместить I1 к следующему блоку. Всякий раз, когда I2

Answer 2

Я недавно сделал что-то подобное. Возможно, я не понимаю вашу проблему, но здесь идет.

Я бы использовал словарь:

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 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)

Не ясно, какой результат вы бы хотели получить, если бы в одном и том же текстовом идентификаторе было более одного вхождения как Type1, так и Type2. Пожалуйста уточни.

Answer 4

Могу ли я проверить, с помощью до , вы имеете в виду немедленно до (т. Е. t1_a, t2_b, t2_c, t2_d должен просто дать пару (t1_a, t2_b), или вы хотите, чтобы все пары, где Значение type1 встречается в любом месте перед типом type2 в том же блоке (т. е. (t1_a, t2_b), (t1_a, t2_c), (t1_a, t2_d) для предыдущего примера).

В любом случае вы сможете сделать это за один проход по списку (при условии, что вы отсортированы по id, затем начнете индексировать).

Вот решение, предполагающее второй вариант (каждая пара):

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:]

Если это непосредственно перед этим, это еще проще: просто следите за предыдущим элементом и выдайте кортеж, когда он имеет тип 1, а текущий тип 2.

Вот пример использования и возвращенные результаты:

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

Возвращает:

[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]

Answer 5

Если предположить, что для каждого идентификатора есть много записей, я бы (псевдокод)

    for each ID:
        for each type2 substring of that ID:
            store it in an ordered list, sorted by start point
        for each type1 substring of that ID:
            calculate the end point (or whatever)
            look it up in the ordered list
            if there's anything to the right, you have a hit

Итак, если у вас есть контроль над начальной сортировкой, то вместо (ID, start) вы хотите, чтобы они сортировались по ID, а затем по типу (от 2 до 1). Затем внутри типа сортируйте по начальной точке для type2 и смещению, которое вы собираетесь сравнивать для type1. Я не уверен, что под «A до B» вы подразумеваете «A начинается до B» или «A заканчивается до B», но делайте все, что подходит.

Затем вы можете выполнить всю операцию, выполнив один раз список. Вам не нужно создавать индекс type2s, потому что они уже в порядке. Поскольку type1 также сортируются, вы можете выполнять каждый поиск с помощью линейного или двоичного поиска, начиная с результата предыдущего поиска. Используйте линейный поиск, если есть много типов type1s по сравнению с type2s (поэтому результаты близки друг к другу), и бинарный поиск, если есть много типов type2s по сравнению с type1s (поэтому результаты редки). Или просто придерживайтесь линейного поиска, поскольку он проще - этот поиск является внутренним циклом, но его производительность не может быть критичной.

Если у вас нет контроля над сортировкой, тогда я не знаю, быстрее ли будет составлять список подстрок type2 для каждого идентификатора по мере продвижения; или отсортировать весь список, прежде чем начать в нужном порядке; или просто работать с тем, что у вас есть, написав «поиск», который игнорирует записи type1 при поиске в type2s (которые уже отсортированы по мере необходимости). Протестируйте это или просто сделайте все, что приведет к более ясному коду. Даже без повторной сортировки вы все равно можете использовать оптимизацию в стиле слияния, если только «отсортировано по начальному индексу» не подходит для type1s.