Каковы узкие места производительности в этом коде?

avatar
PDP
8 августа 2021 в 19:43
157
3
-1

У меня есть следующий код 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) 
    )
  )
Источник
Steffan Westcott
10 августа 2021 в 09:54
1

Несмотря на уже данный ответ, я подозреваю, что узким местом является выбор алгоритма, а не детали реализации. Возможно, если бы вы сказали нам, какова цель программы, то лучшее решение могло бы стать очевидным.

Ответы (3)

avatar
Shannon Severance
9 августа 2021 в 05:17
4

Мне трудно понять этот код. Если бы вы могли предоставить описание того, что пытается сделать код, можно было бы дать лучшие предложения.

Но исходя из того, что я вижу, запуск этих двух функций solution берет вектор и каким-то образом уменьшает значения, пока они не станут одинаковыми. а затем возвращает размер вектора, умноженный на то же значение. (Или сумма приведенных значений) next-transformation выбирает два индекса из вектора с разными значениями, которые solution затем уменьшают большее значение на разницу.


Один из индексов, возвращаемых next-transformation, всегда равен нулю.

Результат next-transformation:

  1. nil, когда все элементы вектора одинаковы.
  2. [0 first-index-of-element-less-than-first], когда один или несколько элементов вектора меньше первого элемента.
  3. еще [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) равно единице, результатом будет (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 один раз не является хорошим бенчмаркингом, но, учитывая размер наблюдаемых различий, я считаю, что в этом случае оно по-прежнему направлено.

avatar
Steffan Westcott
10 августа 2021 в 12:58
2

Как видно из другого ответа, цель связана с наибольшим общим делителем:

(defn gcd [x y]
  (if (zero? y)
    x
    (recur y (mod x y))))

(defn solution [arr]
  (* (count arr) (reduce gcd arr)))
avatar
leetwinski
10 августа 2021 в 11:09
3

реализованный вами алгоритм фактически f(data) = gcd(data) * length(data) для любого набора data положительных целых чисел.

Хотя выбранный вами алгоритм рекурсивного вычитания неоптимален, его можно улучшить, например,

(defn solve2 [data]
  (cond (some #(= 1 %) data) (count data)             ;; if any of numbers is 1, gcd is obviously 1
        (apply = data) (* (first data) (count data))  ;; if all of them are equal => gcd is found 
        :else (let [res (map #(reduce (fn [acc x]
                                        (if (< x acc)
                                          ;; the next line is identical to substracting x from acc while substraction result is > x
                                          (- acc (long (* x (dec (Math/ceil (/ acc x))))))
                                          acc))
                                      %
                                      data)
                             data)]
                ;; repeating until gcd is not found
                (recur res))))

user> (solve2 [4 8 2 6 10 12])
;;=> 12

user> (solve2 [4 8 2 6 10 21])
;;=> 6

или для вашего ввода:

user> (time (solve2 [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: 1.518815 msecs"
;;=> 60

но на самом деле вам нужно просто составить некоторую функцию gcd и уменьшить ввод с ее помощью. Что-то вроде этого:

;; binary gcd algorithm impl
(defn gcd
  ([m n] (gcd 1 m n))
  ([mul m n]
   (let [m (long m)
         n (long n)]
     (cond (zero? m) (* n mul)
           (zero? n) (* m mul)
           (== m n) (* m mul)
           (or (== 1 m) (== 1 n)) mul
           (and (even? m) (even? n)) (recur (* mul 2) (/ m 2.0) (/ n 2.0))
           (even? m) (recur mul (/ m 2.0) n)
           (even? n) (recur mul m (/ n 2.0))
           (> n m) (recur mul (/ (- n m) 2.0) m)
           :else (recur mul (/ (- m n) 2.0) n)))))

user> (reduce gcd [2 4 8 8 10 22])
;; 2
user> (reduce gcd [2 4 8 11 10 22])
;; 1

user> (time (reduce gcd [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: 0.079517 msecs"
;;=> 1

user> (time (let [data [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]]
              (* (count data) (reduce gcd data))))
;; "Elapsed time: 0.085898 msecs"
;;=> 60