What is the best way to process this list
in [Lisp]
|
From: Kenneth Tilton on 4 Jan 2010 12:33 Pascal J. Bourguignon wrote: > Kenneth Tilton <kentilton(a)gmail.com> writes: > >> Pascal J. Bourguignon wrote: >> >>>> Using a plist is not the lay to go. Use defstruct. Simpler than a >>>> plist, really, and massively more efficient. >>> False. Structures are not always faster than plist. Notaby, >>> implementations may typecheck the structure object, which slows >>> structure accessors so much that plist up to 5 or even more slots is >>> faster. >> Rubbish! What crappy implementation are you imagining for these >> incredibly slow defstructs (by which I mean which Lisp and how do they >> implement defstructs by default? Lemme see some timings! >> >> kt > > Existance proof: > > C/USER[11]> (defstruct ss a b c d e) > SS > C/USER[12]> (let ((s (make-ss :a 42))) (time (loop :repeat 100000 :do (ss-a s)))) > Real time: 0.494208 sec. > Run time: 0.464029 sec. > Space: 804400 Bytes > NIL > C/USER[13]> (defstruct (sl (:type list)) a b c d e) > SL > C/USER[14]> (let ((s (make-sl :a 42))) (time (loop :repeat 100000 :do (sl-a s)))) > Real time: 0.489189 sec. > Run time: 0.424026 sec. > Space: 804400 Bytes > GC: 1, GC time: 0.012001 sec. > NIL > C/USER[15]> (values (lisp-implementation-type) (lisp-implementation-version)) > "CLISP" ; > "2.41 (2006-10-13) (built on thalassa.lan.informatimago.com [192.168.1.198])" > > C/USER[17]> (disassemble 'ss-a) > > Disassembly of function SS-A > (CONST 0) = SS > (CONST 1) = 1 > 1 required argument > 0 optional arguments > No rest parameter > No keyword parameters > 5 byte-code instructions: > 0 (CONST&PUSH 0) ; SS > 1 (LOAD&PUSH 2) > 2 (CONST&PUSH 1) ; 1 > 3 (CALLS2 47) ; SYSTEM::%STRUCTURE-REF > 5 (SKIP&RET 2) > NIL > C/USER[18]> (disassemble 'sl-a) > > Disassembly of function SL-A > 1 required argument > 0 optional arguments > No rest parameter > No keyword parameters > 3 byte-code instructions: > 0 (LOAD 1) > 1 (CAR) > 2 (SKIP&RET 2) > NIL > C/USER[19]> > PWUAHAHAHAHA!!! What made you choose slot A? PWUAHAHAHHAHAAH!!!! kenny -- http://thelaughingstockatpngs.com/ http://www.facebook.com/pages/The-Laughingstock/115923141782?ref=nf
From: Pascal J. Bourguignon on 4 Jan 2010 14:52 Kenneth Tilton <kentilton(a)gmail.com> writes: > PWUAHAHAHAHA!!! What made you choose slot A? PWUAHAHAHHAHAAH!!!! aref, or a structure slot access could involve a multiplication, which is often slower tha a few memory accesses (as long as the cache is hit). In any case, my advice is to use defstruct, and once your application is debugged, if you need to optimize speed and you didn't use generic function on these structures, try out (:type vector) or (:type list). -- __Pascal Bourguignon__ http://www.informatimago.com/
From: Thomas A. Russ on 4 Jan 2010 14:59 Cecil Westerhof <Cecil(a)decebal.nl> writes: > > > > To get the ingredient list for my brownies recipe, I use: > > (getf (get-recipe "Brownies") :ingredients) > > > > and get: > > ((:QUANTITY "5" :TYPE "stuk" :INGREDIENT "eieren") > > (:QUANTITY "350" :TYPE "gram" :INGREDIENT "suiker") > > (:QUANTITY "175" :TYPE "gram" :INGREDIENT "boter (gesmolten)") > > (:QUANTITY "1" :TYPE "eetlepel" :INGREDIENT "vanille essence") > > (:QUANTITY "175" :TYPE "gram" :INGREDIENT "bloem") > > (:QUANTITY "100" :TYPE "gram" :INGREDIENT "cacao") > > (:QUANTITY "100" :TYPE "gram" :INGREDIENT "(walnoten)") > > (:QUANTITY "100" :TYPE "gram" :INGREDIENT "(kokos)") > > (:QUANTITY "2" :TYPE "stuk" :INGREDIENT "(bananen)") > > (:QUANTITY "100" :TYPE "gram" :INGREDIENT "(hazelnoten)")) > > > > This I want to display and this can be done with: > > (dolist (this-ingredient (getf (get-recipe "Brownies") :ingredients)) > > (format t "~3@a ~8a ~a~%" > > (getf this-ingredient :quantity) > > (getf this-ingredient :type) > > (getf this-ingredient :ingredient))) > > > > and this gives: > > 5 stuk eieren > > 350 gram suiker > > 175 gram boter (gesmolten) > > 1 eetlepel vanille essence > > 175 gram bloem > > 100 gram cacao > > 100 gram (walnoten) > > 100 gram (kokos) > > 2 stuk (bananen) > > 100 gram (hazelnoten) > > > > At the moment this is hard coded, but of course this is not what I want. > > I want only to use the space that is needed. The way I am thinking about > > it, is to do two dolist and in the first I could find the longest > > lengths for :quantity and :type and use those in the format. I was just > > wondering if there is not a more efficient way to do this. > > I already made a function for it: > (defun display-ingredients (recipe) > (let ((quantity-length 0) > (temp) > (type-length 0)) > (dolist (this-ingredient (getf recipe :ingredients)) > (setq temp (length (getf this-ingredient :quantity))) > (when (> temp quantity-length) > (setq quantity-length temp)) > (setq temp (length (getf this-ingredient :type))) > (when (> temp type-length) > (setq type-length temp))) > (dolist (this-ingredient (getf recipe :ingredients)) > (format t "~v@a ~va ~a~%" > quantity-length (getf this-ingredient :quantity) > type-length (getf this-ingredient :type) > (getf this-ingredient :ingredient))))) > So it does what I want, but I was just wondering if there was a better > way? In this particular case it is not very important, because the lists > will not be very big, but I like to make things for the general case, so > that when the data set changes there are no nasty surprises. Well, I would think that a "better" way might be one that is more flexible. Also, you could improve robustness by handling the case where there is no corresponding value. Consider the following code for doing the formatting. It does still need to go through the list twice, but I don't think there is a way to avoid that. (defun display-formatted-properties (keylist list-of-plists stream) (let ((field-lengths (make-array (length keylist) :initial-element 0))) (loop for plist in list-of-plists do (loop for key in keylist as i upfrom 0 do (setf (aref field-lengths i) (max (aref field-lengths i) (length (getf plist key "")))))) (loop for plist in list-of-plists do (loop for key in keylist as i upfrom 0 do (format stream " ~vA" (aref field-lengths i) (getf plist key ""))) (format stream "~%")))) I used LOOP mainly to get parallel stepping in the inner loop. One could use DOLIST with explicit assignments instead. Note that this doesn't do different left/right justification, although one could add that as an extension. (display-formatted-properties '(:quantity :type :ingredient) (getf (get-recipe "Brownies") :ingredients) *standard-output*) 5 stuk eieren 350 gram suiker 175 gram boter (gesmolten) 1 eetlepel vanille essence 175 gram bloem 100 gram cacao 100 gram (walnoten) 100 gram (kokos) 2 stuk (bananen) 100 gram (hazelnoten) If you want to have this work with more than just strings, you can achieve that by using format on the value returned by GETF when computing the length. But if you do that, it may be just better to collect all of the string values along with the field lengths so that you (a) only call FORMAT once per data item and (b) are sure that the length and the output formats remain the same. This will also do justification for :LEFT :RIGHT or :CENTER if specified, and will also optionally produce column headers based on the keywords. (defun display-formatted-properties (keylist list-of-plists stream &key alignment include-header-p) (if alignment (assert (= (length keylist) (length alignment))) (setq alignment (make-list (length keylist) :initial-element :left))) (let ((field-lengths (make-array (length keylist) :initial-element 0)) (formatted-strings nil)) (setq formatted-strings (loop for plist in list-of-plists collect (loop for key in keylist as i upfrom 0 as formatted-value = (format nil "~A" (getf plist key "")) do (setf (aref field-lengths i) (max (aref field-lengths i) (length formatted-value))) collect formatted-value))) (when include-header-p (push (loop for key in keylist as keystring = (format nil "~A" key) as i upfrom 0 do (setf (aref field-lengths i) (max (aref field-lengths i) (length keystring))) collect keystring) formatted-strings)) (loop for strings in formatted-strings do (loop for item in strings as align in alignment as i upfrom 0 as width = (aref field-lengths i) do (when (> width 0) ; Only do non-empty fields (when (> i 0) (format stream " ")) (ecase align (:left (format stream "~vA" width item)) (:right (format stream "~v@A" width item)) (:center (format stream "~v:@<~A~>" width item))))) (format stream "~%")))) (display-formatted-properties '(:quantity :type :ingredient) (getf (get-recipe "Brownies") :ingredients) t) 5 stuk eieren 350 gram suiker 175 gram boter (gesmolten) 1 eetlepel vanille essence 175 gram bloem 100 gram cacao 100 gram (walnoten) 100 gram (kokos) 2 stuk (bananen) 100 gram (hazelnoten) (display-formatted-properties '(:quantity :type :ingredient) (getf (get-recipe "Brownies") :ingredients) t :include-header-p t :alignment '(:right :left :left)) QUANTITY TYPE INGREDIENT 5 stuk eieren 350 gram suiker 175 gram boter (gesmolten) 1 eetlepel vanille essence 175 gram bloem 100 gram cacao 100 gram (walnoten) 100 gram (kokos) 2 stuk (bananen) 100 gram (hazelnoten) (display-formatted-properties '(:ingredient :quantity :type) (getf (get-recipe "Brownies") :ingredients) t :include-header-p t :alignment '(:center :right :left)) INGREDIENT QUANTITY TYPE eieren 5 stuk suiker 350 gram boter (gesmolten) 175 gram vanille essence 1 eetlepel bloem 175 gram cacao 100 gram (walnoten) 100 gram (kokos) 100 gram (bananen) 2 stuk (hazelnoten) 100 gram ====================================== And then there is the entire set of solutions that use the MAPing functions instead of loops.
From: Kenneth Tilton on 4 Jan 2010 15:32 Pascal J. Bourguignon wrote: > Kenneth Tilton <kentilton(a)gmail.com> writes: >> PWUAHAHAHAHA!!! What made you choose slot A? PWUAHAHAHHAHAAH!!!! > > aref, or a structure slot access could involve a multiplication, which > is often slower tha a few memory accesses (as long as the cache is hit). Keep wiggling, and while you are at it let's review the record: Pascal J. Bourguignon wrote: > Kenneth Tilton <kentilton(a)gmail.com> writes: >> Using a plist is not the lay to go. Use defstruct. Simpler than a >> plist, really, and massively more efficient. > > False. Structures are not always faster than plist. False? I said "plist" and you said "plist" and you offer timings and disassembly of a list defstruct? Tsk, tsk. Let's see those fancy timings and disassemblies of (getf x :ingredient) -- yes, it is my turn to stack the deck, we'll take the third attribute. kt -- http://thelaughingstockatpngs.com/ http://www.facebook.com/pages/The-Laughingstock/115923141782?ref=nf
From: mdj on 4 Jan 2010 18:58
On Jan 5, 5:52 am, p...(a)informatimago.com (Pascal J. Bourguignon) wrote: > Kenneth Tilton <kentil...(a)gmail.com> writes: > > PWUAHAHAHAHA!!! What made you choose slot A? PWUAHAHAHHAHAAH!!!! > > aref, or a structure slot access could involve a multiplication, which > is often slower tha a few memory accesses (as long as the cache is hit). For aref, that's true (unless the index is a power of two into a one dimensional array) but not for structures. There's no point at all in having generated code recompute a value that is derivable at structure definition time. Matt |