Geek asks and answers

Find Minimum Functions

OK, here's the deal. I have a set of linear functions, a * x + b.

My goal is to answer the following question / question: what is the minimum function for x = q?

For example: if I have functions f (x) = 3 * x + 2, g (x) = 5 * x - 6 and h (x) = 2 * x + 1, I will answer, for example:

  • for x = 4, the function h

  • for x = 2, the function g

  • for x = 1, the function g

My idea is this:

  • Sort functions by coefficient at x in descending order.

  • Sort queries in ascending order

  • Get rid of parallel functions, save them with the smallest constant term (for example: if I have f (x) = 2 * x + 4 and g (x) = 2 * x + 2, f (x) will never be less than g ( x), so I don't need f (x)).

  • Now I am in the interval from -inf to some real number, call it w1, and I know that in this interval the function with the highest linear coefficient is the smallest

  • Find w1 by finding the smallest x1 st f (x1) = g (x1), where f is my current function and g goes through all the other functions with a smaller linear coefficient, w1 = x1

  • Repeat while my query is in the interval (-inf, w1): print the current function, then go to the next query.

  • If I still have requests to answer, let the current function be the one that intersects my current current function at x = w1, and instead of -inf put w1 repeat the same steps.

However, my implementation or idea is not fast enough. Is there something that I have not noticed that can speed up my program?

Thanks in advance.

+5
2

?

Edit- , x, x , . , .

. enter image description here

( )

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

" x = q" " q".

, , N , N-1 . , , .

+4

, , x , , .

: "" "" ( x ).

?

, "" , , , x, ( ) . , , - , .

"" - . , ( ). .

. ( ). . , .

( , ) - , x . x0 . x0. ( ) x0 - . x0. ( , x0), , . - .

, :

rangeArr - F,X, F - , x - . , - + .

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

More articles:


All Articles