Dividere una lista di numeri in una lista più piccola con "somma" approssimativamente uguale

Question

Eseguo circa 2000 test sulla griglia, ogni test viene eseguito come compito separato sulla griglia. I test hanno tempi di avvio piuttosto grandi. L'esecuzione totale richiede 500 ore, termina in meno di 10 ore sul nodo 60 SunGridEngine. Il tempo di esecuzione dei test varia da 5 minuti a 90 minuti. La combinazione di test senza molta intelligenza ha dato un guadagno in termini di prestazioni. Vorrei creare "compiti" di dimensioni approssimativamente uguali. Come posso farlo?

(quello che facciamo oggi:. Ordinamento tutti i test e continuare ad aggiungere fino alla somma del tempo di esecuzione è di circa 5 ore alla ricerca di qualcosa di meglio)

Answer 1

Fare questo in modo ottimale è NP-completo. Questa è una variazione di partition problem, che è un caso speciale di subset sum problem, che a sua volta è un caso speciale di knapsack problem.

Nel tuo caso probabilmente non hai bisogno di una soluzione esatta, quindi puoi probabilmente usare qualche euristica per ottenere qualcosa "abbastanza buono" in un ragionevole lasso di tempo. Vedere la sezione Methods della pagina dei problemi delle partizioni per una descrizione di alcuni approcci.

Answer 2

Il tuo problema sembra un po 'come un problema di pianificazione del negozio. Esistono diversi tipi di approcci di sequenziamento, alcuni dei quali sono descritti here. Ad esempio, l'ordinamento in ordine crescente di tempo di elaborazione ridurrà al minimo il tempo medio di attesa e una serie di altre misure. Se elabori un po 'di più sull'obiettivo, i tempi di impostazione, i tempi di elaborazione e qualsiasi interdipendenza che possa essere d'aiuto.

Answer 3

Quello che stai cercando è il problema di partizione per k set.

C'è un po 'di letteratura su k = 3, chiamato il problema delle 3 partizioni. Questo è NP completo in senso stretto.

Ci sono molte euristiche che dovrebbero fornire rapidamente un risultato approssimativo.

Vi suggerisco di iniziare qui: http://en.wikipedia.org/wiki/Partition_problem

Spero che questo aiuti.

Answer 4

Questo è a version del problema di sottoinsieme ed è NP-completo. La cosa migliore da fare è utilizzare subset-sum heuristics.

Answer 5

Guardando i link pubblicati da Laurence ho pensato di provare a montare qualcosa. L'algoritmo consiste nell'assegnare il test più lungo all'elenco di attività più breve (ripetere fino a quando tutti i test sono assegnati). Usando i tuoi esempi e tempi di test casuali la deviazione standard era piuttosto bassa, meno di 2 minuti in esecuzione più volte (codice in C#, ma niente che non sarebbe banale da convertire):

private static void BuildJobs() 
    { 
     PriorityQueue<Task> tasks = new PriorityQueue<Task>(); 

     //create a task list for each node 
     for (int i = 0; i < 60; i++) 
     { 
      Task t = new Task(); 
      tasks.Enqueue(t); 
     } 

     //get the list of tests, in order from longest to shortest 
     int[] testList = new int[2000]; 

     for (int i = 0; i < testList.Length; i++) 
     { 
      testList[i] = random.Next(5, 90); 
     } 

     Array.Sort<int>(testList); 
     Array.Reverse(testList); 

     // add the longest running test to the current shortest task list 
     foreach (int time in testList) 
     { 
      Task t = tasks.Dequeue(); 
      t.addTest(time); 
      tasks.Enqueue(t); 
     } 

     Debug.WriteLine(CalculateStdDev(tasks)); 

    }