libera/#sbcl - IRC Chatlog
Search
10:18:59
lukego
Interesting that remove-duplicates is O(n) on lists by default but O(n^2) if a :KEY argument is given. any particular reason for not using the hashtable approach together with :key too or just not yet implemented so?
10:25:26
Shinmera
"The elements of sequence are compared pairwise, and if any two match, then the one occurring earlier in sequence is discarded, unless from-end is true, in which case the one later in sequence is discarded."
10:28:42
lukego
I suppose this is where you want to have a language lawyer on retainer who can say, well actually, the current optimization is also detectable - using TIME to establish that pairwise comparisions aren't happening - so that sets the necessary precedent for extending the optimization to the KEY case...
10:30:59
Shinmera
though I suppose in cases where equality is sort of ambiguous the pairwise comparison is the only way to do it.
10:31:52
flip214
Shinmera: it would be allowed to produce a list (cons (funcall key object) object)) and then remove duplicates on that, right? so two times O(n), which means O(n) overall.
10:32:19
flip214
"The elements of sequence are compared pairwise" doesn't say that KEY is called more than once per element, does it?
10:33:53
flip214
and yes, could be done via a hashtable as well, replacing elements (or not, depending on :from-end)
10:34:20
lukego
I think I'll just eschew these complicates standard functions in favor of serapeum e.g. (filter (distinct) list :key #'foo)
10:36:47
flip214
lukego: well, having the language primitives as efficient as possible wouldn't hurt
10:46:48
lukego
I'll also stay out of that. I'm MTV generation and don't have the temperament for trying to respect the standards at this level of detail