范围最小查询-Clojure

本文关键字：-Clojure 查询 范围 | 更新日期: 2023-09-27 18:24:20

我正在处理一个Clojure项目，该项目将数组a作为输入，并为每个i、j、O(n)预处理和O(1)查找范围[i,j]中的最小值。（预处理需要O(n*log(n))，但通过使用并发（pmap）并将数组划分为n/log n数组，我们可以在O(n)中解决此问题）

所以，我决定把数组表示为向量，把矩阵表示为向量中的向量。

这是C#中的一个函数：

    void build_RMQ_log(int[] a)
    {
        ST = new int[2 * a.Length][];
        for (int i = 0; i < 2 * a.Length; i++)
            ST[i] = new int[(int)Math.Log(a.Length, 2)];
        for (int i = 0; i < a.Length; i++)
        {
            ST[i][0] = i;
            ST[i + a.Length - 1][0]=0;
        }
        for (int j = 1; j < (int)Math.Log(a.Length, 2); j++)
        {
            for (int i = 0; i < a.Length; i++)
            {
                if (a[ST[i][j - 1]] <= a[ST[i + (int)Math.Pow(2, j - 1)][j - 1]])
                    ST[i][j] = ST[i][j - 1];
                else
                    ST[i][j] = ST[i + (int)Math.Pow(2, j - 1)][j - 1];
            }
        }
    }
    i

这就是我在Clojure中写的：

    ;build_RMQ_log(int[] a)
    (defn check [row1 row2 arr j]
                  (let [x1 (nth arr (nth row1 j))
                    x2 (nth arr (nth row2 (- j 1)))
                    x3 (nth arr (nth row1 (- j 1)))]
                  (if (<= x1 x2)
                     (assoc row1 j (nth row1 (- j 1)))
                     (assoc row1 j (nth row2 (- j 1))))))
    (defn apply_fn [ST a row r]
    (let [len (count a)
     cnt (/ len (log_ len 2))]
      (loop[ii 0 r 0]
        (if (= ii (- cnt 1))
          ST
         (recur (inc ii) (check row (nth ST (+ r (Math/pow 2 (- ii 1)))) a ii))))))

   (defn build_RMQ_log [a]
     (let [len (count a)
           ST (diag_n_m len (log_ len 2))
           r 0]
     (pmap  (fn [row] (apply_fn (ST a row r))) ST )))

首先，当我尝试运行它时，它显示了这个错误：

    #<IllegalArgumentException java.lang.IllegalArgumentException: Wrong number of  args (3) passed to: PersistentVector>

此外，我写的代码并没有达到我想要的效果，因为我不知道如果apply_fn并行工作，我如何更改r（代表行号）的值。也就是说，就像c中的变化一样：

for (int i = 0; i < a.Length; i++)

（r类似于c#中for循环中的i）

提前感谢。

范围最小查询-Clojure

如果我没有正确地理解您，那么您希望将递增的r传递给apply_fn的每个调用。你可以试试这个：

(defn build_RMQ_log [a]
  (let [len (count a)
        ST (diag_n_m len (log_ len 2))
        rs (range)]
    (pmap  (fn [row r] (apply_fn (ST a row r))) ST rs)))

也就是说，将两个集合传递给pmap，其中第二个集合是递增整数的无限集合（即[0, 1, 2, 3, ...]）。

相关文章：