Neuer Solver senkt den Spitzen-RAM von PyTorch um das 20-Fache
0/1 Knapsack Problem in PyTorch
PyTorch wählt beim Memory Planning aus, welche Operationen gespeichert und welche neu berechnet werden – ein 0/1-Knapsack-Problem. Der neue Solver dp_knapsack_sliding_hirschberg kombiniert Sliding-Window- und Hirschberg-Trick: Statt einer vollen DP-Tabelle der Form (Anzahl Items, max. Gewicht) braucht er nur zwei Zeilen. Auf einem Rechner mit 64 GB RAM schafft er 2000 Items, während dp_knapsack schon bei 100 abstürzt.
Auf meinem Rechner mit 64 GB RAM stürzt dp_knapsack bei Problemen mit 100 Items ab, während dp_knapsack_sliding_hirschberg Probleme mit 2000 Items innerhalb dieses RAM-Budgets bewältigt.