尋找減少分數的最有效方法-有解無憂

正如標題所示，我一直在努力尋找最有效的方法來減少分數(i.e. 10/20 -> 1/2)，我想出了這個。

def recursive(n, d):
    i=1
    loop = True

    while loop == True:
        i  = 1
        if n % i == 0:
            if d % i == 0:
                loop = False

        if i > min(n, d):
            return f'{n} / {d}'

    nn = n // i
    nd = d // i
    return recursive(nn, nd), f'{n}/{d} Common D: {i}'

我的思考程序是在最壞的情況下，這將計算到分子、分母對的最小值——在這個程序中n/d進行(N)計算。如果分數首先要減少，它會這樣做。在這樣做的程序中，它會減少(N)，即首先需要計算多少。

例如，給定一個像的隨機分數206/202，它會立即將其一分為二并再次呼叫該函式，新呼叫只需計數到 101，因此會進行(N/2)計算。

為了測驗這一點，我做了一個控制函式，它總是計數到n/dpair的最小值(thus always doing N computations)，如下所示：

def big_O(n, d):
    list_ = [f'{n} / {d} OG']
    for iteration in range(2 ,min(n, d) 1):
        if n % iteration == 0:
            if d % iteration == 0:
                list_.append(f'{n//iteration} / {d//iteration} Common D: {iteration}')
    return list_

我用我手頭的一個 janky 計時器和一個亂數生成器對它們進行了計時：

def gen():
    return randint(1,1000), randint(1,1000)

然而令我驚訝的是，我的功能表現得更差，我沒有保存很多結果，但這里有一個非常能說明其余結果：

給定 100,000 個樣本

簡單：按速度排序

frac big O-- 2.3903738830000023 秒

frac recursive-- 8.184171485 秒

This came as shock to me as I thought in the worst case scenario, due to bad luck with getting un-reducible fractions, they should be roughly equal! So I calculated the amount of times the generator would come up with a fraction that couldn't be reduced and I got something around 60% of the time, and I thought to myself,

"Ok, what if I make them all even. Then given the logic above (206/202), surely my function should be faster."

def gen_even():
    return randrange(2,2002,2), randrange(2,2002,2)

And the results are!

With 100,000 Samples

SIMPLE: ORDERED BY SPEED

frac.big_O() -- 4.2074602940000005 seconds

frac.recursive() -- 7.840177308999998 seconds

It's slightly better... BUT IT'S STILL WORSE! How can this be?! I don't get it. After this I looked at many, many different things, but in the end I couldn't figure it out. I did however find out some more fun facts, for instance once the fraction can be reduced twice (i.e. 12/8 : 6/4 : 3/2) then my function starts being better by a factor of how many more reductions there are.

For example with this generation function:

def genx4():
    return randint(1,1000)*4, randint(1,1000)*4

The results look like this:

100,000 samples

SIMPLE: ORDERED BY SPEED

frac recursive -- 6.605415995000001 seconds

frac big O -- 8.567245255000003 seconds

And if you replace the *4 with *1000 they look like this

With only 100 samples!

SIMPLE: ORDERED BY SPEED

frac recursive -- 0.014295906999997499 seconds

frac big O -- 2.250979277999999 seconds

除了為什么只有這里好？！我不知道，所以如果讀到這里的任何好心人有什么要說的，從減少分數的不同可能解決方案到為什么我的遞回函式在上述情況下更糟，請繼續，也謝謝你非常適合您的時間！

uj5u.com熱心網友回復：

對于“最有效”的解決方案，您只是在尋找的 GCD n, d，因此歐幾里得演算法O(log(max(n,d))在乘法中解決了這個問題。除非您是理論家或處理大量數字，否則可能不值得嘗試進行優化。例如，有關 GCD 計算的更多資訊，請參見關于最大公約數的 wiki，但總而言之，您必須使用輸入在“千位數”范圍內的快速乘法演算法才能開始優于正常乘法。

對于令人驚訝的計時結果，這可能是由于與 Python 內部的 for 回圈相比的while 回圈開銷。嘗試反匯編這兩個函式—— for 回圈迭代在中完成C，while回圈迭代在 Python 位元組碼中完成，速度較慢。

在您測量的短時間尺度上，性能可能是高度不可預測的。因此，為許多短回圈計時可能會告訴您更多關于語言回圈實作的效率，而不是代碼的演算法效率。

當您的輸入變大時，您只看到與漸近預測兼容的結果這一事實并不令人驚訝——這是漸近分析的核心思想。

轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424339.html

標籤：Python 算法分数

上一篇：從圍繞2的冪構造的嵌套陣列結構中獲取專案的演算法

下一篇：將排序陣列隨機拆分為更小的排序陣列