Clojure: последовательность обратно в вектор

Как я могу вернуть последовательность в вектор после операции создания последовательности (например, сортировка)? Использует ли использование (vec..) последовательность, являющуюся вектором, дорогостоящей?

Одна (плохая?) возможность создает новый вектор из последовательности:

(vec (sort [1 2 3 4 5 6]))

Я спрашиваю, потому что мне нужен произвольный доступ (nth..) к огромным отсортированным векторам - теперь это огромные последовательности после сортировки, с ужасным временем O (n) случайного доступа

Ответы

Ответ 1

Из моих собственных тестов (ничего научного) вам может быть лучше работать непосредственно с массивами в случаях, когда вы много сортируете. Но если вы редко разбираетесь и имеете много произвольного доступа, хотя, переход с помощью вектора может быть лучшим выбором, поскольку случайное время доступа в среднем более чем на 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.: Обратите внимание, что векторная версия фактически не хранит отсортированный вектор в любом месте, но это не должно значительно изменить результат, поскольку вы использовали бы простые привязки в цикле для скорости.

Ответ 2

Meikel Brandmeyer только что опубликовал решение этого в группе Clojure.

(defn sorted-vec
  [coll]
  (let [arr (into-array coll)]
    (java.util.Arrays/sort arr)
    (vec arr)))

Clojure sort возвращает seq через отсортированный массив; этот подход делает то же самое, но возвращает вектор, а не seq.

Если вы хотите, вы даже можете перевести преобразование в структуру постоянных данных Clojure:

(defn sorted-arr
  "Returns a *mutable* array!"
  [coll]
  (doto (into-array coll)]
    (java.util.Arrays/sort))

но полученный массив Java (который вы можете рассматривать как коллекцию Clojure в большинстве случаев) будет изменчивым. Это прекрасно, если вы не передаете его другому коду, но будьте осторожны.

Ответ 3

Если вам нужен случайный доступ к результату сортировки с огромными векторами, тогда время, затрачиваемое на вызов vec, должно быть значительно перевешивается за счет экономии времени.

Если вы прокомментируете и обнаружите, что он слишком медленный, вам, вероятно, придется использовать java-массивы.

Ответ 4

Как новый разработчик Clojure, легко путать коллекции и последовательности.

Эта отсортированная векторная функция:

(sort [1 2 3 4 5 6]) = > (1 2 3 4 5 6); возвращает последовательность

Но мне нужен вектор для следующей операции, потому что это не работает...

(взятие-в то время (частичное > 3) (1 2 3 4 5 6))

= > ClassCastException java.lang.Long нельзя отнести к clojure.lang.IFn user/eval2251 (NO_SOURCE_FILE: 2136)

Попробуем преобразовать последовательность в вектор:

(vec (1 2 3 4 5 6))

= > ClassCastException java.lang.Long нельзя отнести к clojure.lang.IFn user/eval2253 (NO_SOURCE_FILE: 2139)

Неа! Но если вы все соедините, все будет хорошо.

(взятие-в то время (частичное > 3) (sort [1 2 3 4 5 6]))

= > (1 2)

Урок: вы не можете напрямую работать с последовательностями! Это промежуточный этап в этом процессе. Когда REPL пытается оценить (1 2 3 4 5 6), он видит функцию и генерирует исключение:

(1 2 3 4 5 6) = > ClassCastException java.lang.Long не может быть добавлено в clojure.lang.IFn user/eval2263 (NO_SOURCE_FILE: 2146)