All geek questions in one place

Why is this Clojure program working with mutable arrays so slowly?

Spoiler warning, this is the first part of Code Day Advent 6.

I tried to solve this problem in Clojure and in Scala. The Scala program went fine and ended within seconds on my Macbook Air. However, the Clojure version takes much longer. What is the problem?

(ns adventofcode.day6
  (:require [clojure.java.io :as io]
            [clojure.string :as string]))

(set! *warn-on-reflection* true)

(def ^:const grid-size 1000)

(defn make-grid []
  (let [grid (make-array Long/TYPE grid-size grid-size)]
    (doseq [i (range grid-size)
            j (range grid-size)]
      (aset grid i j -1))
    grid))

(defn parse-line [l]
  (let [[command left-top right-bottom]
        (-> l
            (string/replace "turn off" "turn-off")
            (string/replace "turn on" "turn-on")
            (string/replace "through " "")
            (string/split #" "))
        parse-coordinates (fn [s]
                            (let [parts (string/split s #",")]
                              (map #(Integer/parseInt %) parts)))
        [left top] (parse-coordinates left-top)
        [right bottom] (parse-coordinates right-bottom)]
    [command left top right bottom]))

(defn process-line [grid command left top right bottom]
  (doseq [i (range left (inc right))
          j (range top (inc bottom))]
    (case command
      "turn-off" (aset grid i j -1)
      "turn-on"  (aset grid i j 1)
      "toggle"   (aset grid i j (* -1 (aget grid i j)))
      (throw (Exception. "unrecognized command")))))

(defn count-lights [grid]
  (reduce + (for [i (range grid-size)
                  j (range grid-size)
                  :let [value (aget grid ^Long i ^Long j)]
                  :when (pos? value)]
              value)))

(defn the-answer []
  (with-open [rdr (-> "input-day6.txt"
                      io/resource
                      io/reader)]
    (let [grid (make-grid)]
      (doseq [l (line-seq rdr)]
        (apply process-line grid
               (parse-line l)))
      (count-lights grid))))

EDIT: I rewrote the transition vector solution and it has pretty decent performance (11 seconds on my Macbook Air and 7 on my Macbook Pro)

(ns adventofcode.day6faster
  (:require [clojure.java.io :as io]
            [clojure.string :as string]))

(set! *warn-on-reflection* true)

(def ^:const grid-size 1000)

(defn make-grid []
  (vec (repeat (* grid-size grid-size) -1)))

(defn parse-line [l]
  (let [[command left-top right-bottom]
        (-> l
            (string/replace "turn off" "turn-off")
            (string/replace "turn on" "turn-on")
            (string/replace "through " "")
            (string/split #" "))
        parse-coordinates (fn [s]
                            (let [parts (string/split s #",")]
                              (map #(Integer/parseInt %) parts)))
        [left top] (parse-coordinates left-top)
        [right bottom] (parse-coordinates right-bottom)]
    [command left top right bottom]))

(defn set-grid! [t-grid grid-size i j v]
  (let [pos (+ i (* j (dec grid-size)))]
    (assoc! t-grid pos v)))

(defn update-grid! [t-grid grid-size i j f]
  (let [pos (+ i (* j (dec grid-size)))]
    (assoc! t-grid pos
            (f (get t-grid pos)))))

(defn process-line [t-grid command left top right bottom]
  (doseq [i (range left (inc right))
          j (range top (inc bottom))]
    (case command
      "turn-off" (set-grid! t-grid grid-size i j -1)
      "turn-on"  (set-grid! t-grid grid-size i j 1)
      "toggle"   (update-grid! t-grid grid-size i j (fn [i] (* -1 i)))
      (throw (Exception. "unrecognized command")))))

(defn count-lights [grid]
  (count (filter pos? grid)))

(defn the-answer []
  (with-open [rdr (-> "input-day6.txt"
                      io/resource
                      io/reader)]
    (let [t-grid (transient (make-grid))]
      (doseq [l (line-seq rdr)]
        (apply process-line t-grid
               (parse-line l)))
      (count-lights (persistent! t-grid)))))

EDIT 2: now with loops, types and a single modified array. 1.5 seconds on my Macbook Air!

(ns adventofcode.day6singlearray
  (:require [clojure.java.io :as io]
            [clojure.string :as string]))

(set! *warn-on-reflection* true)
(set! *unchecked-math* :warn-on-boxed) 

(def ^:const grid-size 1000)

(defn make-grid []
  (let [l (* grid-size grid-size)
        a (make-array Long/TYPE l)]
    (loop [i 0]
      (if (< i l)
        (do (aset ^longs a i -1)
            (recur (inc i)))
        a))))

(defn parse-line [l]
  (let [[command left-top right-bottom]
        (-> l
            (string/replace "turn off" "turn-off")
            (string/replace "turn on" "turn-on")
            (string/replace "through " "")
            (string/split #" "))
        parse-coordinates (fn [s]
                            (let [parts (string/split s #",")]
                              (map #(Integer/parseInt %) parts)))
        [left top] (parse-coordinates left-top)
        [right bottom] (parse-coordinates right-bottom)]
    [command left top right bottom]))

(defn set-grid! [grid ^long i ^long j v]
  (let [pos (+ i (* j (dec grid-size)))]
    (aset ^longs grid pos ^long v)))

(defn toggle-grid! [grid ^long i ^long j]
  (let [pos (+ i (* j (dec grid-size)))]
    (aset ^longs grid pos
             ^long (* -1 (aget ^longs grid pos)))))

(defn process-line [grid command left top right bottom]
  (let [operation (case command
                    "turn-off" #(set-grid! grid %1 %2 -1)
                    "turn-on"  #(set-grid! grid %1 %2 1)
                    "toggle"   #(toggle-grid! grid %1 %2)
                    (throw (Exception. "unrecognized command")))]
  (loop [^long i left
         ^long j top]
    (if (<= i ^long right)
      (if (<= j ^long bottom)
        (do (operation i j)
            (recur i (inc j)))
        (recur (inc i) top))))))    

(defn count-lights [grid]
  (count (filter pos? grid)))

(defn the-answer []
  (with-open [rdr (-> "input-day6.txt"
                      io/resource
                      io/reader)]
    (let [grid (make-grid)]
      (doseq [l (line-seq rdr)]
        (apply process-line grid
               (parse-line l)))
      (count-lights grid))))
+4
source share
2 answers

( 4- ). .

(set! *unchecked-math* true)

(defn turn-off [^ints grid [r1 c1 r2 c2]]
  (doseq [i (range r1 (inc r2))
          k (range (+ c1 (* i 1000)) (+ c2 (* i 1000) 1))]
    (aset grid k 0)))

(defn turn-on [^ints grid [r1 c1 r2 c2]]
  (doseq [i (range r1 (inc r2))
          k (range (+ c1 (* i 1000)) (+ c2 (* i 1000) 1))]
    (aset grid k 1)))

(defn toggle [^ints grid [r1 c1 r2 c2]]
  (doseq [i (range r1 (inc r2))
          k (range (+ c1 (* i 1000)) (+ c2 (* i 1000) 1))]
    (aset grid k (- 1 (aget grid k)))))

(defn count-on [^ints grid]
  (areduce grid i cnt 0 (+ cnt (aget grid i))))

(defn day06a []
  (let [grid (int-array (* 1000 1000))] ; 0-initialized via Java
    (with-open [rdr (clojure.java.io/reader "input/input06.txt")]
      (doseq [cmd (line-seq rdr)]
        (let [v (map #(Integer/parseInt %) (re-seq #"[0-9]+" cmd))]
          (cond (.startsWith cmd "turn off") (turn-off grid v)
                (.startsWith cmd "turn on")  (turn-on grid v)
                (.startsWith cmd "toggle")   (toggle grid v)))))
    (count-on grid)))
+1

:

  • (set! *warn-on-reflection* true)
(set! *unchecked-math* :warn-on-boxed)

.

  • .

  • /recur

Java Scala:

(ns adventofcode.day6singlearray
  (:require [clojure.java.io :as io]
            [clojure.string :as string]))

(set! *warn-on-reflection* true)
(set! *unchecked-math* :warn-on-boxed) 

(def ^:const grid-size 1000)

(defn make-grid []
  (let [l (* grid-size grid-size)
        a (make-array Long/TYPE l)]
    (loop [i 0]
      (if (< i l)
        (do (aset ^longs a i -1)
            (recur (inc i)))
        a))))

(defn parse-line [l]
  (let [[command left-top right-bottom]
        (-> l
            (string/replace "turn off" "turn-off")
            (string/replace "turn on" "turn-on")
            (string/replace "through " "")
            (string/split #" "))
        parse-coordinates (fn [s]
                            (let [parts (string/split s #",")]
                              (map #(Integer/parseInt %) parts)))
        [left top] (parse-coordinates left-top)
        [right bottom] (parse-coordinates right-bottom)]
    [command left top right bottom]))

(defn set-grid! [grid ^long i ^long j v]
  (let [pos (+ i (* j (dec grid-size)))]
    (aset ^longs grid pos ^long v)))

(defn toggle-grid! [grid ^long i ^long j]
  (let [pos (+ i (* j (dec grid-size)))]
    (aset ^longs grid pos
             ^long (* -1 (aget ^longs grid pos)))))

(defn process-line [grid command left top right bottom]
  (let [operation (case command
                    "turn-off" #(set-grid! grid %1 %2 -1)
                    "turn-on"  #(set-grid! grid %1 %2 1)
                    "toggle"   #(toggle-grid! grid %1 %2)
                    (throw (Exception. "unrecognized command")))]
  (loop [^long i left
         ^long j top]
    (if (<= i ^long right)
      (if (<= j ^long bottom)
        (do (operation i j)
            (recur i (inc j)))
        (recur (inc i) top))))))    

(defn count-lights [grid]
  (count (filter pos? grid)))

(defn the-answer []
  (with-open [rdr (-> "input-day6.txt"
                      io/resource
                      io/reader)]
    (let [grid (make-grid)]
      (doseq [l (line-seq rdr)]
        (apply process-line grid
               (parse-line l)))
      (count-lights grid))))
0

Source: https://habr.com/ru/post/1619013/

More articles:


All Articles