4clojure回文数超时问题

Question

我不明白为什么4coljur Problem 150回文数字难题超时我发布我的解决方案。在我的本地REPL上，一切都非常快。我发现这solution，它的工作原理，但它有一个类似我的解决方案的性能。我知道这是很多代码，但问题并不容易。希望评论有助于理解。

(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代码，你将能够评估folloing单元测试：

(= (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斗争，但我没有清楚地看到这一点说这很慢。我是否使用太多内存？递归？我是新来的这种语言和任何很酷的提示，将不胜感激：

我的第一个解决方案有点慢，但在我的机器上约600ms结束。

(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)))))) 

Answer 1

每一个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))))