2

一般的な理解のための全体的なタスク: 関数 f(x) の結果をプロットする必要があります。簡単な作業ですが、2 つの問題があります。

  1. x の値ごとに、f(x) の計算には多くの時間がかかります (数十分または約 1 時間)。
  2. f(x) の推定形状がわからないため、関数を正しく表すために事前定義された x 制限で必要な x 値がいくつあるかわかりません。

新しい f(x) 値を取得するたびに f(x) のプロットを更新したいと思います。結果的に f(x) を解きたくないので、詳細レベルを上げたいので、プロットを見るたびに、(x_min, x_max) の範囲全体で表示され、この範囲内でゆっくりと更新されます範囲。

したがって、問題は次のとおりです。適切な順序で x のリストを提供する関数が必要です。

二分探索に触発されて、次のアルゴリズムを思いつきました。

list x値のaには一意の値のみが含まれ、並べ替えられます。

def dissort(a)
    step = len(a) - 1
    picked = [False for x in a]
    out = []
    while False in picked and step > 0:
        for k in range(0, len(a), step):
            if not picked[k]:
                out.append(a[k])
                picked[k] = True
        step = step // 2
    return out

in = [1, 2, 3, 4, 5, 6, 7, 8, 9]
out = [1, 9, 5, 3, 7, 2, 4, 6, 8]
assert(dissort(in) == out)

ここにいくつかの欠陥があります。picked配列は不要な場合があり、選択された値は詳細レベルが上がるたびに不必要にチェックされます。今のところパフォーマンスに満足していますが、将来的にはもっと大きなリストにも使用できます。

よりパフォーマンスを上げる方法はありますか？一部のpythonパッケージにはすでに実装がありますか? 私はそれを見つけることができませんでした。

4

3 に答える 3

1

x 値のランダムな順序は問題ありませんか? もしそうなら：

import random
xvals = random.sample(range(10),10)

結果：

 [9, 5, 1, 7, 6, 2, 3, 0, 4, 8]

数字は繰り返されません。もちろん、結果は呼び出すたびに異なります。また、任意の数の x 値を生成できます。

random.sample(range(20),20)
 [10, 5, 0, 18, 13, 14, 19, 3, 1, 2, 17, 6, 4, 11, 15, 7, 9, 8, 12, 16]

これもO(n)だと思います。

おそらく、これに関する唯一の問題は次のとおりです。x値の数を増やすたびに、前の反復からの繰り返しを望まないでしょうか? それとも上記で十分ですか？

于 2021-03-12T17:15:15.700 に答える