Ответ 1

Эта версия основана на @mikera's, так же быстро и не требует использования уродливых макросов. На моей машине это занимает ~ 12 мс против ~ 9 мс для java.util.Arrays/sort:

(set! *unchecked-math* true)
(set! *warn-on-reflection* true)

(defn swap [^longs a ^long i ^long j]
  (let [t (aget a i)]
    (aset a i (aget a j))
    (aset a j t)))

(defn ^long apartition [^longs a ^long pivot ^long i ^long j]
  (loop [i i j j]
    (if (<= i j)
      (let [v (aget a i)]
        (if (< v pivot)
          (recur (inc i) j)
          (do 
            (when (< i j) 
              (aset a i (aget a j))
              (aset a j v))
            (recur i (dec j)))))
      i)))

(defn qsort 
  ([^longs a]
     (qsort a 0 (long (alength a))))
  ([^longs a ^long lo ^long hi]    
     (when
         (< (inc lo) hi)
       (let [pivot (aget a lo)
             split (dec (apartition a pivot (inc lo) (dec hi)))]
         (when (> split lo)
           (swap a lo split))
         (qsort a lo split)
         (qsort a (inc split) hi)))
     a))

(defn ^longs rand-long-array []
  (let [rnd (java.util.Random.)] 
    (long-array (repeatedly 100000 #(.nextLong rnd)))))

(comment
  (dotimes [_ 10]
    (let [as (rand-long-array)]
      (time
       (dotimes [_ 1] 
         (qsort as)))))
  )

Необходимость ручной встраивания в основном не нужна, начиная с Clojure 1.3. С несколькими подсказками типа только на аргументы функции JVM сделает для вас инкрустацию. Нет необходимости вводить индексные аргументы в int для операций с массивом - Clojure делает это для вас.

Одна вещь, о которой следует помнить, заключается в том, что вложенный цикл /recur действительно представляет проблемы для JVM-inline, поскольку loop/recur не поддерживает (в это время) поддержку возвращаемых примитивов. Таким образом, вы должны разбить свой код на отдельные fns. Это наилучшим образом, так как вложенные loop/recurs становятся все более уродливыми в Clojure.

Для более детального изучения того, как последовательно достичь производительности Java (когда вам это действительно нужно), изучите и поймите test.benchmark.

Ответ 2

Это немного ужасно из-за макросов, но с этим кодом я думаю, что вы можете сопоставить скорость Java (я получаю около 11 мс для теста):

(set! *unchecked-math* true)

(defmacro swap [a i j]
  `(let [a# ~a
         i# ~i
         j# ~j
         t# (aget a# i#)]
     (aset a# i# (aget a# j#))
     (aset a# j# t#)))

(defmacro apartition [a pivot i j]
  `(let [pivot# ~pivot]
     (loop [i# ~i
            j# ~j]
       (if (<= i# j#)
         (let [v# (aget ~a i#)]
           (if (< v# pivot#)
             (recur (inc i#) j#)
             (do 
               (when (< i# j#) 
                 (aset ~a i# (aget ~a j#))
                 (aset ~a j# v#))
               (recur i# (dec j#)))))
         i#))))

(defn qsort 
  ([^longs a]
    (qsort a 0 (alength a)))
  ([^longs a ^long lo ^long hi]    
    (let [lo (int lo)
          hi (int hi)]
      (when
        (< (inc lo) hi)
        (let [pivot (aget a lo)
              split (dec (apartition a pivot (inc lo) (dec hi)))]
          (when (> split lo) (swap a lo split))
          (qsort a lo split)
          (qsort a (inc split) hi)))
      a)))

Основные трюки:

• Делать все с помощью примитивной арифметики
• Использовать ints для индексов массива (это позволяет избежать некоторых ненужных бросков, а не большое дело, но каждый помогает...)
• Используйте макросы, а не функции для разрыва кода (избегайте служебных вызовов функций и бокса параметров)
• Использовать loop/recur для максимальной скорости во внутреннем цикле (т.е. разбиение подмассива)
• Избегайте создания каких-либо новых объектов в куче (избегайте векторов, последовательностей, карт и т.д.).

Ответ 3

Радость Clojure, глава 6.4 описывает ленивый алгоритм быстрой сортировки. Красота ленивой сортировки заключается в том, что она будет делать столько же работайте по мере необходимости, чтобы найти первые значения x. Поэтому, если x < n этот алгоритм O (n).

(ns joy.q)

(defn sort-parts
  "Lazy, tail-recursive, incremental quicksort.  Works against
   and creates partitions based on the pivot, defined as 'work'."
  [work]
  (lazy-seq
   (loop [[part & parts] work]
     (if-let [[pivot & xs] (seq part)]
       (let [smaller? #(< % pivot)]
         (recur (list*
                 (filter smaller? xs)
                 pivot
                 (remove smaller? xs)
                 parts)))
       (when-let [[x & parts] parts]
         (cons x (sort-parts parts)))))))

(defn qsort [xs]
    (sort-parts (list xs))) 

Ответ 4

Изучив основные моменты ответа mikera, вы можете видеть, что они в основном сосредоточены на устранении накладных расходов, введенных с помощью идиоматического (в отличие от измененного) Clojure, который, вероятно, не будет существовать в идиоматической реализации Java:

• примитивная арифметика - немного проще и более идиоматично в Java, вы с большей вероятностью будете использовать int, чем Integer s
• ints для индексов массива - тот же
• Используйте макросы, а не функции для разложения кода (избегайте функциональных накладных расходов и бокса) - исправляет проблему, возникающую при использовании языка. Clojure поощряет функциональный стиль, следовательно, служебный вызов функции (и бокс).
• Использовать loop/recur для максимальной скорости во внутреннем цикле - в Java вы бы идиоматически использовали обычный цикл (который, как я знаю, компилирует цикл /recurn, насколько мне известно)

Это, как говорится, фактически есть другое тривиальное решение. Напишите (или найдите) эффективную реализацию Java Quick Sort, произнесите что-то с такой подписью:

Sort.quickSort(long[] elems)

И затем назовите его из Clojure:

(Sort/quickSort elems)

Контрольный список:

• столь же эффективен, как в Java - да

• idiomatic в Clojure - возможно да, я бы сказал, что Java-interop является одним из основных функций Clojure.

• reusable - yes, есть хорошая возможность, что вы можете легко найти очень эффективную реализацию Java, уже написанную.

_{Я не пытаюсь троллировать, я понимаю, что вы пытаетесь выяснить с помощью этих экспериментов. Я просто добавляю этот ответ ради полноты. Пусть не упускает очевидного!:)Суб >}