Clojure运行速度非常慢

我制作了一个简单的Clojure程序，即使迭代次数等于500，它的运行速度也非常慢。有人能告诉我我的代码出了什么问题吗？

(ns calc.core
(:require [clojure.math.numeric-tower :as math]))
(def ^:const B 500)
(defn build-map [p h g]
  (into {} (for [n (range 0 B)] [n (mod (/ h (math/expt g n)) p)])))
(defn find-result [res-map p g]
  (for [n (range 0 B)
    :when (= (mod (math/expt g (* B n)) p) (res-map n))]
  (get res-map n)))
(defn calculate [p h g]
  (find-result (build-map p h g) p g))
(def ^:const P 130N)
(def ^:const G 642N)
(def ^:const H 323N)    
(defn -main []
  (do
    (println "Starting calculation...")
    (println (calculate P H G))
    (println "done")))

更新#1我更改了查找结果的功能，性能有所提高：

(defn find-result [res-map p g]
  (for [[k v] res-map
    :when (= (mod (math/expt g (* B k)) p) v)]
  v))

为什么这个代码运行得更快？还可以对我的代码进行哪些改进，使其运行得更快(对于B=1024，运行时间仍然很慢(？

更新#2

尝试了所有的建议，仍然，Clojure版本似乎永远运行。例如，这个用Java编写的版本运行速度惊人：https://gist.github.com/kernelmode/e943f155edad50c01955

这是我代码的更新版本：

(ns crypto5.core
  (:require [clojure.math.numeric-tower :as math]))
(def ^:const B (math/expt 2N 10N))
(def ^:const P 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171N)
(def ^:const G 11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568N)
(def ^:const H 3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333N)
(def ^:const R (/ 1 G))
(def GpowB (math/expt G B))
(def exps (take B (iterate (fn [[e eb]] [(* e G) (* eb GpowB)]) [1 1])))
(defn -main []
  (println (map #(mod (/ H (first %)) P) (filter (fn [[e eb]] (= (mod (/ H e) P) (mod eb P))) exps))))

您正在计算大量庞大的数字。当B为500时，地图中的关键点为0-499。在g为642N的find结果中，您计算了500次math/expt，最大的是(math/expt642N249500(。仅这一个就需要很长时间来计算，而这正是k=499的时候。如果你指定了你想解决的确切问题，那会很有帮助。看起来更像是一个算法问题。

更新

我在这里创建了一个Clojure解决方案：Clojure的解决方案要点。据我所知，它应该与Java版本相同(最好检查一下以确定(。它的运行时间大约为30秒，体积更小，可读性也更强。具有讽刺意味的是，我以前很难阅读Clojure，现在读Java我遇到了麻烦：(。你遇到的最大性能问题是没有使用modPow。事实证明，即使在Java中进行pow和mod也比使用modPow慢得多。哦，Clojure BigInt与BigInteger不同，这并没有让它变得更容易。所以我采用了BigInteger和Java互操作。有时你需要获得最好的表现。希望这能有所帮助。

更新#2代码

(ns calc.core)
(def start (biginteger 1))
(def b (.pow (biginteger 2) 20))
(def g (biginteger 11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568))
(def p (biginteger 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171))
(def h (biginteger 3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333))
(defn build-left-table [start end p h g]
  (into {}
        (pmap (fn [n] [(.mod(.multiply h (.modInverse (.modPow g (biginteger n) p) p)) p) (biginteger n)])
              (range start (inc end)))))
(defn find-collision [table b p g]
  (let [base (.modPow g b p)]
    (loop [i 0
           v (biginteger 1)]
      (when (< i b)
        (do
          (if (contains? table v)
               (let [percentage (double (/ (* i 100) b))]
                 (println (str "Collision after " percentage "%"))
                 [i (table v)])
               (recur (inc i) (.mod (.multiply v base) p))))))))
(time (find-collision (build-left-table start b p h g) b p g))

更新#3

如果你只是想找到值，这是一个更好的类似Clojure的版本。上面基本上是一个java重写：

(defn find-collision [table b p g]
  (let [base (.modPow g b p)
        f (iterate (fn [x] (.mod (.multiply x base) p)) (biginteger 1))]
    (some (fn [x] (table x)) (take b f))))

您的算法是O(n-logn(，因为expt对每个n进行logn乘法运算。您可以将其简化为O(n(，以更实用的方式再次写入。我的食谱：

预先计算g^B:(def GpowB (math/expt g B))
在[1 1]上迭代计算指数：(def exps (take B (iterate (fn [[e eb]] [(* e G) (* eB GpowB)]) [1 1])))
筛选此序列以获取解决方案并获取结果：(map #(mod (/ H (first %)) P) (filter (fn [[e eb]] (= (mod (/H e) P) (mod eb P))) exps))

把它当作一个提示，我现在还不能测试它。

在更新中，由于避免了在映射中为每个元素调用(res-map n)进行查找，因此速度会更快。

相关内容

最新更新

热门标签：