Python: langsam verschachtelt für Schleife

Question

Ich muss eine optimale Auswahl von Medien, basierend auf bestimmten Einschränkungen herausfinden. Ich mache es in FOUR geschachtelt für Schleife und da es etwa O (n^4) Iterationen dauern würde, ist es langsam. Ich hatte versucht, es schneller zu machen, aber es ist immer noch verdammt langsam. Meine Variablen können so hoch wie ein paar Tausend sein.

Hier ist ein kleines Beispiel dafür, was ich zu tun versucht:

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. 

Es ist nicht für bis zu Hunderten von einzelnen Medientypen langsam war, aber würde für Tausende verlangsamen.

Andere Art und Weise habe ich versucht, ist:

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)] 

diese Weise ist es langsam auch für solche kleinen Zahlen.

Zwei Fragen:

1. Warum die zweite für kleine Zahlen langsam ist?
2. Wie kann ich mein Programm für große Zahlen (in Tausend) arbeiten lassen? Hier

ist die Version mit 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 

Es dauert 19,8 Sekunden mit diesen Zahlen zu beenden.

Answer 1

Aus den Kommentaren habe ich, dass Sie an einem Problem arbeiten, das als ILP umgeschrieben werden kann. Sie haben mehrere Einschränkungen und müssen eine (fast) optimale Lösung finden.

Jetzt sind ILPs ziemlich schwierig zu lösen, und Brute-Forcing wird schnell unpraktisch (wie Sie bereits gesehen haben). Aus diesem Grund gibt es in der Industrie mehrere wirklich clevere Algorithmen, die wirklich wunderbar funktionieren.

Für Python gibt es eine ganze Reihe von Schnittstellen, die sich an moderne Löser anschließen; für weitere Einzelheiten siehe z.B. diese SO post. Sie könnten auch einen Optimierer wie SciPy optimize in Betracht ziehen, aber diese Operationen machen im Allgemeinen keine ganzzahlige Programmierung.

Answer 2

Jede Operation in Python wird eine Billion mal langsam sein. Aber das ist nicht alles, was du tust. Wenn Sie versuchen, alle Billionen Elemente in einer einzigen Liste zu speichern, speichern Sie viele Daten im Speicher und manipulieren sie so, dass der Computer viel Arbeit aufwenden muss, um Speicher ein- und auszuwechseln, sobald er nicht mehr in den Arbeitsspeicher passt.

Die Art, wie Python-Listen funktionieren, ist, dass sie eine gewisse Menge an Speicher zuweisen, um die Elemente in der Liste zu speichern. Wenn Sie die Liste ausfüllen und mehr zuweisen müssen, reserviert Python doppelt so viel Speicher und kopiert alle alten Einträge in den neuen Speicherplatz. Das ist in Ordnung, solange es in den Speicher passt - obwohl es bei jeder Erweiterung des Speichers den gesamten Inhalt der Liste kopieren muss, muss es dies weniger häufig machen, da es die Größe verdoppelt. Das Problem tritt auf, wenn nicht genügend Arbeitsspeicher zur Verfügung steht und ungenutzter Speicher auf die Festplatte ausgelagert werden muss. Wenn es das nächste Mal versucht, die Größe der Liste zu ändern, muss es alle Einträge, die jetzt auf die Festplatte ausgelagert sind, von der Festplatte neu laden und dann alle wieder austauschen, um Speicherplatz für die neuen Einträge zu erhalten. Dadurch entstehen viele langsame Festplattenoperationen, die Ihrer Aufgabe im Weg stehen und sie noch mehr verlangsamen.

Müssen Sie wirklich jeden Artikel in einer Liste speichern? Was wirst du mit ihnen machen, wenn du fertig bist? Sie könnten sie vielleicht auf die Festplatte schreiben, während Sie gehen, anstatt sie in einer riesigen Liste zu sammeln, wenn Sie jedoch eine Billion davon haben, ist das immer noch eine sehr große Menge an Daten! Oder filtern Sie die meisten aus? Das wird helfen.

Alles, was gesagt, ohne das eigentliche Programm selbst zu sehen, ist es schwer zu wissen, ob Sie die Hoffnung haben, diese Arbeit durch eine erschöpfende Suche abzuschließen. Können alle Variablen gleichzeitig im Tausenderbereich liegen? Müssen Sie wirklich jede Kombination dieser Variablen berücksichtigen? Wenn max_disks == 2000, müssen Sie wirklich die Ergebnisse für i = 1731 von i = 1732 unterscheiden? Zum Beispiel könnten Sie vielleicht Werte von 1,2,3,4,5,10,20,30,50,50,100,200,300,500,1000,2000 betrachten? Oder gibt es stattdessen eine mathematische Lösung? Zählen Sie nur Gegenstände?