Python: медленный вложенный цикл for

Мне нужно найти оптимальный выбор медиа, исходя из определенных ограничений. Я делаю это в ЧЕТЫРЕХ вложенных циклах for, и, поскольку это займет около O (n ^ 4) итераций, это медленно. Я пытался сделать это быстрее, но это все еще чертовски медленно. Мои переменные могут достигать нескольких тысяч.

Вот небольшой пример того, что я пытаюсь сделать:

    max_disks = 5
    max_ssds = 5
    max_tapes = 1
    max_BR    = 1
    allocations = []
    for i in range(max_disks):
     for j in range(max_ssds):
        for k in range(max_tapes):
            for l in range(max_BR):
                allocations.append((i,j,k,l)) # this is just for example. In actual program, I do processing here, like checking for bandwidth and cost constraints, and choosing the allocation based on that.

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

Другой способ, которым я пробовал:

    max_disks = 5
    max_ssds = 5
    max_tapes = 1
    max_BR    = 1

    allocations = [(i,j,k,l) for i in range(max_disks) for j in range(max_ssds) for k in range(max_tapes) for l in range(max_BR)]

Таким образом, это медленно даже для таких небольших чисел.

Два вопроса:

  1. Почему второй медленный для небольших чисел?
  2. Как я могу заставить свою программу работать с большими числами (в тысячах)?

Вот версия с itertools.product

            max_disks = 500
            max_ssds = 100
            max_tapes = 100
            max_BR    = 100
            # allocations = []
            for i, j, k,l in itertools.product(range(max_disks),range(max_ssds),range(max_tapes),range(max_BR)):
                pass

Чтобы финишировать с этими числами, требуется 19,8 секунды.


python performance constraint-programming linear-programming
person Community    schedule 19.09.2016    source источник
comment
Первый пример с пониманием списка быстрее, чем второй пример. В остальном они эквивалентны, но поиск атрибута allocations.append и последующий вызов метода замедляют вложенный цикл. Вы, вероятно, захотите вместо этого взглянуть на itertools.product() и не создавать огромный объект списка со всеми возможными комбинациями (вместо этого обрабатывайте элементы один за другим).   -  person Martijn Pieters    schedule 19.09.2016
comment
Я тоже пробовал itertools.product(). Но и это не сработало для тысяч.   -  person    schedule 19.09.2016
comment
Вы настаиваете на составлении списка распределений? Вы уже знаете общую структуру списка, который вы создаете, поэтому не можете ли вы обрабатывать распределения по отдельности?   -  person N. Wouda    schedule 19.09.2016
comment
Добавление к списку, который я использовал здесь только для примера. На самом деле в самом внутреннем цикле я выполняю такие операции, как проверка пропускной способности, которую обеспечивает выделение, и принимаю решение о сохранении выделения или нет.   -  person    schedule 19.09.2016
comment
@Pretty: «не сработало» ничего нам не говорит. itertools.product() еще быстрее, чем любой опубликованный вами метод, и непобедим, если вы сначала не материализуете все в список. Возможно, вы хотите показать, что еще вы делаете с комбинациями, которые вы создаете? Зачем вообще нужно создавать такое большое количество кортежей в списке?   -  person Martijn Pieters    schedule 19.09.2016

Ответы (2)


arrow_upward
3
arrow_downward

Из комментариев я понял, что вы работаете над проблемой, которую можно переписать как ILP. У вас есть несколько ограничений, и вам нужно найти (почти) оптимальное решение.

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

Для Python существует довольно много интерфейсов, которые подключаются к современным решателям; для получения дополнительной информации см. например, этот публикацию SO. Вы также можете использовать оптимизатор, например SciPy optimize, но они обычно не занимаются целочисленным программированием.

person N. Wouda    schedule 19.09.2016

arrow_upward
0
arrow_downward

Выполнение любой операции в Python триллион раз будет медленным. Однако это еще не все, чем вы занимаетесь. Пытаясь сохранить все триллионы элементов в одном списке, вы храните много данных в памяти и манипулируете ими таким образом, что у компьютера возникает много работы по замене памяти, когда она больше не помещается в ОЗУ.

Работа списков Python заключается в том, что они выделяют некоторый объем памяти для хранения элементов в списке. Когда вы заполните список и ему нужно выделить больше, Python выделит вдвое больше памяти и скопирует все старые записи в новое пространство для хранения. Это нормально, пока он помещается в памяти — хотя ему приходится копировать все содержимое списка каждый раз, когда он расширяет хранилище, он должен делать это реже, поскольку он продолжает удваивать размер. Проблема возникает, когда заканчивается память и приходится выгружать неиспользуемую память на диск. В следующий раз, когда он попытается изменить размер списка, он должен перезагрузить с диска все записи, которые теперь выгружены на диск, а затем снова выгрузить их обратно, чтобы получить место для записи новых записей. Таким образом, это создает множество медленных дисковых операций, которые будут мешать вашей задаче и замедлять ее еще больше.

Вам действительно нужно хранить каждый элемент в списке? Что ты собираешься делать с ними, когда закончишь? Возможно, вы могли бы записать их на диск по ходу дела вместо того, чтобы накапливать их в гигантском списке, хотя, если у вас их триллион, это все равно очень большой объем данных! Или, может быть, вы отфильтровываете большинство из них? Это поможет.

Все это говорит о том, что, не видя самой программы, трудно понять, есть ли у вас надежда завершить эту работу исчерпывающим поиском. Могут ли все переменные быть в масштабе тысяч одновременно? Вам действительно нужно учитывать каждую комбинацию этих переменных? Когда max_disks==2000, вам действительно нужно отличать результаты для i=1731 от i=1732? Например, возможно, вы могли бы рассмотреть значения i 1,2,3,4,5,10,20,30,40,50,100,200,300,500,1000,2000? Или, может быть, вместо этого есть математическое решение? Вы просто считаете предметы?

person Weeble    schedule 19.09.2016