2

我不明白为什么 4clojure问题 150上的回文数谜题在我发布我的解决方案时会超时。在我本地的 REPL 上,一切都非常快。我找到了这个解决方案并且它有效,但它的性能与我的解决方案相似。我知道这是很多代码,但问题并不容易。希望评论有助于理解。

(defn palindrome [n] 
  (let [ ;; given a number return a string
        digits (fn [^String x]  (String/valueOf x))              
    ;; given a string return the length
        digits-count  (fn [^String x] ( .length x) ) 
    ;; given an input sequence of digits, return a number. e.g. (seqstr (seq "1234")) => 1234
        seqstr  #(Long/parseLong (apply str %)) 
    ;; true when the given string has an even number of digits:
    even-digits? #(even? (digits-count %)) 
    ;; return the left middle of a string. For even-digit strings returns the 'real' left part, for odd-digit strings returns one digit more. 
    ;; e.g. (left-middle "12345678") => "1234"
    ;; e.g. (left-middle "1234567")  => "1234"
        left-middle #(if (even-digits? %) 
              (subs % 0 (quot (digits-count % ) 2) ) 
          (subs % 0 (inc (quot (digits-count % ) 2)))) 
    ;; mirror a given number. 
    ;; (mirror [1234 :even] ) => 12344321
    ;; (mirror [1234 :odd] )  => 1234321
        mirror (fn [[num dig]]
           (let [ d (seq (digits num))]
            (if (= :even dig) (seqstr (concat d (reverse d)))    
                        (seqstr (concat d (drop 1 (reverse d)))))))

    ;; initialize loop given a string. Returns a vector given a starting point.
    ;; (init "12345678") => [1234 :even 10000]
    ;; (init "1234567" ) => [1234 :odd  10000]
    ;; the first item in the vector contains the number we start the iteration with.
    ;; the flag indicates whether we should mirror it to an even or odd-digit number
    ;; the goal (power of 10) indicates when the next switch between odd/even-digit numbers will occur
    init #(let [s (left-middle %)] 
           (vector (Long/parseLong s) 
                (if (even-digits? %) :even :odd) 
            (long (Math/pow 10 (digits-count s)))))

    ;; given a vector (see structure above), determine the next step
      ;;(next  [999 :even 1000] ) => [1000 :odd 10000] . When finished mirroring even-digit numbers of length 3, continue with mirroring 4-digit odd-digit numbers
      ;;(next [9999 :odd 10000] ) => [1000 :even 10000]. When finished mirroring odd-digit numbers of length 4, continue with mirroring 4-digit even-digit numbers
    ;;(next [123 :odd 1000])    => [124 :odd 1000]. The normal case.
    next (fn [[num even goal]] 
         (let [m (inc num)] 
          (if (= m goal)
            (if (= even :even)
              [goal :odd (* 10 goal)]
              [(/ goal 10) :even goal])
            [m even goal] )))
   i  (init (digits n)) 
   palindromes (iterate next i) ] 
  (filter (partial <= n ) (map mirror palindromes))))

如果您将上面的代码粘贴到 REPL 中,您将能够评估以下单元测试:

(= (take 26 (palindrome 0))
   [0 1 2 3 4 5 6 7 8 9 
    11 22 33 44 55 66 77 88 99 
    101 111 121 131 141 151 161])

(= (take 16 (palindrome 162))
   [171 181 191 202 
    212 222 232 242 
    252 262 272 282 
    292 303 313 323])

(= (take 6 (palindrome 1234550000))
   [1234554321 1234664321 1234774321 
    1234884321 1234994321 1235005321])  

(= (first (palindrome (* 111111111 111111111)))
   (* 111111111 111111111))

(= (set (take 199 (palindrome 0)))
   (set (map #(first (palindrome %)) (range 0 10000))))

(= true 
  (apply < (take 6666 (palindrome 9999999))))

(= (nth (palindrome 0) 10101)
   9102019)

对于“最慢”测试(第 5 位),我得到以下性能:

user=> (time (= (set (take 199 (palindrome 0)))
   (set (map #(first (palindrome %)) (range 0 10000)))))
  "Elapsed time: 66.509472 msecs"

我真的不明白 4clojure 主页上的“超时”标准是什么。在我看来,低于 1 秒的一切都应该有效。我在 JRE 7 上使用了 Clojure 1.5.1,在 JRE 6 上使用了 clojure 1.2.1。

这是我第四次尝试解决这个难题,我的大多数解决方案都在测试 5 中遇到了困难,但我没有清楚地看到说它很慢的意义。我是否使用了太多的内存?递归?我是这种语言的新手,任何很酷的提示将不胜感激:

我的第一个解决方案有点慢,但在我的机器上大约需要 600 毫秒。

(defn palindrome [n] 
  (let [
    digits         #(seq (str %))      ;; given a number return a seq of its digits
    digits-count   #(count (digits %)) ;; given a number return how many digits it has 
    seqstr         #(Long/parseLong (apply str %))  ;; seq to number
    start          (seqstr (take (/ (digits-count n) 2) (digits n)))
    digits-range   #(map long (range (max (Math/pow 10 (dec %)) start) (Math/pow 10 %)))  ;; return all numbers of given digits length
    mirror         #(let [d (digits %1)]
                       (if (true? %2) (seqstr (concat d (reverse d)))     ;; mirror 1234 true  => 12344321 even number of digits 
                                      (seqstr (concat d (drop 1 (reverse d)))))) ;; mirror 1234 false => 1234321  odd number of digits

    digits-seq     #(drop (/ (digits-count %) 2) (range)) ;; e.g. when input number has 10 digits, result is a seq: 5, 6, 7, 8, ....
                                                          ;;      when input number has  9 digits, result is a seq: 5, 6, 7, 8, ....
    input-even     (even? (digits-count n))                                                   
    ]
(filter #(<= n %) (cons 0 (mapcat #(concat (map (fn [x]  (mirror x false))  (if (and input-even (* 2 %)) [] (digits-range %))) 
                                  (map (fn [x]   (mirror x true ))  (digits-range %)) ) (digits-seq n) ))))) 
4

1 回答 1

2

每个 4clojure 拼图都有一个或多个教学目的。您有正确的算法,但是超时测试正在惩罚您使用过多的字符串之间的转换。

罪魁祸首是您的镜像函数,它将数字转换为字符串,对其进行操作,然后将其转换回数字。

尝试插入此替代方案,它不需要字符串转换和操作:

    mirror (fn [[num dig]]
             (loop [a num, r (if (= dig :even) num (quot num 10))]
               (if (= 0 r)
                 a
                 (recur (+ (* a 10) (mod r 10)), (quot r 10)))))

这是基于您的原始帖子的完整传递解决方案,仅进行了一些其他小的更改:

(fn palindrome [n] 
  (let [even-digits? #(even? (count %)) 
        left-middle #(if (even-digits? %) 
                       (subs % 0 (quot (count % ) 2) ) 
                       (subs % 0 (inc (quot (count % ) 2)))) 
        mirror (fn [[num dig]]
                 (loop [a num r (if (= dig :even) num (quot num 10))]
                   (if (= 0 r)
                     a
                     (recur (+ (* a 10) (mod r 10)) (quot r 10)))))
        init #(let [s (left-middle %)] 
                (vector (Long/parseLong s) 
                        (if (even-digits? %) :even :odd) 
                        (long (Math/pow 10 (count s)))))
        nextp (fn [[num even goal]] 
               (let [m (inc num)] 
                 (if (= m goal)
                   (if (= even :even)
                     [goal :odd (* 10 goal)]
                     [(/ goal 10) :even goal])
                   [m even goal] )))
        i  (init (str n)) 
        palindromes (iterate nextp i) ] 
    (filter (partial <= n ) (map mirror palindromes))))
于 2013-10-08T15:59:29.527 回答