代码之家  ›  专栏  ›  技术社区  ›  Jayan

将数字列表划分为较小的列表,且“总和”大致相同

  •  5
  • Jayan  · 技术社区  · 15 年前

    我在网格上执行大约2000个测试,每个测试作为网格上的独立任务运行。这些测试确实有相当长的启动时间。总执行时间为500小时,在60节点引擎上不到10小时即可完成。测试的运行时间从5分钟到90分钟不等。在没有太多智能的情况下,组合测试可以提高性能。我想创建大小大致相同的“任务”。我怎样才能做到?

    (我们现在做的是:对所有测试进行排序并不断添加,直到执行时间的总和约为5小时。寻找更好的东西)

    5 回复  |  直到 15 年前
        1
  •  11
  •   Laurence Gonsalves    15 年前

    这样做是NP完全的。这是一个变体的 partition problem subset sum problem ,这本身就是 knapsack problem

    在您的情况下,您可能不需要精确的解决方案,因此您可能可以使用一些启发式方法在合理的时间内获得“足够好”的结果。见 Methods 分区问题页面的一部分,介绍一些方法。

        2
  •  3
  •   Aryabhatta Aryabhatta    15 年前

    你要找的是k集的划分问题。

    有许多启发式方法可以快速给出近似结果。

    http://en.wikipedia.org/wiki/Partition_problem

    希望这有帮助。

        3
  •  3
  •   BlueRaja - Danny Pflughoeft    15 年前

    这是 a version 是子集和问题的一种,是NP完全的。你最好的办法是雇佣一些人 subset-sum heuristics .

        4
  •  1
  •   Grembo    15 年前

    你的问题听起来有点像车间调度问题。有各种不同的测序方法,其中一些已经描述 here . 例如,按处理时间的递增顺序排序将使平均等待时间和一系列其他措施最小化。如果您对目标、设置时间、处理时间以及任何有帮助的相互依赖性进行详细说明。

        5
  •  0
  •   Dolphin    15 年前

    看着劳伦斯发布的链接,我想我应该试着做点什么。算法是将最长的测试分配给最短的任务列表(重复,直到分配了所有测试)。使用您的示例和随机测试时间,std偏差非常低,运行几次都不到2分钟(用C#编写代码,但转换起来并不容易):

        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));
    
        }