У меня есть следующий код 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 миллисекунд.
Я предполагаю, что одной проблемой являются два цикла (в solution и 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)
)
)
Несмотря на уже данный ответ, я подозреваю, что узким местом является выбор алгоритма, а не детали реализации. Возможно, если бы вы сказали нам, какова цель программы, то лучшее решение могло бы стать очевидным.