類型球拍的優化...這是遠嗎？

Question

關於打字/球拍的簡短提問。我目前正在努力通過Euler Project problems來更好地學習球拍。一些my solutions真的很慢，尤其是在處理素數和因素時。所以對於一些問題，我試圖製作一個打字/球拍版本，我發現速度沒有改善，恰恰相反。 （我試圖通過使用真正的大數字來減少開銷的影響，計算時間大約爲10秒。）

我從Racket文檔中得知最佳優化發生在when using Floats/Flonums。所以...是的，我試圖使浮動版本的問題處理整數。如在this problem與racket version使用整數，和typed/racket one人爲地轉動整數漂浮。我不得不使用的招數：檢查兩個數字實際上意味着檢查他們在這個功能用來檢查是否x可以被Y分爲「足夠接近」，像之間的平等：

(: divide? (-> Flonum Flonum Boolean)) 
(define (divide? x y) 
    (let ([r (/ x y)]) 
    (< (- r (floor r)) 1e-6))) 

它的工作原理（以及...解決方案是正確的），我的速度提高了30％-40％。

這是多麼可以接受？人們是否真的在現實生活中這樣做？如果不是，使用整數時優化打字/球拍解決方案的最佳方法是什麼？或者應該在處理整數時完全放棄鍵入/拍攝並保留用於浮點計算的問題？

Answer 1

在大多數情況下，解決方案是使用更好的算法，而不是轉換爲Typed Racket。

由於在項目歐拉關注整數最多的問題，下面是一些提示和技巧：

1. 除法運算符/需要計算的分母和分子之間的最大公司爲了抵消共同因素。這使得/是一個不好的選擇，如果你只想知道一個數字是否與另一個數字相除。使用(= (remainder n m) 0)檢查m是否分爲n。另外：如果知道除法餘數爲零，則使用quotient比/多。

2. 使用記憶來避免重新計算。即使用矢量來存儲已經計算的結果。示例：https://github.com/racket/math/blob/master/math-lib/math/private/number-theory/eulerian-number.rkt

3. 首先實現樸素算法。然後考慮如何減少個案數量。經驗法則：如果可以將案例數量減少到1至100萬，蠻力效果最佳。

4. 爲了減少查找搜索空間參數化情況的數量。示例：如果需要查找數字m和n上的Pythagorean三元組：循環，然後計算a = m^2 - n^2，b = 2mn和c = m^2 + n^2。這比在a，b和c上循環更快，其中^ 2 + b^2 = c^2不是真的。

5. 在math/number-theory的來源尋找提示和技巧。

Answer 2

不希望成爲一個真正的答案，因爲我不能提供soegaard尚未發佈任何一般性的提示，但因爲我最近做了「親情號碼 問題21」，我以爲不妨離開你在這裏我的解決方案（遺憾的是沒有多少Lisp解決方案在歐拉上發佈......）。

(define (divSum n) 
    (define (aux i sum) 
    (if (> (sqr i) n) 
     (if (= (sqr (sub1 i)) n) ; final check if n is a perfect square 
      (- sum (sub1 i)) 
      sum) 
     (aux (add1 i) (if (= (modulo n i) 0) 
          (+ sum i (/ n i)) 
          sum)))) 
    (aux 2 1)) 


(define (amicableSum n) 
    (define (aux a sum) 
    (if (>= a n) 
     sum 
     (let ([b (divSum a)]) 
      (aux (add1 a) 
       (if (and (> b a) (= (divSum b) a)) 
        (+ sum a b) 
        sum))))) 
    (aux 2 0)) 

> (time (amicableSum 10000)) 
cpu time: 47 real time: 46 gc time: 0 

當除數打交道，經常可以停在n的平方根喜歡這裏與divSum。當你找到一個友好的一對，你可能會同時加入這兩個總和，什麼可以節省你在我的代碼中不必要的計算(divSum b)。