So I understand that 'seq' is the idiomatic way to see if a
collection/sequence is empty.
Logically I'm looking for an O(1) predicate with which I can determine if a
seq/collection is empty, and a well behaved
one that is idempotent and side effect free (for general performance
reasons).
'seq' leaves something to be desired here since it does heap allocations
when called with various types of arguments.
I'll also freely confess that I dislike seq as an emptiness predicate, I
like empty? and not-empty? types of things, even better,
I loved Common Lisp's treatment where NIL and empty lists have the same
value in conditional situations
(i.e. if x is an empty list it is == nil and is false, unlike Clojure). I
guess what I'm saying here is that 'seq' as idiomatic clojure for
empty tests is distasteful.
In my own personal libraries I use a predicate to give the common lisp like
semantics I desire, but it still calls clojure.core/empty?,
which still calls 'seq'. So all I've done is make the test more expensive
even if I find it more readable.
While looking at the Clojure 1.7 implementation of 'seq' today in RT.java,
I happened across the implementation of 'count',
and it occurred to me that it was a much leaner and meaner test for empty
sequences than 'seq'. So here are some timings.
user> (doseq [thing [[] {} #{} (seq []) (into [] (range 0 1000)) (range 0
1000)]]
(println "Time for 1M seq on" (type thing))
(time (dotimes [i 1000000] (seq thing))))
Time for 1M seq on clojure.lang.PersistentVector
"Elapsed time: 18.993869 msecs"
Time for 1M seq on clojure.lang.PersistentArrayMap
"Elapsed time: 14.461354 msecs"
Time for 1M seq on clojure.lang.PersistentHashSet
"Elapsed time: 23.044994 msecs"
Time for 1M seq on nil
"Elapsed time: 8.291876 msecs"
Time for 1M seq on clojure.lang.PersistentVector
"Elapsed time: 21.214759 msecs"
Time for 1M seq on clojure.lang.LongRange
"Elapsed time: 6.27834 msecs"
Note the time on PersistentVector, we may have an O(n) implemention of `seq`
which is undesirable for an emptiness predicate. Larger inputs require
more time for 'seq' to return.
Now compare the same timings with 'count', adding in a clojure-level
emptyness test (which would
no doubt be faster in RT.java):
user> (doseq [thing [[] {} #{} (seq []) (into [] (range 0 1000)) (range 0
1000)]]
(println "Time for 1M count on" (type thing))
(time (dotimes [i 1000000] (== (count thing) 0))))
Time for 1M count on clojure.lang.PersistentVector
"Elapsed time: 8.061005 msecs"
Time for 1M count on clojure.lang.PersistentArrayMap
"Elapsed time: 7.297715 msecs"
Time for 1M count on clojure.lang.PersistentHashSet
"Elapsed time: 10.165718 msecs"
Time for 1M count on nil
"Elapsed time: 4.190523 msecs"
Time for 1M count on clojure.lang.PersistentVector
"Elapsed time: 8.772564 msecs"
Time for 1M count on clojure.lang.LongRange
"Elapsed time: 27.166397 msecs"
Except for the LongRange input, `count` is much faster.
So I'm just bringing it up for discussion, wondering if we can get a faster
clojure.core
implementation of `empty?`.
That said, there is one apples-to-apples problem in the above.
(seq x) returns nil if empty. (== (count x) 0) returns true if nil is
empty.
Clojure neophyte that I am, I can't understand where there is not a "!="
function for numbers.
Wrapping the above test in a 'not' gives:
user> (doseq [thing [[] {} #{} (seq []) (into [] (range 0 1000)) (range 0
1000)]]
(println "Time for 1M count on" (type thing))
(time (dotimes [i 1000000] (not (== (count thing) 0)))))
Time for 1M count on clojure.lang.PersistentVector
"Elapsed time: 15.961422 msecs"
Time for 1M count on clojure.lang.PersistentArrayMap
"Elapsed time: 11.12519 msecs"
Time for 1M count on clojure.lang.PersistentHashSet
"Elapsed time: 12.899191 msecs"
Time for 1M count on nil
"Elapsed time: 7.119841 msecs"
Time for 1M count on clojure.lang.PersistentVector
"Elapsed time: 11.454936 msecs"
Time for 1M count on clojure.lang.LongRange
"Elapsed time: 28.544915 msecs"
The O(1) times double when wrapping the test in 'not'.
Perhaps some clojurian will tell me what I should use.
Btw, don't even thing about 'not=':
user> (doseq [thing [[] {} #{} (seq []) (into [] (range 0 1000)) (range 0
1000)]]
(println "Time for 1M count on" (type thing))
(time (dotimes [i 1000000] (not= (count thing) 0))))
Time for 1M count on clojure.lang.PersistentVector
"Elapsed time: 44.768754 msecs"
Time for 1M count on clojure.lang.PersistentArrayMap
"Elapsed time: 40.158507 msecs"
Time for 1M count on clojure.lang.PersistentHashSet
"Elapsed time: 41.868068 msecs"
Time for 1M count on nil
"Elapsed time: 36.098277 msecs"
Time for 1M count on clojure.lang.PersistentVector
"Elapsed time: 42.149571 msecs"
Time for 1M count on clojure.lang.LongRange
"Elapsed time: 59.107886 msecs"
Well, that's not fair of course since '(not (==' and '(not (=' are two
different things.
But then you'd expect '=' to be as slow, and it isn't, so somethings gets
optimized with '=' vs. '=='.
user> (doseq [thing [[] {} #{} (seq []) (into [] (range 0 1000)) (range 0
1000)]]
(println "Time for 1M count on" (type thing))
(time (dotimes [i 1000000] (= (count thing) 0))))
Time for 1M count on clojure.lang.PersistentVector
"Elapsed time: 10.324226 msecs"
Time for 1M count on clojure.lang.PersistentArrayMap
"Elapsed time: 7.858452 msecs"
Time for 1M count on clojure.lang.PersistentHashSet
"Elapsed time: 10.132961 msecs"
Time for 1M count on nil
"Elapsed time: 4.097666 msecs"
Time for 1M count on clojure.lang.PersistentVector
"Elapsed time: 8.661771 msecs"
Time for 1M count on clojure.lang.LongRange
"Elapsed time: 26.705511 msecs"
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
