Chia danh sách các số thành danh sách nhỏ hơn với "tổng" xấp xỉ

Question

Tôi thực hiện khoảng 2000 thử nghiệm trên lưới, mỗi thử nghiệm được chạy dưới dạng nhiệm vụ riêng biệt trên lưới. Các bài kiểm tra có thời gian khởi động khá lớn. Tổng số thực hiện mất 500 giờ, kết thúc trong vòng chưa đầy 10 giờ trên 60 nút SunGridEngine. Thời gian chạy thử nghiệm thay đổi từ 5 phút đến 90 phút. Kết hợp các bài kiểm tra mà không có nhiều trí thông minh đã cho một số hiệu suất đạt được. Tôi muốn tạo "nhiệm vụ" có kích thước bằng nhau. Làm thế nào tôi có thể làm như vậy?

(những gì chúng ta làm gì bây giờ:. Phân loại tất cả các bài kiểm tra và tiếp tục bổ sung cho đến khi tổng thời gian thực hiện là khoảng 5 giờ tìm kiếm một số điều tốt hơn)

Answer 1

Việc làm này một cách tối ưu là NP-đầy đủ. Đây là biến thể của partition problem, đây là trường hợp đặc biệt của số subset sum problem, tự nó là trường hợp đặc biệt của số knapsack problem.

Trong trường hợp của bạn, bạn có thể không cần giải pháp chính xác, vì vậy bạn có thể sử dụng một số chẩn đoán để có được thứ gì đó "đủ tốt" trong một khoảng thời gian hợp lý. Xem phần Methods của trang sự cố phân vùng để biết mô tả về một số phương pháp tiếp cận.

Answer 2

Sự cố của bạn nghe có vẻ hơi giống với sự cố lập lịch cửa hàng. Có tất cả các loại phương pháp sắp xếp trình tự khác nhau, một số được mô tả here. Việc sắp xếp theo thứ tự tăng dần của thời gian xử lý, ví dụ, sẽ giảm thiểu thời gian chờ đợi trung bình và một loạt các biện pháp khác. Nếu bạn xây dựng thêm một chút về mục tiêu, thời gian thiết lập, thời gian xử lý và bất kỳ sự phụ thuộc lẫn nhau nào có thể hữu ích.

Answer 3

Điều bạn đang tìm kiếm là sự cố phân vùng cho bộ k.

Có một số tài liệu về k = 3, được gọi là bài toán 3 phân vùng. Đây là NP hoàn chỉnh theo nghĩa mạnh mẽ.

Có nhiều chẩn đoán cho kết quả gần đúng một cách nhanh chóng.

tôi đề nghị bạn bắt đầu ở đây: http://en.wikipedia.org/wiki/Partition_problem

Hope this helps.

Answer 4

Đây là a version của vấn đề tổng hợp tập hợp con và hoàn thành NP. Đặt cược tốt nhất của bạn là sử dụng một số subset-sum heuristics.

Answer 5

Nhìn vào các liên kết Laurence được đăng Tôi nghĩ rằng tôi sẽ cố gắng whipping một cái gì đó lên. Thuật toán là gán bài kiểm tra dài nhất cho danh sách nhiệm vụ ngắn nhất (lặp lại cho đến khi tất cả các bài kiểm tra được chỉ định). Sử dụng ví dụ của bạn và thời gian thử nghiệm ngẫu nhiên độ lệch tiêu chuẩn là khá thấp, ít hơn 2 phút chạy nó nhiều lần (mã trong C#, nhưng không có gì không tầm thường để chuyển đổi):

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

    }