对非常大的 BigInteger 进行平方非常慢

Question

我正在经历 2022 年代码降临，目前正在第 11 天第 2 部分。

我有这个解决方案：

(ns advent-of-code-2022.day11
  (:require [taoensso.timbre :as log]))

(declare give-monkey-item)
(defrecord Monkey [items operation throw-item num-inspections])

(defn create-monkey [items operation divisor monkey-true monkey-false]
  (->Monkey
    items
    operation
    (fn [item monkeys]
      (if (= (mod item divisor) 0)
        (give-monkey-item item monkeys monkey-true)
        (give-monkey-item item monkeys monkey-false)))
    0))

(defn give-monkey-item [item monkeys catcher]
  (update-in monkeys [catcher :items] #(conj % item)))

(defn throw-items [monkeys current-monkey]
  (reduce (fn [monkeys item]
            (-> item
                (biginteger)
                ((.operation current-monkey))
                ((.-throw_item current-monkey) monkeys)))
      monkeys
      (.items current-monkey)))

(defn adjust-current-monkeys-inspections [monkeys current-monkey-index]
  (let [current-monkey (get monkeys current-monkey-index)
        num-items (count (.items current-monkey))]
    (update-in monkeys [current-monkey-index :num-inspections] #(+ % num-items))))

(defn clear-current-monkeys-items [monkeys current-monkey-index]
  (let [current-monkey (get monkeys current-monkey-index)
        itemless-monkey (assoc current-monkey :items [])]
    (assoc monkeys current-monkey-index itemless-monkey)))

(defn play-turn [monkeys current-monkey-index]
  (let [current-monkey (get monkeys current-monkey-index)]
    (-> monkeys
        (throw-items current-monkey)
        (adjust-current-monkeys-inspections current-monkey-index)
        (clear-current-monkeys-items current-monkey-index))))

(defn play-round [monkeys]
  (reduce (fn [monkeys monkey-index]
            (play-turn monkeys monkey-index))
          monkeys
          (range (count monkeys))))

(defn play-rounds [monkeys num-rounds]
  (reduce (fn [rounds round-number]
            (log/info round-number)
            (let [latest-monkeys (last rounds)]
              (conj rounds (play-round latest-monkeys))))
          [monkeys]
          (range num-rounds)))

(defn calculate-monkey-business [monkeys num-rounds]
  (let [rounds (play-rounds monkeys num-rounds)]
    (->> (last rounds)
         (map #(.-num_inspections %))
         (sort)
         (reverse)
         (take 2)
         (reduce *))))

我正在使用以下代码对其进行测试：

(ns advent-of-code-2022.day11-test
  (:require [clojure.test :refer :all]
            [advent-of-code-2022.day11 :refer :all]))

(def monkeys
  [(create-monkey
     [54 98 50 94 69 62 53 85]
     (fn [old] (* old 13))
     3 2 1)
   (create-monkey
     [71 55 82]
     (fn [old] (+ old 2))
     13 7 2)
   (create-monkey
     [77 73 86 72 87]
     (fn [old] (+ old 8))
     19 4 7)
   (create-monkey
     [97 91]
     (fn [old] (+ old 1))
     17 6 5)
   (create-monkey
     [78 97 51 85 66 63 62]
     (fn [old] (* old 17))
     5 6 3)
   (create-monkey
     [88]
     (fn [old] (+ old 3))
     7 1 0)
   (create-monkey
     [87 57 63 86 87 53]
     (fn [old] (.pow old 2)) ; this is slow for big numbers
     11 5 0)
   (create-monkey
     [73 59 82 65]
     (fn [old] (+ old 6))
     2 4 3)
   ])

(deftest day11-full-test-part2
  (testing "day11-full-test-part2"
    (is (= (calculate-monkey-business monkeys 10000) 10605))))

它尝试运行 10000 次迭代，但在第 200 次迭代左右，(fn [old] (.pow old 2))测试代码中的标记函数开始对非常大的 BigIntegers 进行平方，并且变得非常慢。它是如此之慢以至于该程序可能需要几天才能完成。如果我替换.pow为简单的+，程序将在几秒钟内完成。 .pow是我尝试过的最新功能；我从一个简单的开始(* old old)，也尝试过clojure.math.numeric-tower/expt，但是三个都有这个问题。

有没有办法在 Clojure 中有效地对这些大的 BigIntegers 进行平方？

Answer 1

艾伦·汤普森（Alan Thompson）有一些建议可以稍微加快你的程序速度。我怀疑它会达到 1000 倍 - 对于小数字来说，与未暗示的相比，它可能更像是 100 倍.pow，与 相比，它可能更像是 2 倍(* x x)- 但即使是这样，这也不会接近足够的加速来保存你。事实上，正如我稍后将展示的，速度并不是您唯一的限制因素！

您注意到，在 10000 次迭代中的第 200 次迭代左右，事情变得很慢，并预测了几天的运行时间。但是，您正在查看一个具有指数运行时间的流程，而人们往往会严重低估指数公式的大小。因此，我预测您将需要真正的算法更改，而不仅仅是在现有算法上撒上一些仙尘。

为什么我说它是指数级的？好吧，您已经观察到，主导因素是以下形式的运算x = x * x：对数字进行平方，然后继续。当然，由于所有的猴子生意，并不是每一轮都涉及对所有数字进行平方，但这就是使你的数字变大的主要因素。想象一万轮只写x = x * x，从一个无害的数字如 2 开始。你对 2 (2^1) 进行平方，然后对所得的 4 (2^2) 进行平方，然后对所得的 16 (2^4) 进行平方，然后对所得的进行平方结果是 256 (2^8)，依此类推，平方一万次。该过程计算 2^(2^10000)：明显是指数（事实上，超指数，因为指数本身呈指数增长）。

为什么这是个问题？嗯，在计算机内存中存储像 2^(2^10000) 这样的数字的精确二进制表示形式是根本不可能的。在整个宇宙的任何地方存储这样一个数字的精确二进制表示是不可能的：没有足够的原子来组成所有的位。当然，我高估了假设每一轮都涉及数字的平方；但你可以预期每轮大约有 20% 的数字会被平方，因为测试可被 5 整除的猴子会向进行平方的猴子扔掷骰子。这仍然远远超出了可能性的范围。

因此任何使用 BigInteger 来存储该数字的精确表示的方法都是行不通的。幸运的是，有一些简单的改进可以让您快速执行此模拟。我不想放弃整个事情，因为很多乐趣在于自己解决问题。这里有一些提示，单独剧透。

在过程结束时您不需要确切的值本身。

在此过程中您也不需要确切的值

您所需要的只是判断它们是否可以被某些素数整除

他们从不要求你除以某些东西，这不是很好吗？

你考虑过模运算吗？