Typed Racket 中的优化......这是否太过分了？

Question

一个关于 typed/racket 的问题。我目前正在努力通过 Euler Project problems to better learn racket. Some of my solutions 真的很慢，尤其是在处理素数和因子时。所以对于一些问题，我试着做了一个 typed/racket 版本，但我发现速度没有任何提高，恰恰相反。（我尝试通过使用非常大的数字来尽量减少开销的影响，计算时间约为 10 秒。）

我从 Racket 文档中了解到，最好的优化发生在 when using Floats/Flonums. So... yeah, I've tried to make float versions of problems dealing with integers. As in this problem with a racket version using integers, and a typed/racket one 人为地将整数转换为浮点数。我必须使用技巧：检查两个数字之间的相等性实际上意味着检查它们是否为 "close enough"，就像在这个检查 x 是否可以被 y 整除的函数中一样：

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

它有效（好吧...解决方案是正确的）并且我的速度提高了 30%-40%。

这有多可接受？人们在现实生活中真的这样做吗？如果不是，使用整数时优化 typed/racket 解决方案的最佳方法是什么？还是应该在处理整数时完全放弃 typed/racket 并保留用于浮点计算问题？

Answer 1

在大多数情况下，解决方案是使用更好的算法而不是转换为 Typed Racket。

由于 Project Euler 中的大多数问题都与整数有关，这里有一些提示和技巧：

除法运算符/需要计算分母和分子之间的最大公约数以抵消公因子。如果您只想知道一个数是否能整除另一个数，这会使 / 成为一个糟糕的选择。使用 (= (remainder n m) 0) 检查 m 是否除以 n。另外：当你知道除法的余数为零时，使用 quotient rander 而不是 /。
使用记忆避免重新计算。 IE。使用向量来存储已经计算的结果。示例：https://github.com/racket/math/blob/master/math-lib/math/private/number-theory/eulerian-number.rkt
首先实现一个简单的算法。然后考虑如何减少案例数。一条经验法则：如果可以将案例数量减少到 1-1000 万，则蛮力最有效。
为了减少搜索参数化的案例数量 space。示例：如果您需要找到一个毕达哥拉斯三元组：遍历数字 m 和 n，然后计算 a = m^2 - n^2、b = 2mn 和 c = m^2 + n^2。这比循环 a、b 和 c 跳过那些 a^2 + b^2 = c^2 不正确的三元组要快。
在 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

在处理除数时，通常可以像这里的 divSum 一样停在 n 的平方根处。当你找到一对友好的情侣时，你不妨同时将两者加到总和中，这样可以在我的代码中为你节省不必要的 (divSum b) 计算。

Typed Racket 中的优化......这是否太过分了？

Optimization in Typed Racket... Is this going too far?

optimization

integer

racket

typed-racket