Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the track-best Reference Manual, version 0.1.20130509, generated automatically by Declt version 3.0 "Montgomery Scott" on Tue Dec 22 15:16:36 2020 GMT+0.
• Introduction | What track-best is all about | |
• Systems | The systems documentation | |
• Modules | The modules documentation | |
• Files | The files documentation | |
• Packages | The packages documentation | |
• Definitions | The symbols documentation | |
• Indexes | Concepts, functions, variables and data types |
Track-Best is a Common Lisp library used to track the N best of some series of items. One creates a tracker and then adds scored items to it. The tracker keeps the N best items and returns them at the end.
The main entry point is the function WITH-TRACK-BEST
macro.
(with-track-best (keyword-args)
...body...)
The body
can call (track item score &optional tracker)
as often as
desired. In the end, the with-track-best
will return two values:
the list of best items and the list of their scores.
The keyword-args
can be any of the following:
:NAME variable-name
--- A symbol used as the variable name for the
tracker. This is only needed if you will explicitly refer to the
tracker in the body
statements.:KEEP number-to-keep
--- The number of items to track. This
defaults to 1
item.:KEEP-TIES whether-to-keep-ties
--- If true, then items with the
same score will all be kept until there are KEEP items with better
scores. This defaults to 'NIL'.:ORDER-BY-FN function-to-compare-scores
--- The function used to
determine if one score is larger or smaller than another score. The
default for this argument is #'>
:ALWAYS-RETURN-LIST t-or-nil
--- If always-return-list
is true,
then WITH-TRACK-BEST
will return a list even when KEEP
is 1
.
If always-return-list
is not true, then WITH-TRACK-BEST
will
return the single item when KEEP
is 1
. The default for this
argument is NIL
.:RETURN-BEST t-or-nil
--- if return-best
is NIL
, then the form
returns the value(s) from the last expression in the body
rather
than the best items. This argument defaults to T
. Note: This
argument is evaluated at macroexpansion time, not at runtime.The other useful entry point is the MAP-BEST
which takes a function
and an optional tracker. It calls the function for each item
currently in the best list of the tracker (from best to worst).
MAP-BEST
passes two parameters to the function: the item and its
score. The MAP-BEST
function returns a list of the results of those
function calls.
(with-track-best (:keep 3 :return-best nil)
(dolist (v '(-5 -3 -1 0 2 4))
(track v (abs v)))
(map-best #'(lambda (item score)
(* item score))))
=> '(-25 16 -9)
Given two strings S1
and S2
, find the longest substring they have
in common.
(let ((s1 "Keep playing cards on Friday. Get smart.")
(s2 "Thank G-d it's Friday!"))
(with-track-best ()
(dotimes (len (length s1))
(dotimes (offset (- (length s1) len -1))
(let ((needle (subseq s1 offset (+ offset len))))
(when (search needle s2 :test #'string=)
(track needle len)))))))
The outer DOTIMES
loop determines the length substring of S1
to
look for in S2
. The inner DOTIMES
loop picks the offset to start
the substring of S1
. Then, if the substring is found in S2
, it is
tracked with its score being its length.
Given a list of vertexes VERTEX-LIST
, find the vertex farthest from
a TARGET
vertex based on a given DISTANCE
function.
(defun find-farthest (target vertex-list distance-fn)
(with-track-best ()
(dolist (v vertex-list)
(track v (funcall distance-fn v target))))))
Given a list of vertexes VERTEX-LIST
, find the three that are closest
to a TARGET
vertex based on a given DISTANCE
function.
(defun find-three-closest (target vertex-list distance-fn)
(with-track-best (:keep 3 :order-by-fn #'<)
(dolist (v vertex-list)
(track v (funcall distance-fn v target))))))
The :ORDER-BY-FN
function here specifies that the best vectors are
the ones with the smallest score. The scores used here are the
distance from the TARGET
as given by the DISTANCE-FN
.
Suppose you had a list of various states. For each state you had a list of different cities and their altitude. Find the highest altitude in each state and find the state with the lowest high.
(let ((data '(("Alabama" ("Birmingham" 664)
("Mobile" 218)
("Montegomery" 221))
("Alaska" ("Anchorage" 144)
("Fairbanks" 531))
("Arizona" ("Grand Canyon" 6606)
("Phoenix" 1132)
("Tuscon" 2641)))))
(with-track-best (:order-by-fn #'<)
(dolist (state-info data)
(multiple-value-bind (city altitude)
(with-track-best ()
(dolist (city-info (rest state-info))
(track (first city-info) (second city-info))))
(track (list (first state-info) city) altitude)))))
=> (values '("Alaska" "Fairbanks") 531)
The inner WITH-TRACK-BEST
here tracks the highest city in a given
state. The outer WITH-TRACK-BEST
trackes the lowest of the highest
cities.
Given a list of numbers, return a list containing the lowest number and highest number from the list.
(with-track-best (:name lowest
:order-by-fn #'<
:return-best nil)
(with-track-best (:name highest
:return-best nil)
(dolist (v '(2 4 6 8 10 1 3 5 7 9))
(track v v lowest)
(track v v highest))
(list (caar (map-best #'cons lowest))
(caar (map-best #'cons highest)))))
In this example, we used the :NAME
to specify two different
trackers. In our loop, we tracked each value with both trackers. In
the end, we also used the :RETURN-RESULTS NIL
directive so that the
returned value would be our LIST
expression rather than the best
result from the LOWEST
tracker.
If the :KEEP-TIES
parameter is not NIL, then all items with the best
score will be returned. The order of these items is not guaranteed.
(with-track-best (:keep-ties t)
(dolist (c '((:FIVE 5) (:EIGHT 8)
(:CINQO 5) (:OCHO 8)
(:CINQ 5) (:HUIT 8)))
(track (first c) (second c))))
=> (values '(:EIGHT :HUIT :OCHO) '(8 8 8))
If the :KEEP
parameter is 1
, the first item tracked with the best
score will be returned. If the :KEEP
parameter is greater than one,
there is no guarantee about which items are kept when multiple items
of the same score are found. For example, the following form will
definitely return (VALUES :EIGHT 8)
.
(with-track-best ()
(dolist (c '((:FIVE 5) (:EIGHT 8)
(:CINQO 5) (:OCHO 8)
(:CINQ 5) (:HUIT 8)))
(track (first c) (second c))))
=> (values :EIGHT 8)
On the other hand, this snippet will not guarantee the order in which
:EIGHT
, :OCHO
, and :HUIT
appear nor which of :FIVE
, :CINQO
,
or :CINQ
will be included.
(with-track-best (:keep 4)
(dolist (c '((:FIVE 5) (:EIGHT 8)
(:CINQO 5) (:OCHO 8)
(:CINQ 5) (:HUIT 8)))
(track (first c) (second c))))
=> (values ??? '(8 8 8 5))
To be sure, the answer is deterministic. Given the same inputs in the same order, the same output will be generated. There are two caveats to this:
:KEEP
is greater than one and ':KEEP-TIES' is NIL.Next: Modules, Previous: Introduction, Up: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
• The track-best system |
Patrick Stein <pat@nklein.com>
Free
Macros/functions for tracking the best items. See the README.md for more details.
0.1.20130509
track-best.asd (file)
Modules are listed depth-first from the system components tree.
• The track-best/src module |
track-best (system)
src/
Files are sorted by type and then listed depth-first from the systems components trees.
• Lisp files | ||
• Static files |
Next: Static files, Previous: Files, Up: Files [Contents][Index]
Next: The track-best/src/package․lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
track-best.asd
track-best (system)
Next: The track-best/src/types․lisp file, Previous: The track-best․asd file, Up: Lisp files [Contents][Index]
src (module)
src/package.lisp
Next: The track-best/src/globals․lisp file, Previous: The track-best/src/package․lisp file, Up: Lisp files [Contents][Index]
package.lisp (file)
src (module)
src/types.lisp
Next: The track-best/src/insert․lisp file, Previous: The track-best/src/types․lisp file, Up: Lisp files [Contents][Index]
types.lisp (file)
src (module)
src/globals.lisp
*current-best-tracker* (special variable)
Next: The track-best/src/methods․lisp file, Previous: The track-best/src/globals․lisp file, Up: Lisp files [Contents][Index]
globals.lisp (file)
src (module)
src/insert.lisp
insert-tracked-item (function)
Next: The track-best/src/track-best․lisp file, Previous: The track-best/src/insert․lisp file, Up: Lisp files [Contents][Index]
insert.lisp (file)
src (module)
src/methods.lisp
Previous: The track-best/src/methods․lisp file, Up: Lisp files [Contents][Index]
methods.lisp (file)
src (module)
src/track-best.lisp
with-track-best (macro)
Previous: Lisp files, Up: Files [Contents][Index]
• The track-best/readme.md file |
Previous: Static files, Up: Static files [Contents][Index]
track-best (system)
README.md
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
• The track-best package |
package.lisp (file)
common-lisp
Definitions are sorted by export status, category, package, and then by lexicographic order.
• Exported definitions | ||
• Internal definitions |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
• Exported macros | ||
• Exported functions |
Next: Exported functions, Previous: Exported definitions, Up: Exported definitions [Contents][Index]
track-best.lisp (file)
Previous: Exported macros, Up: Exported definitions [Contents][Index]
methods.lisp (file)
Add the ITEM with SCORE to the TRACKER.
methods.lisp (file)
Previous: Exported definitions, Up: Definitions [Contents][Index]
• Internal special variables | ||
• Internal functions | ||
• Internal structures | ||
• Internal types |
Next: Internal functions, Previous: Internal definitions, Up: Internal definitions [Contents][Index]
The current best-tracker instance.
globals.lisp (file)
Next: Internal structures, Previous: Internal special variables, Up: Internal definitions [Contents][Index]
types.lisp (file)
types.lisp (file)
types.lisp (file)
types.lisp (file)
types.lisp (file)
types.lisp (file)
types.lisp (file)
types.lisp (file)
types.lisp (file)
types.lisp (file)
types.lisp (file)
types.lisp (file)
Insert the ITEM with the given SCORE into the TRACKER.
insert.lisp (file)
types.lisp (file)
types.lisp (file)
Next: Internal types, Previous: Internal functions, Up: Internal definitions [Contents][Index]
types.lisp (file)
structure-object (structure)
(integer 1 *)
1
best-item-list-size (function)
(setf best-item-list-size) (function)
0.0
best-item-list-score (function)
(setf best-item-list-score) (function)
best-item-list-items (function)
(setf best-item-list-items) (function)
types.lisp (file)
structure-object (structure)
list
best-tracker-best (function)
(setf best-tracker-best) (function)
(integer 0 *)
0
best-tracker-size (function)
(setf best-tracker-size) (function)
1
best-tracker-keep (function)
(setf best-tracker-keep) (function)
best-tracker-keep-ties (function)
(setf best-tracker-keep-ties) (function)
track-best::order-by-fn
(function >)
best-tracker-order-by-fn (function)
(setf best-tracker-order-by-fn) (function)
Previous: Internal structures, Up: Internal definitions [Contents][Index]
types.lisp (file)
Previous: Definitions, Up: Top [Contents][Index]
• Concept index | ||
• Function index | ||
• Variable index | ||
• Data type index |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
Jump to: | F L M S T |
---|
Jump to: | F L M S T |
---|
Next: Variable index, Previous: Concept index, Up: Indexes [Contents][Index]
Jump to: | (
B C F I M T W |
---|
Jump to: | (
B C F I M T W |
---|
Next: Data type index, Previous: Function index, Up: Indexes [Contents][Index]
Jump to: | *
B I K O S |
---|
Jump to: | *
B I K O S |
---|
Previous: Variable index, Up: Indexes [Contents][Index]
Jump to: | B O P S T |
---|
Jump to: | B O P S T |
---|