clojure "look-and say" Sequenz

Question

Arbeiten an einigen 2015 AoC Probleme clojure zu lernen ... Die unten war schnell genug für die 40. Iteration, aber kriecht viel später. Ich habe mich mit einigen anderen Lösungen verglichen und es ist mir nicht sofort klar, warum das so langsam ist. Ich versuchte zu verwenden, immer wieder zu glauben, dass es ungefähr so ​​effizient wie eine Schleife ist (und Stapelverbrauch zu vermeiden). Eine Sache, auf die ich nicht 100% ig klar bin, ist, ob es einen signifikanten Unterschied zwischen der Verwendung von Rezidiven und der Verwendung von Rezidiven gibt. Ich testete es in beide Richtungen und sah keinen Unterschied.

(def data "3113322113") 

(defn encode-string [data results count] 
    (let [prev (first data) 
     curr (second data)] 
    (cond (empty? data) results 
      (not= prev curr) 
      (recur (rest data) (str results count prev) 1) 
      :else (recur (rest data) results (inc count))))) 

(count 
(nth (iterate #(encode-string % "" 1) data) 40 #_50)) 

Ein Beispiel für eine Lösung, die ich gegen gebenchmarkt ist Bruce Hauman ist, was wirklich schön ist: Ich bin Iterieren über sehr große Strings wiederholt

(defn count-encode [x] 
    (apply str 
     (mapcat 
      (juxt count first) 
      (partition-by identity x)))) 

ich in meiner Lösung zu realisieren, aber ich weiß nicht Sehen Sie, wie Bruce's so viel schneller ist, denn obwohl er nicht explizit iteriert, wird Partition wahrscheinlich hinter den Kulissen ausgeführt.

Answer 1

Ihre Version wird die Berechnung so etwas wie

(str "11" (str "22" (str "31" ...))) 

, die für jeweils zwei Zeichen ein brandneues String-Objekt baut. Da hierbei jedes Zeichen in den Eingabe- und Ausgabezeichenfolgen bei jedem Schritt durchlaufen wird, ist Ihre Operation quadratisch in der Länge der Zeichenfolge.

Die Lösung, mit der Sie vergleichen, ist anders: Sie baut eine langsame Folge von ganzen Zahlen auf, was ein linearer Prozess ist. Dann tut es so etwas wie

(apply str [1 1 2 2 3 1]) 

, die die gleiche ist wie

(str 1 1 2 2 3 1 ...) 

und str, wenn Sie mit mehreren Argumenten aufgerufen, einen Stringbuilder verwendet, um effizient das Ergebnis schrittweise aufzubauen, eine Optimierung, die nicht ist verfügbar, wenn Sie bei jedem Zwischenschritt ein vollwertiges String-Objekt anfordern. Daher ist der gesamte Prozess linear und nicht quadratisch.