Минимальный диапазон запросов - Clojure

Question

Я работаю над проектом Clojure, который принимает в качестве входных данных массив a и находит минимум в диапазоне [i,j] для каждого i, j, при O(n) предварительной обработке и O(1) за каждый запрос.(предварительная обработка занимает 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>

кроме того, код, который я написал, не делает то, что я хочу, потому что я не знаю, какМогу ли я изменить значение r (которое представляет номер строки), если apply_fn работает параллельно.Т.е. как будто он меняется в c #:

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

(r походит на i в for -loop в c #)

Заранее спасибо.

Answer 1

Если я вас правильно понял, вы хотите передать увеличивающийся 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, ...]).