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

Question

Мне нужно найти оптимальный выбор носителя, основанный на определенных ограничениях. Я делаю это в четырехмерном вложенном цикле, и поскольку это потребует итераций 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 секунд, чтобы закончить с этими числами.

Answer 1

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

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

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

Answer 2

Выполнение любой операции в 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? Или, может быть, есть математическое решение? Вы просто считаете предметы?