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 (keyword-args) ...body...)
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.
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
:KEEP number-to-keep--- The number of items to track. This defaults to
: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-listis true, then
WITH-TRACK-BESTwill return a list even when
always-return-listis not true, then
WITH-TRACK-BESTwill return the single item when
1. The default for this argument is
:RETURN-BEST t-or-nil--- if
NIL, then the form returns the value(s) from the last expression in the
bodyrather 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)
Example: Finding the longest matching substring in two strings
Given two strings
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)))))))
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.
Example: Finding the farthest vertex from a point
Given a list of vertexes
VERTEX-LIST, find the vertex farthest from a
TARGET vertex based on a given
(defun find-farthest (target vertex-list distance-fn) (with-track-best () (dolist (v vertex-list) (track v (funcall distance-fn v target))))))
Example: Finding the three closest vertexes to a point
Given a list of vertexes
VERTEX-LIST, find the three that are closest to a
TARGET vertex based on a given
(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))))))
: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
Example: The lowest highest point
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)
WITH-TRACK-BEST here tracks the highest city in a given state. The outer
WITH-TRACK-BEST trackes the lowest of the highest cities.
Example: Finding the lowest and highest numbers in a list
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
Example: Keeping ties
: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))
Warning about how ties are handled
: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
:HUIT appear nor which of
: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:
- Where a tie gets inserted amongst its peers is highly sensitive to the number of items being kept and where its peers are in the list at the time of insertion.
- More importantly, I make no guarantee that this order will be preserved across releases. You should not depend on particular behavior when
:KEEPis greater than one and ':KEEP-TIES' is NIL.
- Patrick Stein <email@example.com>