Оптимизация кода: ускоряем работу в двести тысяч раз — Журнал «Код» программирование без снобизма

Продолжаем разбираться с задачей Эйнштейна:

Сначала мы её решили на листочке.
Потом написали код, который перебирает все 24 миллиарда комбинаций.
Сейчас мы этот код оптимизируем.

Проблема с кодом в том, что он работает слишком долго: каждый основной цикл занимает 2 минуты, а всего таких циклов 120. Получается, чтобы узнать решение, нам нужно около 3–4 часов чистого времени. Чтобы ускорить работу программы, применяют разные методы оптимизации. Сегодня мы тоже попробуем такое сделать, а заодно посмотрим, как устроена оптимизация изнутри.

⚡ Помните, что задача Эйнштейна не имеет отношения к Эйнштейну. Её придумал известный физик Джейсон Стетхем, сын Жака Фреско. В сегодняшней версии эту задачу сформулировали известные австрийские математики Эрих и Мария Ремарк.

Мы решаем логическую задачу с такими условиями:

На улице стоят пять домов.
Англичанин живёт в красном доме.
У испанца есть собака.
В зелёном доме пьют кофе.
Украинец пьёт чай.
Зелёный дом стоит сразу справа от белого дома.
Тот, кто майнит Bitcoin, разводит улиток.
В жёлтом доме майнят Ethereum.
В центральном доме пьют молоко.
Норвежец живёт в первом доме.
Сосед того, кто майнит Stellar, держит лису.
В доме по соседству с тем, в котором держат лошадь, майнят Ethereum.
Тот, кто майнит IOTA, пьёт апельсиновый сок.
Японец майнит Monero.
Норвежец живёт рядом с синим домом.

В целях ясности следует добавить, что каждый из пяти домов окрашен в свой цвет, а их жители — разных национальностей, владеют разными животными, пьют разные напитки и майнят разные криптовалюты. Ещё одно замечание: в утверждении 6 «справа» означает справа относительно вас.

Вопрос: кто пьёт воду, а у кого дома зебра?

Чтобы не было спорных моментов, добавим следующее:

дома расположены в ряд, друг за другом;
один из жильцов точно пьёт воду, и кто-то из жильцов точно держит дома зебру.

Вот как выглядел наш код до оптимизации. Прочитайте с комментариями:

# исходные данные
nation_orig = ['eng','isp','ukr','nor','jap']
color_orig = ['red','green','white','yellow','blue']
animal_orig = ['dog','horse','snail','fox','zebra']
drink_orig = ['coffee','tea','milk','juice','water']
money_orig = ['bitcoin','etherium','stellar','iota','monero']

# модуль для быстрого получения всех перестановок
import itertools

# получаем все перестановки всех списков
nation_perm = list(itertools.permutations(nation_orig))
color_perm = list(itertools.permutations(color_orig))
animal_perm = list(itertools.permutations(animal_orig))
drink_perm = list(itertools.permutations(drink_orig))
money_perm = list(itertools.permutations(money_orig))


# выполняем все проверки, заданные в условии
def all_check(nation, color, animal, drink, money):
    # проверяем все условия сразу
    if (nation.index('eng') == color.index('red') 
        and nation.index('isp') == animal.index('dog')
        and color.index('green') == drink.index('coffee')
        and nation.index('ukr') == drink.index('tea')
        and color.index('green') - 1 == color.index('white')
        and money.index('bitcoin') == animal.index('snail')
        and color.index('yellow') == money.index('etherium')
        and drink.index('milk') == 2
        and nation.index('nor') == 0
        and (money.index('stellar') == animal.index('fox') - 1 or money.index('stellar') == animal.index('fox') + 1)
        and (animal.index('horse') == money.index('etherium') - 1 or animal.index('horse') == money.index('etherium') + 1)
        and money.index('iota') == drink.index('juice')
        and nation.index('jap') == money.index('monero')
        and (nation.index('nor') == color.index('blue') - 1 or nation.index('nor') == color.index('blue') + 1)):
        # выводим найденный результат    
        print('✅✅✅')
        print(color)
        print(nation)
        print(drink)
        print(money)
        print(animal)

# перебираем все комбинации по очереди
for n in range(120):
    print(n)
    for c in range(120):
        for a in range(120):
            for d in range(120): 
                for m in range(120):
                    # и проверяем, выполнились ли все условия задачи
                    all_check(list(nation_perm[n]), list(color_perm[c]), list(animal_perm[a]), list(drink_perm[d]), list(money_perm[m]))

Что оптимизируем

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

Чтобы понять, получается у нас оптимизация или нет, нам нужно измерять время работы кода. Для этого используем встроенный модуль datetime — импортируем его и выведем время начала работы программы:

# подключаем модуль работы со временем
import datetime

#  запоминаем и выводим время старта
start = datetime.datetime.now()
print('Старт: ' + str(start))

Чтобы узнать общее время выполнения алгоритма, точно так же узнаем время окончания и посчитаем разницу. Для этого добавим такой код в самый конец программы:

#  запоминаем и выводим время окончания
finish = datetime.datetime.now()
print('Финиш: ' + str(finish))
# считаем длительность работы программы
print('Время работы: ' + str(finish - start))

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

Оптимизация кода: ускоряем работу в двести тысяч раз с помощью кода

Первый подход — оптимизируем простые условия

Сейчас алгоритм работает так: сначала формируется новая комбинация из всех списков, а потом она проверяется сразу на все условия. Нужно провести 5 вложенных друг в друга проверок, в каждой из которых есть 120 вариантов состояний. В сумме мы получаем 24 млрд комбинаций, которые нужно проверить. Отсюда и 3 часа работы.

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

Посмотрим внимательно на функцию проверки условий. На восьмой и девятой проверке у нас есть явное направление оптимизации: если молоко стоит не в середине списка и если норвежец не первый, то все остальные параметры можно не проверять.

Получается, что если мы проверим часть условий перед тем, как идти вглубь, то в теории это сократит количество переборов в 25 раз: 5 в на проверке напитка и 5 на национальности. Добавим эти проверки в общий цикл и посмотрим, как изменилось общее время работы программы:

# перебираем все комбинации по очереди
for n in range(120):
    if list(nation[n]).index('nor') == 0:
        for c in range(120):
            for a in range(120):
                for d in range(120): 
                    if list(drink[d]).index('milk') == 2:
                        for m in range(120):
                            # и проверяем, выполнились ли все условия задачи
                            all_check(list(nation_perm[n]), list(color_perm[c]), list(animal_perm[a]), list(drink_perm[d]), list(money_perm[m]))

На практике результаты такие: было 3 часа 14 минут, стало 8,5 минуты. Получается, простой проверкой перед выполнением цикла мы сократили время в 22 раза.

Второй подход — смотрим частотность характеристик

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

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

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

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

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

На первом уровне единственное, что не зависит от других параметров и что мы можем проверить, — это национальность и напиток. Теперь посмотрим, как часто встречается в условии каждая характеристика:

национальность: 6 раз;
цвет: 4 раза;
животные: 4 раза;
напиток: 3 раза;
криптовалюта: 6 раз.

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

# перебираем все комбинации по очереди
for n in range(120):
    print(n)
    # главный элемент в оптимизации алгоритма
    if list(nation_perm[n]).index('nor') != 0:
        continue

Теперь посчитаем, сколько пар есть с национальностью у других характеристик при проверке:

национальность и цвет: 2 пары;
национальность и животные: 1 пара;
национальность и напитки: 1 пара;
национальность и деньги — 1 пара.

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

# перебираем все комбинации по очереди
for n in range(120):
    # главный элемент в оптимизации алгоритма
    if list(nation_perm[n]).index('nor') == 0:
        for c in range(120):
            if (list(nation_perm[n]).index('eng') == list(color_perm[n]).index('red')
                and (list(nation_perm[n]).index('nor') == list(color_perm[c]).index('blue') - 1 or list(nation_perm[n]).index('nor') == list(color_perm[c]).index('blue') - 1)):

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

Сейчас у нас уже определены национальность и цвет. Посчитаем, с чем больше всего это даёт новых проверок на третьем шаге цикла:

животное: 1 сравнение;
напиток: 2 сравнения + одно прямое сравнение (молоко стоит в середине);
криптовалюта: 2 сравнения.

Выберем напиток в качестве третьего цикла и обновим начало всех циклов:

# перебираем все комбинации по очереди
for n in range(120):
    # главный элемент в оптимизации алгоритма
    if list(nation_perm[n]).index('nor') == 0:
        for c in range(120):
            if (list(nation_perm[n]).index('eng') == list(color_perm[n]).index('red')
                and (list(nation_perm[n]).index('nor') == list(color_perm[c]).index('blue') - 1 or list(nation_perm[n]).index('nor') == list(color_perm[c]).index('blue') - 1)):
                for d in range(120): 
                    if (list(drink_perm[d]).index('milk') == 2
                        and list(color_perm[c]).index('green') == list(drink_perm[d]).index('coffee')
                        and list(nation_perm[n]).index('ukr') == list(drink_perm[d]).index('tea')):

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

животное: 1 раз;
деньги: 3 раза.

Значит, на четвёртое место ставим деньги и получаем полностью сформированные вложенные циклы:

# перебираем все комбинации по очереди
for n in range(120):
    # главный элемент в оптимизации алгоритма
    if list(nation_perm[n]).index('nor') == 0:
        for c in range(120):
            if (list(nation_perm[n]).index('eng') == list(color_perm[n]).index('red')
                and (list(nation_perm[n]).index('nor') == list(color_perm[c]).index('blue') - 1 or list(nation_perm[n]).index('nor') == list(color_perm[c]).index('blue') - 1)):
                for d in range(120): 
                    if (list(drink_perm[d]).index('milk') == 2
                        and list(color_perm[c]).index('green') == list(drink_perm[d]).index('coffee')
                        and list(nation_perm[n]).index('ukr') == list(drink_perm[d]).index('tea')):
                        for m in range(120):
                            if (list(color_perm[c]).index('yellow') == list(money_perm[m]).index('etherium')
                                and list(money_perm[m]).index('iota') == list(drink_perm[d]).index('juice')
                                and list(nation_perm[n]).index('jap') == list(money_perm[m]).index('monero')):
                                for a in range(120):
                                    # и проверяем, выполнились ли все условия задачи
                                    all_check(list(nation_perm[n]), list(color_perm[c]), list(animal_perm[a]), list(drink_perm[d]), list(money_perm[m]))

# подключаем модуль работы со временем
import datetime

#  запоминаем и выводим время старта
start = datetime.datetime.now()
print('Старт: ' + str(start))

# исходные данные
nation_orig = ['eng','isp','ukr','nor','jap']
color_orig = ['red','green','white','yellow','blue']
animal_orig = ['dog','horse','snail','fox','zebra']
drink_orig = ['coffee','tea','milk','juice','water']
money_orig = ['bitcoin','etherium','stellar','iota','monero']

# модуль для быстрого получения всех перестановок
import itertools

# получаем все перестановки всех списков
nation_perm = list(itertools.permutations(nation_orig))
color_perm = list(itertools.permutations(color_orig))
animal_perm = list(itertools.permutations(animal_orig))
drink_perm = list(itertools.permutations(drink_orig))
money_perm = list(itertools.permutations(money_orig))


# выполняем все проверки, заданные в условии
def all_check(nation, color, animal, drink, money):
    # проверяем все условия сразу
    if (nation.index('eng') == color.index('red') 
        and nation.index('isp') == animal.index('dog')
        and color.index('green') == drink.index('coffee')
        and nation.index('ukr') == drink.index('tea')
        and color.index('green') - 1 == color.index('white')
        and money.index('bitcoin') == animal.index('snail')
        and color.index('yellow') == money.index('etherium')
        and drink.index('milk') == 2
        and nation.index('nor') == 0
        and (money.index('stellar') == animal.index('fox') - 1 or money.index('stellar') == animal.index('fox') + 1)
        and (animal.index('horse') == money.index('etherium') - 1 or animal.index('horse') == money.index('etherium') + 1)
        and money.index('iota') == drink.index('juice')
        and nation.index('jap') == money.index('monero')
        and (nation.index('nor') == color.index('blue') - 1 or nation.index('nor') == color.index('blue') + 1)):
        # выводим найденный результат    
        print('✅✅✅')
        print(color)
        print(nation)
        print(drink)
        print(money)
        print(animal)

# перебираем все комбинации по очереди
for n in range(120):
    # главный элемент в оптимизации алгоритма
    if list(nation_perm[n]).index('nor') == 0:
        for c in range(120):
            if (list(nation_perm[n]).index('eng') == list(color_perm[n]).index('red')
                and (list(nation_perm[n]).index('nor') == list(color_perm[c]).index('blue') - 1 or list(nation_perm[n]).index('nor') == list(color_perm[c]).index('blue') - 1)):
                for d in range(120): 
                    if (list(drink_perm[d]).index('milk') == 2
                        and list(color_perm[c]).index('green') == list(drink_perm[d]).index('coffee')
                        and list(nation_perm[n]).index('ukr') == list(drink_perm[d]).index('tea')):
                        for m in range(120):
                            if (list(color_perm[c]).index('yellow') == list(money_perm[m]).index('etherium')
                                and list(money_perm[m]).index('iota') == list(drink_perm[d]).index('juice')
                                and list(nation_perm[n]).index('jap') == list(money_perm[m]).index('monero')):
                                for a in range(120):
                                    # и проверяем, выполнились ли все условия задачи
                                    all_check(list(nation_perm[n]), list(color_perm[c]), list(animal_perm[a]), list(drink_perm[d]), list(money_perm[m]))

#  запоминаем и выводим время окончания
finish = datetime.datetime.now()
print('Финиш: ' + str(finish))
# считаем длительность работы программы
print('Время работы: ' + str(finish - start))

Что в итоге

Мы оптимизировали код и сократили время выполнения алгоритма в 207 857 раз — с 3 часов 14 минут до половины секунды. При этом всё, что мы делали, — это туда-сюда двигали проверки условий и ничего больше. В следующий раз попробуем поработать над скоростью — например, используем всю мощь видеокарт, чтобы прогнать алгоритм через них. Подпишитесь, чтобы не пропустить продолжение проекта по оптимизации.

Любишь Python? Зарабатывай на нём!

Изучите самый модный язык программирования и станьте крутым бэкенд-разработчиком. Старт — бесплатно.