Clojure: упорядочьте назад к вектору
Как я могу бросить последовательность назад к вектору после операции создания последовательности (как вид)? Делает использование (vec..) на последовательности, которая была вектором, является дорогостоящим?
Один (плохо?) возможность создает новый вектор из последовательности:
(vec (sort [1 2 3 4 5 6]))
Я спрашиваю, потому что мне нужен произвольный доступ (энный..) к огромным отсортированным векторам - которые являются теперь огромными последовательностями после вида с ужасным O (n) время произвольного доступа
3 ответа
Из моих собственных тестов (ничего научного), возможно, лучше работать непосредственно с массивами в тех случаях, когда вы делаете много сортировки. Но если вы сортируете редко и у вас много случайных обращений, то работа с вектором может быть лучшим выбором, т.к. время случайного обращения в среднем более чем на 40% быстрее, но производительность сортировки ужасна из-за преобразования вектора в массив, а затем обратно в вектор. Вот мои выводы:
(def foo (int-array (range 1000)))
(time
(dotimes [_ 10000]
(java.util.Arrays/sort foo)))
; Elapsed time: 652.185436 msecs
(time
(dotimes [_ 10000]
(nth foo (rand-int 1000))))
; Elapsed time: 7.900073 msecs
(def bar (vec (range 1000)))
(time
(dotimes [_ 10000]
(vec (sort bar))))
; Elapsed time: 2810.877103 msecs
(time
(dotimes [_ 10000]
(nth bar (rand-int 1000))))
; Elapsed time: 5.500802 msecs
P.S.: Обратите внимание, что векторная версия на самом деле нигде не хранит отсортированный вектор, но это не должно существенно изменить результат, так как для скорости вы бы использовали простые привязки в цикле.
.Meikel Brandmeyer только что разместил решение этого вопроса в группе Clojure.
(defn sorted-vec
[coll]
(let [arr (into-array coll)]
(java.util.Arrays/sort arr)
(vec arr)))
Clojure's sort возвращает seq через отсортированный массив; этот подход делает почти то же самое, но возвращает вектор, а не seq.
При желании можно даже пропустить преобразование обратно в структуру постоянных данных Clojure:
(defn sorted-arr
"Returns a *mutable* array!"
[coll]
(doto (into-array coll)]
(java.util.Arrays/sort))
но результирующий Java-массив (который в большинстве случаев можно рассматривать как коллекцию Clojure) будет мутируемым. Это нормально, если вы не передаете его в другой код, но будьте осторожны.
Если вам нужен случайный доступ на результат сортировки с огромными векторами, то время, затрачиваемое на вызов vec, должно быть значительно перевешено экономией времени.
Если вы профилируете и обнаружите, что это слишком медленно, то вам, вероятно, придется использовать java-массивы.
.