Tìm các chức năng tối thiểu

Question

OK, đây là giao dịch. Tôi có một loạt các hàm tuyến tính, một dấu * x + b.

Mục tiêu của tôi là trả lời câu hỏi/truy vấn sau: Chức năng tối thiểu tại x = q là gì?

Ví dụ: Nếu tôi có hàm f (x) = 3 * x + 2, g (x) = 5 * x - 6 và h (x) = 2 * x + 1, tôi sẽ trả lời ví dụ:

• cho x = 4, chức năng h

• cho x = 2, chức năng g

• cho x = 1, chức năng g

Ý tưởng của tôi như sau:

1. Sắp xếp các hàm theo hệ số x, theo thứ tự giảm dần.

2. Sắp xếp các truy vấn trong thứ tự tăng dần

3. Loại bỏ các chức năng song song, giữ những người thân với giá trị bất biến nhỏ nhất (ví dụ: nếu tôi có f (x) = 2 * x + 4 và g (x) = 2 * x + 2, f (x) sẽ không bao giờ nhỏ hơn g (x), vì vậy tôi không cần f (x)).

4. Ngay bây giờ tôi đang trên khoảng từ -INF đối với một số số thực, gọi nó là W1 và tôi biết rằng trên khoảng thời gian này, các chức năng với hệ số tuyến tính cao nhất là nhỏ nhất

5. Tìm W1 bằng cách tìm nhỏ nhất x1 st f (x1) = g (x1) trong đó f là hàm hiện tại của tôi và g lặp lại thông qua tất cả các hàm khác với hệ số tuyến tính nhỏ hơn, w1 = x1

6. Lặp lại miễn là truy vấn của tôi nằm trong khoảng (-inf, w1): xuất ra hàm hiện tại, sau đó tiến hành truy vấn tiếp theo.

7. Nếu tôi vẫn có các truy vấn cần trả lời, hãy để chức năng hiện tại là hàm giao cắt hàm hiện tại thực tế của tôi tại x = w1 và thay vì -inf đặt w1, lặp lại các bước tương tự.

Tuy nhiên, việc triển khai hoặc ý tưởng của tôi không đủ nhanh. Có điều gì mà tôi không nhận thấy có thể tăng tốc chương trình của tôi không?

Cảm ơn bạn trước.

Answer 1

bạn có thể không chỉ giải quyết cho giao lộ của họ và lưu trữ chức năng lớn nhất cho mỗi khoảng thời gian trong miền không?

chỉnh sửa- để xây dựng, nếu bạn giải quyết bất kỳ cặp hàm nào cho x, thì x thể hiện giá trị trong đó một trong hai hàm đó trở nên lớn hơn hàm kia. Sẽ có khoảng thời gian có thể xác định được trong đó hàm tối thiểu giống nhau cho tất cả các giá trị trong khoảng thời gian đó.

Đây là cốt truyện của 3 hàm mẫu của bạn.

Khoảng (với chức năng tối thiểu tương ứng) của đồ thị này sẽ là

(-∞, 7/3]  => 5x - 6 
(7/3, ∞]  => 2x + 1 

Bây giờ, tại thời gian chạy, thay vì bạn chỉ cần làm "chức năng tối thiểu tại x = q là gì" "Khoảng thời gian nào q thuộc về".

Và nếu tôi không nhầm, nếu bạn có N hàm tuyến tính, bạn sẽ có tối đa khoảng thời gian N-1 để lưu trữ. Và, có các cấu trúc dữ liệu chuyên dụng mà bạn có thể sử dụng để lưu trữ và tìm kiếm các khoảng thời gian nếu bạn thực sự có nhiều chức năng để phân tích.

Answer 2

Nếu tôi hiểu chính xác, giải pháp của bạn là thực hiện một số xử lý trước cho tất cả các chức năng của bạn sao cho miền của x được chia thành các phạm vi và trong mỗi phạm vi như vậy, bạn biết chức năng tối thiểu là gì.

Thực tế có hai giai đoạn: "chuẩn bị" và "truy vấn" (trong đó có một số x cụ thể mà bạn đưa ra kết quả).

Nút cổ chai của bạn là gì?

Tự nhiên cho giai đoạn "truy vấn" nhanh, bạn nên tổ chức phạm vi của mình theo loại mảng được sắp xếp để bạn có thể tìm phạm vi bao quanh số x cho trước bằng cách tìm kiếm trung bình (hoặc tương tự) trong thời gian logarit . Nếu đây là những gì bạn đã làm và vẫn không đủ nhanh - hãy xem xét tối ưu hóa mức mã, bởi vì từ quan điểm thuật toán, đây có vẻ là giải pháp tối ưu nhất.

Nếu nút cổ chai của bạn là giai đoạn "chuẩn bị" - đây là cơ hội để tối ưu hóa. Theo tôi hiểu, bạn tìm thấy nút giao của tất cả các cặp hàm của bạn (sau khi loại bỏ các hàm song song). Và điều này không thực sự cần thiết.

Hãy xem xét những điều sau đây. Trước tiên, bạn sắp xếp tất cả các hàm của mình theo hệ số của chúng (hệ số cao hơn là lúc bắt đầu). Loại bỏ các hàm song song. Tiếp theo xây dựng dãy các dãy, trong khi lặp qua các hàm của bạn.

Vì hàm hiện tại có hệ số thấp nhất (trong số các hệ số đã được phân tích) - hàm hiện tại sẽ là một nhỏ nhất là x chuyển sang vô cùng. Vì vậy, phạm vi của nó phải từ một số x0 đến vô cùng. Tìm rằng x0. Lấy phạm vi cuối cùng từ mảng (thuộc hàm được xử lý trước đó), và tìm x0 - giao điểm của hàm đó với hàm hiện tại. Phạm vi trước đây co lại đến x0. Nếu phạm vi đó trở thành không hợp lệ (phạm vi bắt đầu lớn hơn x0) - có nghĩa là chức năng đó hoàn toàn bị che khuất. Trong trường hợp này - loại bỏ phạm vi đó và lặp lại quy trình.

Để làm cho mọi việc rõ ràng hơn, tôi sẽ viết một pseudo-code:

rangeArr là một mảng của các cặp F,X, trong khi F là mô tả chức năng, và X là sự bắt đầu của dãy chức năng. Sự kết thúc của phạm vi chức năng được coi là bắt đầu của dãy tiếp theo, và kết thúc của phạm vi chức năng cuối cùng là + vô cùng.

for each F sorted by coefficient 
{ 
    double x0; 

    while (true) 
    { 
     if (rangeArr is empty) 
     { 
      x0 = -inf; 
      break; 
     } 

     FPrev = rangeArr.back().F; 
     xPrev = rangeArr.back().X; 

     x0 = IntersectionOf(F, FPrev); 

     if (x0 > xPrev) 
      break; 

     rangeArr.DeleteLastRange(); 
    } 

    rangeArr.InsertRange(F, x0); 
}