Clojure посмотреть производительность вектор против набора

Question

У меня есть небольшая коллекция отсортированных предметов менее 50. Я часто проверяю, есть ли определенный элемент в коллекции,

это

(time
 (let [a [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]]
   (dotimes [i 100000]
     (filter (fn [[k]] (= k 15)) a))))

занимает 10 мс, если я использую набор, однако

(time
 (let [a (sorted-set 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)]
   (dotimes [i 100000]
   (a 15))))

Это всегда занимает как минимум вдвое больше. Что я не понимаю, так это то, что набор должен быть оптимизирован для поиска, почему фильтр работает быстрее?

Answer 1

Фильтр ленивый. Поскольку вы не оцениваете результат (filter (fn [[k]] (= k 15)) a), он ничего не делает, а создает ленивую последовательность.

На самом деле, (fn [[k]] (= k 15)) даже не правильно, но вы этого не видите, потому что оно не оценено.

(let [a [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]]
     (filter (fn [[k]] (= k 15)) a))
=> java.lang.UnsupportedOperationException: nth not supported on this type: Integer
    [Thrown class java.lang.RuntimeException]

Вы хотите что-то вроде

(time
 (let [a [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]]
   (dotimes [i 100000]
     (some (fn [k] (= k 15)) a))))

"Elapsed time: 173.689 msecs"
nil

Вместо неверного:

(time
 (let [a [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]]
   (dotimes [i 100000]
     (filter (fn [[k]] (= k 15)) a))))

"Elapsed time: 33.852 msecs"
nil

Answer 2

filter - ленивая функция. Попробуйте добавить first, чтобы вызвать ленивую последовательность, генерируемую функцией filter В вашей анонимной функции также есть небольшая ошибка:

(time
 (let [a [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]]
   (dotimes [i 100000]
     (first (filter (fn [k] (= k 15)) a)))))

"Elapsed time: 126.659769 msecs"

отсортированный набор:

(time
 (let [a (sorted-set 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)]
   (dotimes [i 100000]
   (a 15))))
"Elapsed time: 19.467465 msecs"

Надежда, которая имеет смысл.