Эффективно найти все подстроки в списке строк

Question

Представьте себе большой pandas фрейм данных, заданный

import string
import random
import pandas as pd

n = 10000

def id_generator(chars=string.ascii_uppercase + string.digits, size=6):
    return ''.join(random.choice(chars) for _ in range(size))


mfr = [id_generator(size=random.randint(3, 20)) for _ in range(n)]
desc = [id_generator(size=random.randint(3, 50)) +
        (' ' + random.choice(mfr) if random.random() > 0.8 else '') for _ in range(n)]

df = pd.DataFrame({'id': range(n), 'mfr': mfr, 'desc': desc}).set_index('id')

, что дает

                   mfr                                               desc
id                                                                       
0              XACYXAB                            6JYLELA2WUR1MVOS5 1VKF5
1   JOLB082YROZO97PGS5  YWWTUR4A19JKVB5HLBQ9RKVHNJ10J08SQZZHSLG2IB 4MK...
2                 88QO                            DUV566OX9OLSLZJZR9CRWNT
3        DW4S6WTRGWJVE                                                MFE
4             Z2I5VOWK                 IX5DY8GLSPGD5R8W350DZ6ED8CGN2C20GA

Для каждого значения mfr я хочу найти desc s, которые содержат значение в качестве подстроки, и вернуть соответствующий id . Это можно сделать в pandas по

df['matches'] = df.mfr.map(lambda x: df.index[df.desc.str.contains(x)].tolist())

что дает желаемый результат

                   mfr                                               desc matches
id                                                                               
0              XACYXAB                            6JYLELA2WUR1MVOS5 1VKF5      []
1   JOLB082YROZO97PGS5  YWWTUR4A19JKVB5HLBQ9RKVHNJ10J08SQZZHSLG2IB 4MK...      []
2                 88QO                            DUV566OX9OLSLZJZR9CRWNT      []
3        DW4S6WTRGWJVE                                                MFE      []
4             Z2I5VOWK                 IX5DY8GLSPGD5R8W350DZ6ED8CGN2C20GA      []
5   UPCTNHIF2BOAGOB2WL                  MB2GCMRLQTYD1YRGBJILQ0CZ3LCR2FYHX      []
6              L8K9E3T                                         WW0M73FPD4      []
7                  ZQT               NWNMFRB1ZTMKUVXZH0BFTSIOC3R84XSPRLJS   [532]
8       SPEJJW1JGGSG8B                           7NYL32KTN8ZRNYDV2Z NK4T3      []
9               3WWZ46                Z3HVNIBSQVXJG5487YX7EA89SYPHN5M3BJ2      []

Проблема в том, что мне нужен высокопроизводительный алгоритм. Предоставленный не масштабируется хорошо. Вопрос в том, существуют ли хорошие масштабируемые алгоритмы для этой задачи? Для справки последний вызов занимает ~ 42 секунды на приличном рабочем столе с n = 10000.

Answer 1

Использовать вложенные list comprehension:

n = 1000

d = df['desc'].to_dict()

In [117]: %timeit df['matches1'] = [[k for k, v in d.items() if x in v] for x in df.mfr]
80.8 ms ± 2.81 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [118]: %timeit df['matches'] = df.mfr.map(lambda x: df.index[df.desc.str.contains(x)].tolist())
877 ms ± 27.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)