Как быстро получить результат соответствия списка строк списку шаблонов в python? - PullRequest
Новая
       25

Как быстро получить результат соответствия списка строк списку шаблонов в python?

1 голос
/ 17 июня 2020

Теперь у меня есть список шаблонов: 

list1 = ['a[0-9]+', 'b[a-z]+', 'c[A-Z]+', ...]

, и у меня есть еще один список строк: 

list2 = ['a1', 'babc', 'cABC', 'bbb', 'c1', ...]

I wi sh, чтобы быстро узнать строку в списке list2. какой шаблон в списке 1 и вернуть его индекс (если нет совпадения, вернуть -1): 

output = [0, 1, 2, 1, -1, ...]

Теперь я просто использую «for», чтобы добиться этого: 

output = []
for string in list2:
  matched = False
  for pattern in list1:
    if re.match(pattern, string):
      output.append(list1.index(pattern))
      matched = True
      break
  if not matched:
    output.append(-1)

Этот метод работает, но занимает слишком много времени, так как list1 и list2 большие. Так есть ли другой метод, который может быстро вернуть результат?

Ответы [ 2 ]

1 голос
/ 17 июня 2020

Вы можете использовать map(), что улучшит время выполнения вложенных циклов.
Уменьшая один if и удалив создание и добавление к другому списку и избегая метода индекса для списка, вы уменьшите общее время работы. 

import re

list1 = ['a[0-9]+', 'b[a-z]+', 'c[A-Z]+']
list2 = ['a1', 'babc', 'cABC', 'bbb', 'c1']

def check_if_exist(item):
    for i, regex in enumerate(list1):
        if re.match(regex, item):
            return i
    return -1

print(list(map(check_if_exist, list2)))

Вывод 

[0, 1, 2, 1, -1]

Проверить оба метода в timeit возвращает, что функция с map() выполняется в 0.17607659999999997 и исходный код в 0.1822188 оба 10000 раз.
Это будет иметь большое значение в больших списках.

0 голосов
/ 17 июня 2020

Попробуйте перебрать список выражений и выполнить поиск пополам в отсортированном списке строк: 

import re
list2  = ['a[0-9]+', 'b[a-z]+', 'c[A-Z]+']
list1 = sorted(['a1', 'babc', 'cABC', 'bbb', 'c1'])
output = []

def bisect_match(l, p, start, end):
    if(end-start+1 <= 0):
        return -1
    else:
        half = start + (end - start) // 2
        if(re.match(p, l[half])):
            return half
        else:
            if(l[half] > p):
                return(bisect_match)(l, p, start, half-1)
            else:     
                return(bisect_match)(l, p, half+1, end)

for string in list2:
    output.append(bisect_match(list1, string, 0, len(list1)))

print(output)
...