範圍最小查詢 - Clojure的

我正在一個Clojure的項目，作爲輸入的數組a，發現最小的範圍內[i,j]每個i，j，在O(n) preproccessing，並O(1)爲每個查詢。（preproccessing需要O(n*log(n))，而是通過使用併發（pmap）並且將所述陣列n/log n陣列我們能夠解決在O(n)這個問題）範圍最小查詢 - Clojure的

所以，我choce代表陣列作爲向量和矩陣的矢量向量。

這是在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>

之外，我寫的代碼不會做我想做的，因爲我不知道我怎樣才能改變VAL如果apply_fn並行工作，則表示r（表示行號）。即像它改變在C＃：

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

（r就像在C＃for -loop i）

由於提前。

來源

2012-02-14 Howaida Khoureieh

大概這和這個是一樣的問題：http://stackoverflow.com/questions/9261473/rmq-function-implementation我建議你嘗試先實現沒有並行性的函數，然後修改它以使用'pmap'一旦你第一次得到它正常工作。 – liwp 2012-02-14 09:50:16

我們再次嘗試過，得到相同的錯誤，不知道如何更改「r」的值！將不勝感激您的幫助！ – 2012-02-14 10:12:43

如果我正確地阻止了您，您希望將遞增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, ...]）。

來源

2012-02-14 10:36:28 liwp

非常感謝，即解決了我的第二疑難問題添加以下代碼：（DEFN inc_int_arr [X] （DEF M3 []）（DEF X1（分解X））（環[I 0] （如果（and（not（=（def m3（conj m3 i））[]））（= i x1）） m3（recur（inc i））））（defn build_RMQ_log [a] （計數A） ST（diag_n_m LEN（LOG_ LEN 2）） R（inc_int_arr LEN）] （PMAP（FN [行r]（apply_fn（ST一個行r）））ST）））這應該工作，但是，當我嘗試運行build_RMQ_log時，它向我顯示以下錯誤：＃ – 2012-02-14 11:08:51

你的'pmap'調用只傳遞一個參數給'（fn）'，它需要兩個參數。另外，請停止在函數定義中使用'def'。 – liwp 2012-02-14 11:15:22

沒錯。那麼，它是我在Clojure的第一個項目。感謝您的幫助，希望現在能夠運作。 – 2012-02-14 12:17:30

範圍最小查詢 - Clojure的

回答

相關問題