performance - 这段代码的性能瓶颈是什么？
问题描述
我有以下 Clojure 代码：
(ns smallest-sum.core)
(defn next-transformation
[arr]
(loop [i 0
j 0]
(let [
arr-len (count arr)
]
(if (and (< i arr-len)
(< j arr-len))
(let [
xi (nth arr i)
xj (nth arr j)
j-plus-1 (+ j 1)
i-plus-1 (+ i 1)
new-i (if (< j-plus-1 arr-len)
i
(+ i 1))
new-j (if (< j-plus-1 arr-len)
(+ j 1)
0)
]
(if (> xi xj)
;; We found it
[i j]
;; We haven't found it, recur
(recur new-i new-j)
)
)
nil ; We are at the end of the loop
) ; if
)
) ; loop
) ; defn
(defn solution
[arr]
(loop [state {
:arr arr
:sum 0
}]
(let [
cur-arr (get state :arr)
trx (next-transformation cur-arr)
]
; (println (str "========"))
; (println (str "cur-arr: " cur-arr))
(if (not (= trx nil))
;; trx is not nil -- recur
(let [
i (nth trx 0)
j (nth trx 1)
xi (nth cur-arr i)
xj (nth cur-arr j)
diff (- xi xj)
]
(recur (assoc state :arr (assoc cur-arr
i
diff
)
)
)
)
;; Here we need the sum
(reduce + cur-arr)
)
)
)
)
此代码必须能够在 120000 毫秒内处理大量输入（示例见下文）。
我假设一个问题是可以合并为一个的两个循环（insolution和）。next-transformation
此代码中是否还有其他性能瓶颈？
这是失败的测试，因为solution运行时间超过 120000 毫秒：
(ns smallest-sum.test
(:require [smallest-sum.core :refer :all]
[clojure.test :refer :all]))
(deftest sample-test-cases
(is (< 0 (solution [
91293
38437
40626
173
76990
17858
43446
25050
10791
68990
52403
21503
52331
51909
73488
91293
38437
40626
173
76990
17858
43446
25050
10791
68990
52403
21503
52331
51909
73488
91293
38437
40626
173
76990
17858
43446
25050
10791
68990
52403
21503
52331
51909
73488
91293
38437
40626
173
76990
17858
43446
25050
10791
68990
52403
21503
52331
51909
73488
]) ))
)
更新：在阅读了答案以及这个问题之后，我重写了代码如下。现在它似乎工作（足够快）。
(defn gcd
[a b]
(if (= b 0)
a
(gcd b (mod a b)))
)
(defn gcd-arr
[arr]
(reduce gcd arr)
)
(defn solution
[arr]
(let [
greatest-common-divisor (gcd-arr arr)
arr-len (count arr)
]
(* arr-len greatest-common-divisor)
)
)
解决方案
我发现这段代码很难推理。如果您可以提供代码尝试执行的操作的描述，则可能会提供更好的建议。
但是根据我看到的运行这两个函数solution的情况，它需要一个向量并以某种方式减小值，直到它们都是相同的值。然后返回向量的大小乘以相同的值。（或减少的值的总和）next-transformation从具有不同值的向量中挑选出两个索引，solution然后通过差异减少较大的索引。
next-transformation 返回的索引之一始终为零。
结果next-transformation是：
nil当向量中的所有元素都相同时。[0 first-index-of-element-less-than-first]当向量的一个或多个元素小于第一个元素时。- 否则
[first-index-of-element-greater-than-first 0]。
上述结果可以一次计算而不是嵌套循环。就像是：
(defn nt-1 [arr]
(let [f (first arr)]
(loop [i 1
bigger nil]
(cond (>= i (count arr)) (if (nil? bigger)
nil
[bigger 0])
(> f (arr i)) [0 i]
:else (recur (inc i)
(cond (not (nil? bigger)) bigger
(< f (arr i)) i
:else nil))))))
如果以下内容正确，我不太了解solution，但另一种可能性可能是退出第一个不相等的元素：
(defn nt-2 [arr]
(let [f (first arr)]
(loop [i 1]
(cond (>= i (count arr)) nil
(< f (arr i)) [i 0]
(> f (arr i)) [0 i]
:else (recur (inc i))))))
定时：
;; Using original next-transformation
user> (time (solution (into [] (repeat 100000 10000))))
"Elapsed time: 269826.483125 msecs"
1000000000
user> (def next-transformation nt-1)
#'user/next-transformation
user> (time (solution (into [] (repeat 1000000 10000))))
"Elapsed time: 116.421625 msecs"
10000000000
user> (def next-transformation nt-2)
#'user/next-transformation
user> (time (solution (into [] (repeat 1000000 10000))))
"Elapsed time: 87.211333 msecs"
10000000000
使用您的测试数据：
;; Original next-transformation
user> (time (solution [91293 38437 40626 173 76990 17858 43446 25050 10791
68990 52403 21503 52331 51909 73488 91293 38437 40626
173 76990 17858 43446 25050 10791 68990 52403 21503
52331 51909 73488 91293 38437 40626 173 76990 17858
43446 25050 10791 68990 52403 21503 52331 51909 73488
91293 38437 40626 173 76990 17858 43446 25050 10791
68990 52403 21503 52331 51909 73488]))
"Elapsed time: 112973.434458 msecs"
60
user> (def next-transformation nt-1)
#'user/next-transformation
user> (time (solution [91293 38437 40626 173 76990 17858 43446 25050 10791
68990 52403 21503 52331 51909 73488 91293 38437 40626
173 76990 17858 43446 25050 10791 68990 52403 21503
52331 51909 73488 91293 38437 40626 173 76990 17858
43446 25050 10791 68990 52403 21503 52331 51909 73488
91293 38437 40626 173 76990 17858 43446 25050 10791
68990 52403 21503 52331 51909 73488]))
"Elapsed time: 1630.157375 msecs"
60
零和负数似乎导致无限循环
在至少一个正数和至少一个非正数的情况下solution似乎进入了一个无限循环。我假设正在使用的数据是正整数。
一旦 (arr 0) 为 1，则结果为 (count arr)。
我的直觉说，通常其中一个元素会减少到一个，导致结果(count arr)大部分时间。我的直觉还说，大多数情况下，但并非总是如此，返回是一个无趣的功能，(count arr)所以我可能是错的。
在结果(count arr)尽快退出的情况下，(= 1 (arr 0))将提供性能提升。
(defn s-1 [arr]
(loop [state {:arr arr :sum 0}]
(let [cur-arr (get state :arr)
trx (next-transformation cur-arr)]
(cond (nil? trx) (* (count cur-arr)
(nth cur-arr 0 0))
(= 1 (first cur-arr)) (count arr)
:else (let [i (nth trx 0)
j (nth trx 1)
xi (nth cur-arr i)
xj (nth cur-arr j)
diff (- xi xj)]
(recur (assoc state :arr (assoc cur-arr
i
diff))))))))
定时：
user> (def solution s-1)
;; next-transformation has been restored to original
user> (time (solution [91293 38437 40626 173 76990 17858 43446 25050 10791
68990 52403 21503 52331 51909 73488 91293 38437 40626
173 76990 17858 43446 25050 10791 68990 52403 21503
52331 51909 73488 91293 38437 40626 173 76990 17858
43446 25050 10791 68990 52403 21503 52331 51909 73488
91293 38437 40626 173 76990 17858 43446 25050 10791
68990 52403 21503 52331 51909 73488]))
"Elapsed time: 9.182584 msecs"
60
#'user/next-transformation
user> (time (solution [91293 38437 40626 173 76990 17858 43446 25050 10791
68990 52403 21503 52331 51909 73488 91293 38437 40626
173 76990 17858 43446 25050 10791 68990 52403 21503
52331 51909 73488 91293 38437 40626 173 76990 17858
43446 25050 10791 68990 52403 21503 52331 51909 73488
91293 38437 40626 173 76990 17858 43446 25050 10791
68990 52403 21503 52331 51909 73488]))
"Elapsed time: 2.379 msecs"
60
清理solution，根据我的口味：
;; :sum is never used. So there is no reason
;; to have `state` with two entries.
;; (Not that there ever was:
;; `(loop [arr arr sum 0]...)`)
;; would have been fine.
;; With only `arr` changing, we can
;; recur to the function top, without
;; `loop`
(defn s-2 [arr]
(let [trx (next-transformation arr)]
(cond (nil? trx) (* (count arr)
(nth arr 0 0)) ; Last `0` provides a default
(= 1 (first arr)) (count arr)
:else (let [[i j] trx ;destructuring
diff (- (arr i) (arr j))]
(recur (assoc arr i diff))))))
定时：
user> (def solution s-2)
#'user/solution
user> (time (solution [91293 38437 40626 173 76990 17858 43446 25050 10791
68990 52403 21503 52331 51909 73488 91293 38437 40626
173 76990 17858 43446 25050 10791 68990 52403 21503
52331 51909 73488 91293 38437 40626 173 76990 17858
43446 25050 10791 68990 52403 21503 52331 51909 73488
91293 38437 40626 173 76990 17858 43446 25050 10791
68990 52403 21503 52331 51909 73488]))
"Elapsed time: 2.116625 msecs"
60
使用time一次并不是很好的基准测试，但考虑到所见差异的大小，我相信在这种情况下它仍然是定向的。
推荐阅读
- pygame - 如何将矩形归因于精灵
- ffmpeg - 结合两个命令（从图像中获取视频）
- pointers - 为什么从非指针值调用的闭包不能正确添加到切片中？
- google-analytics - 为什么 Cloudflare Analytics 显示的网站访问者数量比 Google Analytics 多？
- java - 如何解决 java.lang.ArrayStoreException
- jquery - ISO12 HTML5 音频播放器在后台自动播放下一首歌曲
- java - AndroidManifest.XML - 错误
- image-processing - 如何计算图像中线条的实际长度？
- c# - 获取用户打开的文件的名称和路径
- java - 如何循环回到 Java * 初学者编码器 * 中的主菜单