Управление памятью

В задании, которое Жасмин и я недавно выполнили для моего инструктора Алана Дэвиса в Make School, был дан большой список телефонных маршрутов, состоящий из их стандартных префиксов и стоимости.

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

Project Readme

Попытки

Список

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

Словарь

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

Trie

Жасмин сказала, что попытки могут быть хорошим решением. Подробнее о них вы можете прочитать здесь. По сути, это способ хранения последовательностей значений, чаще всего строк.

К нашему ужасу, он использовал 3 ГБ ОЗУ для набора данных из 10 миллионов маршрутов! Когда Жасмин попыталась собрать свой собственный компьютер, на ее ноутбуке с 8 ГБ оперативной памяти произошел сбой.

Пришло время выяснить, куда уходит вся наша оперативная память.

Советы и ресурсы

Благодаря моим попыткам оптимизировать память у меня есть несколько указателей.

Пимплер

Pympler - мощный инструмент для анализа использования памяти.

Pympler.asizeof.asizeof

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

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

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

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

Намного больше

У Pympler в запасе гораздо больше, я настоятельно рекомендую просмотреть их документацию и посмотреть, есть ли что-нибудь полезное.

следомаллок

Python 3.4 и выше имеет встроенный трассировщик памяти, но я признаю, что у меня не так много опыта с ним.

Используйте __slots__!

Слоты в Python - довольно быстрый способ уменьшить использование памяти объектом. По умолчанию Python использует словари для хранения атрибутов класса, которые вы найдете в переменной __dict__.

Если вместо этого вы явно определяете, какие переменные с помощью __slots__ будет иметь ваш объект, вы можете сэкономить существенный объем памяти, который окупается за счет рекурсивных структур данных, таких как попытки.

Использование слотов более чем вдвое сократило использование памяти, сохраняя при этом те же данные.

По умолчанию нет

В своих попытках я понял, что есть много моментов, когда в Trie не будет никаких подзаголовков, но я все же составил для них список.

Хотя есть небольшой компромисс, я считаю, что в ситуациях, когда у вас есть 4,6 миллиона одинаковых объектов, стоит установить для переменных по умолчанию значение None и создавать их только при необходимости.

Вы можете видеть, что при более чем 4 миллионах узлов размер пустых словарей и пустых списков может увеличиваться невероятно быстро.

Создавать структуры данных следует только тогда, когда они используются.

Используйте меньшие типы

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

Вложенные словари - обычное дело, но что, если ключи предсказуемы?

В нашей проблеме с телефонным номером я понял, что будет всего 11 символов «+1234567890», так почему я должен использовать структуру данных, оптимизированную для произвольных ключей?

Я решил, что стоит создать «преобразователь», который преобразует символ в индекс в списке.

def __init__(self, keys = None, items = None, _value = None, _mapper =  None):
  if _mapper:
    self._mapper = _mapper
  elif keys:
    self._mapper = {item: index for index, item in enumerate(keys)}
  else:
    raise ValueError('keys or _mapper must be provided')
self._subtries = None

Это позволяет мне сгенерировать сопоставитель в корне и передать его вниз. Затем я могу использовать его для получения индекса того, где должен находиться Trie. Это была безусловно одна из лучших оптимизаций, которые я сделал, и уменьшил использование памяти примерно с 3 ГБ до 1,5 ГБ.

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

Загляните в наше репо, если хотите увидеть наше решение проблемы с телефонными номерами.

Я ищу стажировку, не бойтесь обращаться к нам! Мой LinkedIn

Первоначально опубликовано на https://blog.dacio.dev 15 мая 2019 г.