5

OK、これが取引です。私は一次関数a*x+bをたくさん持っています。

私の目標は、次の質問/クエリに答えることです。x = qでの最小関数は何ですか？

例：関数f（x）= 3 * x + 2、g（x）= 5 * x -6およびh（x）= 2 * x + 1がある場合、次のように答えます。

  • x = 4の場合、関数h

  • x = 2の場合、関数g

  • x = 1の場合、関数g

私の考えは次のようになります。

  1. 関数をxの係数で降順で並べ替えます。

  2. クエリを昇順で並べ替えます

  3. 並列関数を取り除き、定数項が最小の関数を保持します（たとえば、f（x）= 2 * x + 4およびg（x）= 2 * x + 2の場合、f（x）は決してなりませんg（x）よりも小さいので、f（x）は必要ありません。

  4. 現在、私は-infから実数までの区間にいます。これをw1と呼びます。この区間では、線形係数が最も高い関数が最小であることがわかります。

  5. 最小のx1stf（x1）= g（x1）を見つけてw1を見つけます。ここで、fは現在の関数であり、gは他のすべての関数をより小さな線形係数w1=x1で繰り返します。

  6. クエリが区間（-inf、w1）にある限り繰り返します。現在の関数を出力してから、次のクエリに進みます。

  7. 回答が必要なクエリがまだある場合は、現在の関数をx = w1で実際の現在の関数と交差するものとし、-infputw1の代わりに同じ手順を繰り返します。

しかし、私の実装やアイデアは十分に速くありません。私のプログラムをスピードアップするかもしれないことに気づかなかったものはありますか？

前もって感謝します。

4

2 に答える 2

4

それらの交点を解いて、ドメイン内の各間隔の最大関数を保存することはできませんか?

編集-詳しく説明すると、x について任意の関数のペアを解く場合、x は、これら 2 つの関数の一方が他方よりも大きくなる値を表します。間隔内のすべての値に対して最小関数が同じである、定義可能な間隔があります。

これは、3 つのサンプル関数のプロットです。 ここに画像の説明を入力

このグラフの間隔 (対応する最小関数を使用) は次のようになります。

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

さて、実行時に、「x = q での最小関数は何ですか」の代わりに、単に「q が属する間隔は何ですか」を実行します。

そして、私が間違っていなければ、N 個の線形関数がある場合、格納する間隔は最大でN-1 になります。また、分析する関数が実際にたくさんある場合は、間隔を保存および検索するために使用できる特殊なデータ構造があります。

于 2012-05-20T22:43:43.053 に答える
2

私が正しく理解していれば、あなたの解決策は、ドメインがx範囲に分割されるようにすべての関数に前処理を行うことであり、そのような範囲ごとに最小関数が何であるかがわかります。

実際には、「準備」と「クエリ」の 2 つのフェーズがあります (具体的に指定xすると、結果が得られます)。

あなたのボトルネックは何ですか？

x当然のことながら、「クエリ」フェーズを高速化するには、範囲をソートされた配列のようなものに編成する必要があります。これにより、中央値検索 (または同様の方法) によって指定された を囲む範囲を対数時間で見つけることができます。これがあなたが行ったことであり、それでも十分に高速でない場合は、コードレベルの最適化を検討してください。アルゴリズムの観点からは、これが最適なソリューションと思われるからです。

ボトルネックが「準備」フェーズである場合、ここに最適化の機会があります。私が理解しているように、関数のすべてのペアの交差を見つけます（並列のものを取り除いた後）。そして、これは本当に必要ではありません。

以下を検討してください。最初に、すべての関数を係数で並べ替えます (係数が大きいほど先頭になります)。並列関数を取り除きます。次に、関数を繰り返しながら、範囲の配列を作成します。

現在の関数は (既に分析されたものの中で) 最小の係数を持っているため、現在の関数はx無限大になるにつれて最小になります。その範囲はあるものx0から無限にあるはずです。それを見つけてx0ください。配列から最後の範囲 (以前に処理された関数に属する) を取得x0し、その関数と現在の関数の共通部分を見つけます。前者の範囲は まで縮小しx0ます。その範囲が無効になった場合 (範囲の開始が より大きいx0) - その機能が完全に隠されていることを意味します。そのような場合は、その範囲を削除して、手順を繰り返します。

より明確にするために、擬似コードを記述します。

rangeArrはペアの配列、F,XはF関数の説明、Xは関数範囲の開始です。関数範囲の終わりは次の範囲の開始と見なされ、最後の関数範囲の終わりは +infinity です。

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);
}
于 2012-05-20T23:16:57.067 に答える