Search
Saturday, 22nd of July 2017, 1:12:15 UTC
2:07:58
warweasle1
** NICK warweasle
5:11:56
beach
Good morning everyone!
10:13:32
axion
I'm looking for help in a basic task I'm trying to do as efficiently as I can.
10:14:43
axion
http://paste.lisp.org/display/351414
10:16:46
|3b|
ACTION would just sort list then split result
10:18:46
phoe
sort list then destructively split it
10:19:27
axion
Is there a common 'split' function or should I look to build one?
10:19:30
phoe
or alternatingly push into two accumulator lists, then nreverse them
10:19:37
phoe
axion: that's a good question
10:19:41
|3b|
ACTION probably wouldn't even bother with destructive split
10:20:06
phoe
|3b|: he wants efficience, I think destructive splitting of conses is going to be as efficient as he can get it
10:20:16
phoe
performance- and consing-wise
10:20:38
|3b|
yeah, i was including programmer efficieny as well :)
10:20:46
axion
How would you efficiently split a list?
10:21:08
phoe
if you want programmer effiicience, alternatingly push into two lists, then nreverse them
10:21:20
phoe
if you want fastest possible code, I think I have a possible algorithm in my mind
10:21:39
|3b|
(loop for (a b) on (sort ...) by #'cddr collect a into as when b collect b into bs finally (return (list as bs)))
10:21:45
axion
Doesn't have to be 'fastest possible' but this will occur with every page load, so milliseconds count.
10:21:53
phoe
axion: how long are the lists?
10:21:57
phoe
how many elements are there?
10:21:58
jackdaniel
axion: use uiop:while-collecting (or even better - cmuutil collect macro)
10:22:10
jackdaniel
that's performance-best choice for both metrics
10:22:18
|3b|
actually, "most efficient" in that sense would probably be "cache it" :p
10:22:28
phoe
yes, are the lists dynamic?
10:22:38
axion
Yeah they are pretty dynamic
10:23:10
|3b|
even then, cache when they change rather than on access might win unless they changee more than they are read
10:23:11
jackdaniel
because it doesn't cons unnecessarily, doesn't reverse and keeps pointer to the list end
10:23:58
jackdaniel
oh, sorry, uiop:while-collecting does a lot of things, I'd go with cmuutil collect macro after all
10:24:22
|3b|
ACTION also notes that the performance loss from non-destructive split probably wouldn't show up on that page load anyway :p
10:24:46
|3b|
(which admittedly isn't a very good argument in favor of it)
10:25:03
axion
Yeah, I don't need this to be 'fastest possible'. Just not 'slowest possible'.
10:25:26
axion
I am not trying to introduce bottlenecks when I scale this larger
10:25:52
phoe
my algorithm: grab references to 1st and 2nd cons of the list. set the CDR of the first cons to the 3rd cons, set the CDR of the first cons to the CDDDR of the first cons, set the CDR of the second cons to the CDDDR of the second cons. Use the CDRs of the first and second cons as the new values for the first and second cons, loop until the CDRs of the lists are NIL.
10:26:50
axion
The simplest code can be continually made 'fastest possible' over a lifetime for a programmer. I should have known better to phrase that a bit better
10:29:44
phoe
Let me write a PoC of that
10:29:47
beach
axion: I am fine thanks :)
10:30:16
|3b|
loop/collect version sorts/splits the symbols from CL: in a little over 1.6 million cycles
10:31:19
axion
How do I use sort to case-insensitively sort?
10:31:35
specbot
http://www.lispworks.com/reference/HyperSpec/Body/f_stgeq_.htm
10:33:12
axion
beach: So is a lot of things here, such as algorithm efficiency and Emacs buffer data structures being a bad data structure for their use :)
10:33:39
phoe
axion: http://paste.lisp.org/display/351414#1
10:34:26
axion
Thanks for all the suggestions!
10:34:34
phoe
this splits the list into (1 3 5 7 9) (2 4 6 8 0)
10:37:39
axion
|3b|: some minor problems with your implementation, but nothing big
10:38:21
|3b|
ACTION just typed it into IRC without testing, what did i miss?
10:39:32
axion
I guess there's nothing wrong with it really. I just didn't expect a 2 element list of NIL's if given an initiallly empty list
10:40:14
|3b|
yeah, i guess problem is underspecified for that case :)
10:40:26
axion
|3b|: What is the point of the WHEN clause? I don't see when it would change anything
10:40:37
|3b|
splitting empty list into 2 empty lists sounds reasonable to me though :)
10:40:59
|3b|
with odd number of elements you'd get an extra nil at end of 2nd list
10:41:14
axion
That's not the case for me
10:41:24
axion
oh yeah. repl out of sync
10:46:24
|3b|
about 1/3 second to run on all symbols in my image, ~330k
10:46:59
|3b|
(well, all symbols iterated by do-symbols)
10:47:15
axion
phoe's implementation is extremely fast, but I was expecting that keeping a reference to tail
10:47:25
|3b|
but with lots of duplicates
10:49:37
|3b|
and looks like almost all of that is spent sorting
13:00:22
rk[ghost]
equivalent of assoc with strings instead of symbols?
13:01:39
shka_
rk[ghost]: pass equal as test
13:02:11
phoe
if only strings are taken into account here
13:02:16
shka_
axion: if you care that much about performance, use vector instead of list
13:02:25
shka_
sorting lisp is exactly fast
13:02:39
shka_
phoe: ok, string= will do
13:03:20
shka_
sorting list if not exactly fast :P
13:06:47
rk[ghost]
ah! you can past a test in to assoc, excellent
13:07:02
rk[ghost]
shka_: phoe: thaaanks!
13:07:16
rk[ghost]
quite a sensible implementation to allow test passing
13:07:26
rk[ghost]
ACTION starts whistleing
13:07:35
shka_
oh, most of those functions accept :test
13:08:08
rk[ghost]
doh, i am always so unaware of the gigantic library of CL
13:08:14
rk[ghost]
i end up implementing so many things myself -.-
13:08:23
shka_
it is not that gigantic to be honest
13:08:44
rk[ghost]
sure, but my head keeps thinking all i have is lisp 1.5
13:08:53
shka_
in fact it can be considered quite small when compared to other languages nowdays
13:09:20
rk[ghost]
maybe so. but even something like nth it is taking me a while to be like, use that and quit doing strange caaaddars..
13:10:01
shka_
well, honestly i'm also using stuff like cdaadr
13:10:12
shka_
not proud of it, though :D
13:10:30
shka_
usually, destructuring-bind is great
13:10:31
rk[ghost]
i find it difficult that CL has many ways to go about stuff
13:10:51
shka_
oh, well, it certainly has
13:11:00
shka_
anyway, I'm going afk now
13:11:07
shka_
glad we could help you :-)
13:11:08
rk[ghost]
i find i spend more time trying to decide how fancy to be about a solution rather than just solving it and moving on.
Saturday, 22nd of July 2017, 13:12:15 UTC