У меня есть список имен (строк), разделенных на слова. Есть 8 миллионов имен, каждое имя состоит из 20 слов (токенов). Количество уникальных токенов - 2,2 миллиона. Мне нужен эффективный способ найти все имена, содержащие хотя бы одно слово из запроса (которое может содержать также до 20 слов, но обычно только несколько).
Мой текущий подход использует Python Pandas и выглядит так (далее называемый original):
>>> df = pd.DataFrame([['foo', 'bar', 'joe'],
['foo'],
['bar', 'joe'],
['zoo']],
index=['id1', 'id2', 'id3', 'id4'])
>>> df.index.rename('id', inplace=True) # btw, is there a way to include this into prev line?
>>> print df
0 1 2
id
id1 foo bar joe
id2 foo None None
id3 bar joe None
id4 zoo None None
def filter_by_tokens(df, tokens):
# search within each column and then concatenate and dedup results
results = [df.loc[lambda df: df[i].isin(tokens)] for i in range(df.shape[1])]
return pd.concat(results).reset_index().drop_duplicates().set_index(df.index.name)
>>> print filter_by_tokens(df, ['foo', 'zoo'])
0 1 2
id
id1 foo bar joe
id2 foo None None
id4 zoo None None
В настоящее время такой поиск (по полному набору данных) занимает 5.75 с на моей (довольно мощной) машине. Я бы хотел ускорить его, по крайней мере, 10 раз.
Мне удалось добраться до 5.29s, сжимая все столбцы в один и выполнив поиск по нему (далее называемый original, squeezed):
>>> df = pd.Series([{'foo', 'bar', 'joe'},
{'foo'},
{'bar', 'joe'},
{'zoo'}],
index=['id1', 'id2', 'id3', 'id4'])
>>> df.index.rename('id', inplace=True)
>>> print df
id
id1 {foo, bar, joe}
id2 {foo}
id3 {bar, joe}
id4 {zoo}
dtype: object
def filter_by_tokens(df, tokens):
return df[df.map(lambda x: bool(x & set(tokens)))]
>>> print filter_by_tokens(df, ['foo', 'zoo'])
id
id1 {foo, bar, joe}
id2 {foo}
id4 {zoo}
dtype: object
Но это еще не достаточно быстро.
Другим решением, которое, как представляется, легко реализовать, является использование многопроцессорности Python (потоки не должны здесь помочь из-за GIL, и нет ввода-вывода, правильно?). Но проблема заключается в том, что большой файл данных необходимо скопировать в каждый процесс, который занимает всю память. Другая проблема заключается в том, что мне нужно много раз вызывать filter_by_tokens в цикле, поэтому он копирует данные в каждый вызов, что неэффективно.
Обратите внимание, что слова могут встречаться много раз в именах (например, наиболее популярное слово имеет место в 600 тыс. раз в именах), поэтому обратный индекс будет огромным.
Каков хороший способ написать это эффективно? Решение Python предпочтительнее, но я также открыт для других языков и технологий (например, баз данных).
UPD: Я измерил время выполнения своих двух решений и 5 решений, предложенных @piRSquared в ответе . Вот результаты (tl; dr лучше всего - улучшение 2x):
+--------------------+----------------+
| method | best of 3, sec |
+--------------------+----------------+
| original | 5.75 |
| original, squeezed | 5.29 |
| zip | 2.54 |
| merge | 8.87 |
| mul+any | MemoryError |
| isin | IndexingError |
| query | 3.7 |
+--------------------+----------------+
mul+any дает MemoryError на d1 = pd.get_dummies(df.stack()).groupby(level=0).sum() (на компьютере с оперативной памятью 128 ГБ).
isin дает IndexingError: Unalignable boolean Series key provided на s[d1.isin({'zoo', 'foo'}).unstack().any(1)], по-видимому, потому что форма df.stack().isin(set(tokens)).unstack() немного меньше формы исходного кадра данных (8.39M против 8.41M строк), не знаю, почему и как это исправить.
Обратите внимание, что машина, которую я использую, имеет 12 ядер (хотя я упомянул некоторые проблемы с распараллеливанием выше). Все решения используют одно ядро.
Заключение (на данный момент): есть улучшение 2.1x с помощью решения zip (2.54s) vs original squeezed (5.29s). Это хорошо, хотя я старался хотя бы на 10 раз улучшить, если это возможно. Поэтому я оставляю (по-прежнему замечательный) ответ @piRSquared неприемлемым на данный момент, чтобы приветствовать дополнительные предложения.
