Ускоряем алгоритм по обработке таблиц в Python

Всем привет! Делюсь лайфхаками по обработке таблиц с помощью нюансов использования памяти Python.

Часто в нашей работе приходится сталкиваться с обработкой данных для последующего исследования и анализа. Зачастую алгоритм обработки очень прост: найти вхождения подстроки в строку, проставить флаги в исходном дата фрейме в зависимости от условий, подсчитать количественные характеристики или метрики.

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

Рассмотрим такую задачу есть 2 таблицы: в одной находится информация с запросами, где в одном столбце находится идентификатор клиента, а в другом тело запроса; в другой таблице находятся список идентификаторов запросов, которые указываются в теле запроса из предыдущей таблицы.

Пример

Первая табличка выглядит так (отобрали интересующий столбец):

Пример содержания строки: «Запрос: 43ba-b25d -1ddbeae1-aa60-230b3aa3da8f от 1823-10-06. Нотариус: Иванов Иван Иванович», однако некоторые строки не типизированы и могут представлять из себя однострочный запрос: «H18B11zap04500057-007438459-00-071119.rtf»

Вторая табличка выглядит так (также интересующий столбец):

Задача была в том, чтобы найти вхождения строки из второй таблицы в первую. В первой таблице 556424 строк, во второй 496425 строк.

Казалось бы, задача легкая и понятная. Но так ли это? Давайте разбираться.

Для начала, как и в любой подобной обработке, необходимо импортировать нужные библиотеки, считать таблички и добавить колонку с флагами (по умолчанию равную 0).

Теперь переходим к самому интересному – написанию алгоритма поиска. Первое что приходит на ум - написать «в лоб» алгоритм для поиска подстроки в строке, и затем, там, где совпадение было, выставить флаг 1.

Вариант работает очень долго, приблизительно 12988 часов или 541 день.

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

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

также в нашей получившейся переменной все еще много лишнего, из нее нам нужен только номер запроса, давайте и выделим его:

Получаем на выходе словарик, где ключ – очищенный номер, а значение – исходная строка. Теперь мы можем непосредственно сравнить словарик с исходным списком из второй таблицы:

Сравниваем два листа, ищем в целевом столбце вхождения target, при нахождении добавляем в словарь и ставим 1

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

Далее в результат записываем значение словаря фильтр (исходную строку) и присваиваем 1.

Дальше логично просто пройтись по всей первой табличке и если значение есть в result – ставим 1, если нет – 0

Вроде бы все хорошо, однако время работы все еще достаточно большое – около 1,5 часов.

Однако есть одна очень полезная функция, для который мы и делали именно словарик, а не просто список – map(), которая возвращает колонку с новыми значениями (в нашем случае – flag).

На весь код таким решением:

Выполняется данный код всего за несколько секунд. Эта функция применяется к колонке датафрейма по которому делаем фильтр, аргументом функции является словарь, где ключ – значение, которое встречается в колонке, к которой применяется функция, а значение – значение, которое будет возвращаться в новую колонку.

Код, который представлен выше выполняется быстро и понятен, однако содержит много строчек и «лишних» переменных. Есть более лаконичное и короткое решение. Нам понадобится опять словарь исходных – очищенных строк, но только теперь ключом будет строка, а значением – очищенная строка. Совсем необязательно создавать словарь, можно реализовать через лямбда функцию, только необходимо применить их с большей осторожностью, так как они являются не просто читаемыми для других. Но давайте воспользуемся лямбда функцией, а результат запишем сразу в новый столбец в первой таблице, в нем будут содержаться очищенные значения:

Затем вместо построчных сравнений вхождения подстроки и создания дополнительного словаря можно просто применить функцию merge:

На выходе получаем res_df:

То есть напротив значений, которые нашлись во второй таблице - будут значения, а где не нашлись – Nan. Время выполнения такого кода занимает несколько секунд, а размер составляет всего 2 строки.

Pandas.merge() – базовая функция для всех слияний или объединений таблиц. Также помимо этой функции существует функция join(). Merge можно использовать двумя способами: df1.merge(right = df2) или pandas.merge(left=df1, right=df2), а join – df1.join(df2,…).

Основные различия между merge и join заключаются в следующих пунктах:

В целом эти 2 функции взаимозаменяемы, по времени исполнения они не отличаются, главное помнить о небольших различиях и использовать их правильно.
Таким образом, зная некоторые нюансы использования памяти Python, что словари на поиск работают всегда в разы быстрее, чем поиск по списку, а также нескольких полезных функций, время выполнения нашего код сократилось более чем в 500 раз.
Некоторые шаги можно объединить для уменьшения количества кода. В данной публикации рассмотрено несколько вариантов решения для полного понимания процесса и наглядности.
P.S если в столбце к которому применяем функцию map() будут значения, которых не будет в словаре, то в новом столбце будет Nan. Их легко заменить на нужные значения функцией fillna.