为什么此Clojure程序在可变数组上运行的速度这么慢？ [英] Why is this Clojure program working on a mutable array so slow?

问题描述

剧透警报，这是代码第6天到来的第一部分。

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

我试图解决此问题在Clojure和Scala中都存在。 Scala程序运行良好，并在Macbook Air上几秒钟内完成。但是Clojure版本需要更长的时间。这是什么问题？

I tried to solve this problem in Clojure and in Scala. The Scala program ran fine and finished within a few seconds on my Macbook Air. The Clojure version however takes much longer. What is the problem here?

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

编辑：我已经重写了瞬态矢量的解决方案相当不错的性能（在Macbook Air上为11秒，在Macbook Pro上为7秒）

I've rewritten the solution to transient vectors 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)))))

编辑2：现在具有循环，键入提示和单个可变数组。在我的Macbook Air上1.5秒！

EDIT 2: now with loops, type hints and a single mutable 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))))

推荐答案

Java基本数组对我来说已经足够好了（在便宜的4英寸笔记本电脑上花了半秒钟）。我没有去拆箱索引。

A Java primitive array was good enough for me (half a second on a cheap 4-yo laptop). I didn't bother to unbox indices.

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

这篇关于为什么此Clojure程序在可变数组上运行的速度这么慢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！