All geek questions in one place

Sort a primitive array with a custom comparator on Clojure

I would like to sort a primitive Java array using a custom Comparator, but I get a type error. I think the function comparatorcreates Comparator<java.lang.Object>, not Comparator<Long>, but I can't figure out how to get around this.

Here is a minimal example:

x.core=> (def x (double-array [4 3 5 6 7]))
#'x.core/x
x.core=> (java.util.Arrays/sort x (comparator #(> %1 %2)))

ClassCastException [D cannot be cast to [Ljava.lang.Object;  x.core/eval1524 (form-init5588058267991397340.clj:1)

I tried to add different types of hints to the comparator function, but frankly, I am relatively new to this language and basically just threw darts.

I intentionally simplified the above example to focus on the key question, which is a type error. In the following sections I will try to give more detailed information in order to motivate the question and demonstrate why I use a custom Comparator.

Motivation

, , R order, :

> x = c(7, 2, 5, 3, 1, 4, 6)
> order(x)
[1] 5 2 4 6 3 7 1
> x[order(x)]
[1] 1 2 3 4 5 6 7

, , .

Clojure:

(defn order
  "Permutation of indices sorted by x"
  [x]
  (let [v (vec x)]
    (sort-by #(v %) (range (count v)))))

x.core=> (order [7 2 5 3 1 4 6])
(4 1 3 5 2 6 0)

( , R 1, Clojure 0). , ( , x [0, 1, ..., (count x)] x.

R vs. Clojure

, . R :

> x = runif(1000000)
> system.time({ y = order(x) })
   user  system elapsed
  0.041   0.004   0.046

Clojure :

x.core=> (def x (repeatedly 1000000 rand))
#'x.core/x
x.core=> (time (def y (order x)))
"Elapsed time: 2857.216452 msecs"
#'x.core/y

?

, R:

> x = runif(1000000)
> system.time({ y = sort(x) })
   user  system elapsed
  0.061   0.005   0.069

.

x.core=> (def x (double-array (repeatedly 1000000 rand)))
#'x.core/x
x.core=> (time (java.util.Arrays/sort x))
"Elapsed time: 86.827277 msecs"
nil

java.util.Arrays. , R.

, Comparator ArrayList, , :

(defn order2
  [x]
  (let [v (vec x)
        compx (comparator (fn [i j] (< (v i) (v j))))
        ix (java.util.ArrayList. (range (count v)))]
    (java.util.Collections/sort ix compx)
    (vec ix)))

, Clojure. .: -)

Carcigenicate ,

(defn order
  [x]
  (let [ix (int-array (range (count x)))]
    (vec (-> (java.util.Arrays/stream ix)
             (.boxed)
             (.sorted (fn [i j] (< (aget x i) (aget x j))))
             (.mapToInt
               (proxy [java.util.function.ToIntFunction] []
                 (applyAsInt [^long d] d)))
             (.toArray)))))

:

x.core=> (def x (double-array [5 3 1 3.14 -10]))
#'x.core/x
x.core=> (order x)
[4 2 1 3 0]
x.core=> (map #(aget x %) (order x))
(-10.0 1.0 3.0 3.14 5.0)

, . , , , .

+4
1

Clojure order, quicksort . R: , 520-530 , R 500 .

: (2x quicksort, , ). - 415 , 325-365 . . , gist, - , .

, . , , 30 , , .

invokePrim - Clojure 1.9.0-RC1, . , .

. ; .

(defn order2 [xs]
  (let [rnd (java.util.Random.)
        a1 (double-array xs)
        a2 (long-array (alength a1))]
    (dotimes [i (alength a2)]
      (aset a2 i i))
    (letfn [(quicksort [^long l ^long h]
              (if (< l h)
                (let [p (.invokePrim ^clojure.lang.IFn$LLL partition l h)]
                  (quicksort l (dec p))
                  (quicksort (inc p) h))))
            (partition ^long [^long l ^long h]
              (let [pidx (+ l (.nextInt rnd (- h l)))
                    pivot (aget a1 pidx)]
                (swap1 a1 pidx h)
                (swap2 a2 pidx h)
                (loop [i (dec l)
                       j l]
                  (if (< j h)
                    (if (< (aget a1 j) pivot)
                      (let [i (inc i)]
                        (swap1 a1 i j)
                        (swap2 a2 i j)
                        (recur i (inc j)))
                      (recur i (inc j)))
                    (let [i (inc i)]
                      (when (< (aget a1 h) (aget a1 i))
                        (swap1 a1 i h)
                        (swap2 a2 i h))
                      i)))))
            (swap1 [^doubles a ^long i ^long j]
              (let [tmp (aget a i)]
                (aset a i (aget a j))
                (aset a j tmp)))
            (swap2 [^longs a ^long i ^long j]
              (let [tmp (aget a i)]
                (aset a i (aget a j))
                (aset a j tmp)))]
      (quicksort 0 (dec (alength a1)))
      (vec a2))))

(NB: x, - (def x (repeatedly 1000000 rand)); c/bench, c/quick-bench):

user> (c/bench (order2 x))
Evaluation count : 120 in 60 samples of 2 calls.
             Execution time mean : 522.485408 ms
    Execution time std-deviation : 33.490530 ms
   Execution time lower quantile : 470.089782 ms ( 2.5%)
   Execution time upper quantile : 575.687990 ms (97.5%)
                   Overhead used : 15.378363 ns
nil
user> (let [x (repeatedly 1000000 rand)]
        (c/quick-bench (order2 x)))
Evaluation count : 6 in 6 samples of 1 calls.
             Execution time mean : 527.020004 ms
    Execution time std-deviation : 14.846061 ms
   Execution time lower quantile : 507.175127 ms ( 2.5%)
   Execution time upper quantile : 543.675752 ms (97.5%)
                   Overhead used : 15.378363 ns
nil
user> (let [x (repeatedly 1000000 rand)]
        (c/quick-bench (order2 x)))
Evaluation count : 6 in 6 samples of 1 calls.
             Execution time mean : 513.476501 ms
    Execution time std-deviation : 12.828449 ms
   Execution time lower quantile : 497.164534 ms ( 2.5%)
   Execution time upper quantile : 525.094463 ms (97.5%)
                   Overhead used : 15.378363 ns
nil
user> (let [x (repeatedly 1000000 rand)]
        (c/quick-bench (order2 x)))
Evaluation count : 6 in 6 samples of 1 calls.
             Execution time mean : 529.826816 ms
    Execution time std-deviation : 21.454522 ms
   Execution time lower quantile : 508.547461 ms ( 2.5%)
   Execution time upper quantile : 552.592925 ms (97.5%)
                   Overhead used : 15.378363 ns
nil

R :

> system.time({ y = order(x) })
   user  system elapsed 
  0.512   0.004   0.514 
> system.time({ y = order(x) })
   user  system elapsed 
  0.496   0.000   0.496 
> system.time({ y = order(x) })
   user  system elapsed 
  0.508   0.000   0.510 
> system.time({ y = order(x) })
   user  system elapsed 
  0.508   0.000   0.513 
> system.time({ y = order(x) })
   user  system elapsed 
  0.496   0.000   0.499 
> system.time({ y = order(x) })
   user  system elapsed 
  0.500   0.000   0.502

: Clojure:

(defn order3 [xs]
  (let [rnd (java.util.Random.)
        a1 (double-array xs)
        a2 (long-array (alength a1))]
    (dotimes [i (alength a2)]
      (aset a2 i i))
    (letfn [(quicksort [^long l ^long h]
              (if (< l h)
                (let [p (.invokePrim ^clojure.lang.IFn$LLL partition l h)]
                  (quicksort l (dec p))
                  (quicksort (inc p) h))))
            (partition ^long [^long l ^long h]
              (let [pidx (+ l (.nextInt rnd (- h l)))
                    pivot (aget a1 pidx)]
                (swap1 a1 pidx h)
                (swap2 a2 pidx h)
                (loop [i (dec l)
                       j l]
                  (if (< j h)
                    (if (< (aget a1 j) pivot)
                      (let [i (inc i)]
                        (swap1 a1 i j)
                        (swap2 a2 i j)
                        (recur i (inc j)))
                      (recur i (inc j)))
                    (let [i (inc i)]
                      (when (< (aget a1 h) (aget a1 i))
                        (swap1 a1 i h)
                        (swap2 a2 i h))
                      i)))))
            (swap1 [^doubles a ^long i ^long j]
              (let [tmp (aget a i)]
                (aset a i (aget a j))
                (aset a j tmp)))
            (swap2 [^longs a ^long i ^long j]
              (let [tmp (aget a i)]
                (aset a i (aget a j))
                (aset a j tmp)))]
      (let [lim (alength a1)
            mid (quot lim 2)
            f1 (future (quicksort 0 (dec mid)))
            f2 (future (quicksort mid (dec lim)))]
        @f1
        @f2
        (loop [out (transient [])
               i 0
               j mid]
          (cond
            (== i mid)
            (persistent!
              (if (== j lim)
                out
                (reduce (fn [out j]
                          (conj! out (aget a2 j)))
                  out
                  (range j lim))))

            (== j lim)
            (persistent!
              (reduce (fn [out i]
                        (conj! out (aget a2 i)))
                out
                (range i mid)))

            :else
            (let [ie (aget a1 i)
                  je (aget a1 j)]
              (if (< ie je)
                (recur (conj! out (aget a2 i)) (inc i) j)
                (recur (conj! out (aget a2 j)) i (inc j))))))))))

:

user> (let [x (repeatedly 1000000 rand)]
        (c/quick-bench (order3 x)))
Evaluation count : 6 in 6 samples of 1 calls.
             Execution time mean : 325.351056 ms
    Execution time std-deviation : 3.511578 ms
   Execution time lower quantile : 321.947510 ms ( 2.5%)
   Execution time upper quantile : 330.375038 ms (97.5%)
                   Overhead used : 15.378363 ns
nil
user> (let [x (repeatedly 1000000 rand)]
        (c/quick-bench (order3 x)))
Evaluation count : 6 in 6 samples of 1 calls.
             Execution time mean : 339.422989 ms
    Execution time std-deviation : 19.929177 ms
   Execution time lower quantile : 318.996436 ms ( 2.5%)
   Execution time upper quantile : 366.113347 ms (97.5%)
                   Overhead used : 15.378363 ns
nil
user> (let [x (repeatedly 1000000 rand)]
        (c/quick-bench (order3 x)))
Evaluation count : 6 in 6 samples of 1 calls.
             Execution time mean : 415.171336 ms
    Execution time std-deviation : 13.624262 ms
   Execution time lower quantile : 393.242455 ms ( 2.5%)
   Execution time upper quantile : 428.881001 ms (97.5%)
                   Overhead used : 15.378363 ns

Found 1 outliers in 6 samples (16.6667 %)
    low-severe   1 (16.6667 %)
 Variance from outliers : 13.8889 % Variance is moderately inflated by outliers
nil
user> (let [x (repeatedly 1000000 rand)]
        (c/quick-bench (order3 x)))
Evaluation count : 6 in 6 samples of 1 calls.
             Execution time mean : 324.547827 ms
    Execution time std-deviation : 5.196817 ms
   Execution time lower quantile : 318.541727 ms ( 2.5%)
   Execution time upper quantile : 331.878289 ms (97.5%)
                   Overhead used : 15.378363 ns
nil
user> (c/bench (order3 x))
Evaluation count : 180 in 60 samples of 3 calls.
             Execution time mean : 361.529793 ms
    Execution time std-deviation : 45.285047 ms
   Execution time lower quantile : 307.535934 ms ( 2.5%)
   Execution time upper quantile : 446.679687 ms (97.5%)
                   Overhead used : 15.378363 ns

Found 1 outliers in 60 samples (1.6667 %)
    low-severe   1 (1.6667 %)
 Variance from outliers : 78.9377 % Variance is severely inflated by outliers
nil
+1

Source: https://habr.com/ru/post/1689169/

More articles:


All Articles