Эффективный поиск частичных строк в списках Python

Question

В поисках эффективного метода поиска частичных строк в списках Python (3.6+).

У меня есть два списка.listA - это список строк pathname + уникальное имя файла:

['/pathname/uniquestring.ext', '/pathname/uniquestring.ext', '/pathname/uniquestring.ext' ...]

(создано с помощью glob (), имена файлов даны и уже существуют)

listB - это список словарей.Каждый словарь имеет одинаковый набор ключей, но уникальные значения.

[{key1:value1, key2:value2}, {key1:value3, key2:value4}, ...]

(также уже задано)

Одна пара ключ: значение в каждом словаре в listB будет иметь значение содержится в один уникальный элемент в списке A.

Однако позиция значения в том виде, в каком оно появляется в каждом элементе списка A. Не определена.

То, что я хотел, было: для каждогоitem в listB, найдите элемент в listA, который содержит подстроку, соответствующую паре k: v в dict, и создайте новый dict (или список кортежей) в качестве «таблицы поиска» (цель состояла в том, чтобы исправить поврежденное создание exif-файладата в наборе файлов изображений).

Пример:

listA = ['/pathname/abdce_654321.ext', '/pathname/a3b4c5_123456.ext', '/pathname/cbeebie_645321_abcde.ext', ...]

listB = [{"id": "123456", "create_date": "23/05/2014"}, ...]

new_dict = {"/pathname/a3b4c5_123456.ext": "23/05/2014, ...}

Я получил именно то, что я хочу от dict comp следующим образом:

{j:i['create_date'] for j in listA for i in listB  if i['id'] in j}

Но , даже для моих очень маленьких файлов (~ 5500 наименований) это занимает 12 секунд на моем (по общему признанию, довольно старом) ноутбуке.

Предположительно, это потому, что мне приходится перебирать весь список B~ 5500 раз, используя мой метод.

Есть ли более эффективныйможно сделать это в Python?

(примечание: я не ищу совета о том, как исправить данные exif с помощью python;это обобщенный вопрос о поиске строк в списках)

ИСПРАВЛЕНИЯ И УТОЧНЕНИЯ

1. В моем примере я пренебрег размещением кавычек вокруг значения '123456', подразумевая, конечно, что этоцелое число;В реальных данных это не так, равно как и эквивалентные значения в реальных данных, с которыми я имел дело.
2. Подстрока 'id', как она появляется в элементе listA, почти всегда отделяетсяподчеркиваниями, но не всегда появляются в одной и той же позиции во всей строке;Таким образом, выполнение разделения ('_'), например, для каждого элемента, не всегда помещает строку 'id' в позицию [-1] или [-2] или [-3], хотя [-1] позаботитсяиз ~ 80% случаев.
3. Все идентификаторы уникальны, они не появляются более одного раза в любом списке;каждое имя файла уникально в списке A;каждый идентификатор никогда не появляется более чем в одном словаре.

Спасибо за интерес, проявленный ко всем до сих пор.

Answer 1

Прежде всего, вот обобщенные списки, помогающие с тестированием:

listA = ['/pathname/abdce_%s.ext' % str(x) for x in range(10000)]

listB = [{'id': str(number), "create_date": "23/05/2014"} for number in range(10000)]

hello = {j: i['create_date'] for j in listA for i in listB if i['id'] in j}

Выполнение этого с 10 000 значений заняло у моей машины в среднем 8,8 секунды.(9,5 секунд, если я напечатаю словарь после)

Теперь, если мы скомпилируем этот код в Cython (расширенный набор Python, работающий на C), для меня это время уменьшится до 4,4 секунды.

Смотрите код ниже

cpdef dict main():
    cdef int x
    cdef int number
    cdef char j
    cdef dict i

    listA = ['/pathname/abdce_%s.ext' % str(x) for x in range(10000)]

    listB = [{'id': str(number), "create_date": "23/05/2014"} for number in range(10000)]

    hello = {j: i['create_date'] for j in listA for i in listB if i['id'] in j}

    return hello

Answer 2

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

И match (ваш оригинал), и match2 (мой) распечатывают количество результатов, чтобы попытаться убедиться, что они работают одинаково.

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

Номера для 5000/10000 элементов на моем MBP:

• оригинал: 1.771 / 7.391
• оптимизировано: 0.054 / 0.203
• без удаленияиспользуемые теги (если это неприемлемое бизнес-правило): 0,917 / 3,789

---

import random
import timeit
import string

random.seed(42)


def genrand(n):
    return "".join(
        random.choice(string.ascii_lowercase + string.digits) for x in range(n)
    )


filenames = []
tags = []

for x in range(5000):
    id = genrand(8)
    filenames.append("/pathname/%s_%s.ext" % (genrand(6), id))
    if random.random() < 0.95:
        tags.append({"id": id, "date": "date for %s" % id})


def match():
    x = {j: i["date"] for j in filenames for i in tags if i["id"] in j}
    print(len(x))


def match2():
    x = {}
    available_tags = tags[:]
    for filename in filenames:
        for tag in available_tags:
            if tag["id"] in filename:
                x[filename] = tag
                available_tags.remove(tag)  # we've used this tag, remove it
                break
    print(len(x))


print(timeit.timeit(match, number=1))
print(timeit.timeit(match2, number=1))

Answer 3

Я вижу, к чему идут два комментария.Большой вопрос: нужно ли нам использовать in, потому что это необходимо, только если мы не знаем, где в строке пути указан идентификатор?Если он всегда находится в определенном месте, мы можем извлечь его и использовать поиск в постоянном времени:

def extract_id(path):
    # todo
ids = {item['id']: item['create_date'] for item in listB}
new_dict = {path: ids[extract_id(path)] for path in listA}

, что составляет всего O(N) в отличие от вашего текущего O(N**2).