5

これは私がかなり長い間考えてきた問題です。

x から y までのどの数でも割り切れない a から b までのすべての数を見つける最速の方法は何ですか?

このことを考慮：

2 から 5 で割り切れない 1 から 10 までのすべての数字を見つけたいと考えています。線形アプローチを使用する場合、このプロセスは非常に遅くなります。このような：

result = []
a = 1
b = 10
x = 2
y = 5
for i in range(a,b):
    t = False
    for j in range(x,y):
        if i%j==0:
            t = True
            break
    if t is False:
        result.append(i)
return result

線形解よりも短い計算時間でこれを行う他の方法を知っている人はいますか?

そうでない場合、私はこの時点で空白なので、誰でもこれをより速く行う方法を見ることができます...

敬具、ジョン

[編集]

数値の範囲は 0 から >1,e+100 です

これは、a、b、x、および y に当てはまります。

4

2 に答える 2

4

可能な除数の範囲内の素数のみをチェックする必要があります。たとえば、値が 2 で割り切れない場合、2 の倍数でも割り切れません。他のすべての素数と素数倍数についても同様です。したがって、あなたの例ではチェックできます2, 3, 5-チェックする必要はありません4。4で割り切れるものは2で割り切れる必要があるためです。したがって、より高速なアプローチは、関心のある範囲で素数を計算し、次に単純にそれらが分割する値。

別のスピードアップは、関心のある範囲内の各値を a に追加することですset。範囲内の数値で割り切れる場合は、セットから削除します。次に、セットに残っている数字のみをテストする必要があります。これにより、数字を複数回テストすることがなくなります。

これら 2 つのアプローチを組み合わせるとset、すべての値 (例では、すべての値が 1 から 10 のセット) を作成し、そのセットから 2 番目の範囲の各素数の倍数を単純に削除できることがわかります。

編集: パタシュが指摘したように、特定の値を分割する素数がセットにない場合、これはうまく機能しません。これを修正するには、上記と同様のアルゴリズムを適用できます: 値を持つ を作成しset、[a, b]の各値に対して、setその倍数をすべて削除します。したがって、以下のコメント ( with [3, 6]) の例では、3 から始めて、セット内の倍数を削除します - so 6。したがって、テストする必要がある残りの値は[3, 4, 5]、この場合に必要なものです。

Edit2:これは、最適化されておらず、恐ろしい変数名を持つ、本当にハッキングされた、くだらない実装です:

def find_non_factors():
    a = 1
    b = 1000000
    x = 200
    y = 1000

    z = [True for p in range(x, y+1)]
    for k, i in enumerate(z):
        if i:
            k += x
            n = 2
            while n * k < y + 1:
                z[(n*k) - x] = False
                n += 1

    k = {p for p in range(a, b+1)}

    for p, v in enumerate(z):
        if v:
            t = p + x
            n = 1
            while n * t < (b + 1):
                if (n * t) in k:
                    k.remove(n * t)
                n += 1

    return k

これらの数値で元の実装を試してください。私のコンピューターでは 1 分以上かかります。この実装には 2 秒もかかりません。

于 2013-04-12T05:21:22.060 に答える
3

究極の最適化に関する警告: 時期尚早に最適化しないでください。コードを最適化しようとするときはいつでも、最適化が必要であることを確認するためにそれをプロファイリングし、最適化する予定の同じ種類のデータで最適化をプロファイリングして、それが高速であることを確認します。ほとんどすべてのコードは、正しい答えを出すためだけに最適化する必要はありません。

小さい xy と大きい ab を最適化する場合:

すべての x、x+1、x+2... y の最小公倍数の長さの配列を作成します。たとえば、2、3、4、5 の場合、120 ではなく 60 になります。

次に、この配列にブール値を入力します。最初はすべてのセルに対して false であり、次に xy の各数値に対して、その数値の倍数である配列内のすべてのエントリに true を入力します。

ab の各数値について、arraylength を法とする配列にインデックスを付け、それが true の場合はスキップし、false の場合はそれ以外をスキップして戻ります。

素因数展開が他の数値の素因数展開の厳密なスーパーセットである x から y 因数の数値を削除することで、これを少し速く行うことができます。つまり、2、3、4、5、4 がある場合、2*2 は 2 の厳密なスーパーセットであるため、削除することができ、配列の長さは 30 しかありません。3、4、5、6 などの場合ただし、4 は 2*2 であり、6 は 3*2 です。6 は 3 のスーパーセットであるため削除しますが、4 はすべてのスーパーセットではないため、保持します。LCM は 3*2*2*5 = 60 です。 . この種のことを行うと、大きな ab の場合、それ自体である程度の速度が向上し、それが必要な場合は配列方向に移動する必要がない場合があります。

また、関数の結果全体を毎回使用しない場合 (たとえば、最小値のみに関心がある場合など) は、関数としてではなくジェネレーターとして記述してください。そうすれば、十分な数になるまで呼び出して停止し、時間を節約できます。

于 2013-04-12T05:35:04.983 に答える