BINARY-SEARCH (THE-ELEMENT VECTOR &KEY (TEST= #'EQL) (TEST< #'<) (GET-ELEMENT #'AREF) (START 0) (END (1- (LENGTH VECTOR))) (NOT-FOUND NIL))
Performs a binary search for an element el on a (sorted) array vec. Return values: - The index where the element was found - Either t (if el was found) or nil (if el was not found) You can ask the function to return something else on failure. Named parameters: - get-element is the function used to retrieve an element of the vector. The default is aref. This should be a FUNCTION, and not a symbol! - start and end are the start and end indices within the array. If they are not supplied, 0 and the last index will be used. - test= and test-before are the tests to be used for equality and for determining precedence between elements. These should be FUNCTIONS, and not symbols! - not-found is the element to be returned when the element is not found. If not-found is set to 't', then, in case of failure, the function will return (i NIL), where i is the index where the element *should* be (or where it could be inserted). So, by default you can test the return inside an (if (binary-search) ...), since it returns either NIL or the position.
Counting sort. Only works for arrays of fixnums. data is the array. The elements in the array must range from zero to k. Optional parameters start and end can be used to specify a subrange of the array to be sorted, but then the new array will have zeroes in all other places (this will be fixed later). This function returns the new array and the counting array, which tells where each each key starts in the new array.
Generalized counting sort: it will sort data structures, provided that there is a way to identify elements with fixnum keys. Parameters: =========== - data is the structure to be sorted. - sorted-data is the new sorted structure, that needs to be previously allocated (and be similar to data) - k is the maximum key value. CAUTION: this function will allocate an array of size k, so if it is too large, it may not work. - start and end define the slice of the keys that will be sorted. - The key function identifies array elements given a fixnum. By default tihs is aref; - The copy-element wihch will be used to copy elements among different posisions needs to have four arguments: + new: the new data structure + new-i: the index in the new data structure + old: the old data structure + old-i: the index in the old data structure So, given those, this function should copy an element from position old-i on structure old to position new-i on structure new. Return value and result: ======================== This function will return the counting array, which shows where in the new structure each key begins: (let ((new-data (make-array 12 :element-type 'fixnum))) (counting-sort-g #(0 2 4 6 0 2 4 6 1 3 5 7) new-data 8 0 11)) => #(0 2 3 5 6 8 9 11) new-data #(0 0 1 2 2 3 4 4 5 6 6 7) count vector: #(0 2 3 5 6 8 9 11) Looking at the count vector, we see that the elements with key '0' start at position '0' in the new structure; the elements with key '1' start at position '2'; elements with key '2' start at '3', etc, and elements with key '7' start at the last position, '11'. Example: ======== ;;; A structure contains two arrays: (defstruct (two-arrays (conc-name ta)) array-one array-two) ;;; Now we sort it, using the first array as the key array, and the second as ;;; the data array. (counting-sort-g two-arrays two-arrays-new 100 10 110 :key #'(lambda (data i) (aref (ta-array-one data) i)) :copy-element #'(lambda (new new-i old old-i) (setf (aref (ta-array-one new) new-i) (aref (ta-array-one old) old-i) (aref (ta-array-two new) new-i) (aref (ta-array-two old) old-i)) Efficiency: =========== If k is not large, this is much faster than Lisp's built-in sort function, because it does not rely on element comparison. cl:sort takes O(n lg n) time, counting-sort-g takes O(n + k) time. On the other hand, it requires O(n + k) additional memory: besides the argument sorted-data, which is provided by you, this function will also allocate an array of size k. For details, see: - Cormen, Leiserson, Rivest and Stein: 'Introduction to algorithms' - Berman and Paul, 'Algorithms: sequential, parallel, and distributed' - Wikipedia: + http://en.wikipedia.org/wiki/Sorting_algorithm + http://en.wikipedia.org/wiki/Counting_sort Because it is generic and works on any data structure, this function can be ten times slower than the counting-sort function in this package, which works on arrays of fixnums only.
GENERATE-RANDOM-ARRAY (SIZE RANGE-START RANGE-END)
Generates an array of fixnums of size n, ranging from 0 to k
Returns a list with the keys of a hash table.
ROBUST-ADJUST-ARRAY (ARRAY SIZE &KEY (ELEMENT-TYPE NIL))
Adjusts the size of an array, setting it to the new one. Also works around an issue with Allegro Common Lisp: in ACL, when you call adjust-array on a non-adjustable array, the resulting array is not necessarily of the same type. It is not a SIMPLE-ARRAY anymore. Dependig on how you try to fix it, you may end up with an array whose element-type is T. So, this is a method for resizing an array and keeping the same array type. Yes, we want SIMPLE-ARRAYs because access is faster. But we also want to adjust them, even if adjusting is slow.
SORTEDP (SEQ &KEY (TEST #'<))
Determines if a sequence is sorted. Will return (t size) on success (where size is the size of the sequence) or nil size), where size is the size of the largest sorted subsequence, from the beginning to the right. For example: (sortedp '(10 20 30 40 1 100)) ==> (NIL, 4) (sortedp #(10 20 30 40 50 100)) ==> (T, 6) See that the size of the sorted sequence is always at least one, except for empty sequences, which are always sorted: (sortedp ()) ==> (T, 0)
SUBST-ALL (SUBST-LIST TREE)
Performs several substitutions on a tree (similar to what subst does). subst-list is a list of substitutions. For example: (subst-all '((a 1) (b 2) (c 3)) '(x y a (z b (u v c)))) => (X Y 1 (Z 2 (U V 3)))
FORMAT-SYMBOL (STRING &REST ARGS)
FORMAT-UNINTERNED-SYMBOL (STRING &REST ARGS)
Return a copy of SEQUENCE which is EQUAL to SEQUENCE but not EQ.
Returns the time elapsed since the stopwatch started, while it was running (pauses are excluded). If the clock was currently running, the time until now is computed. Otherwise, time until the most recenr stop is computed.
Completely resets the stopwatch.
Returns the first element of a sequence.
Sets the start time of the stopwatch to 'now', but does NOT reset the elapsed time.
Pauses the stopwatch and updates the elapsed-time.
SETFCLOCK-ELAPSED-TIME (NEW-VALUE STRUCTURE)
SETFCLOCK-RUNNING (NEW-VALUE STRUCTURE)
SETFCLOCK-START-TIME (NEW-VALUE STRUCTURE)
MAKE-CLOCK (&KEY ((START-TIME DUM688) 0) ((ELAPSED-TIME DUM689) 0) ((RUNNING DUM690) NIL))
DO-SEQUENCE ((IDX SEQ) &REST BODY)
Runs across a sequence (syntatic sugar).
FAST-BINARY-SEARCH (THE-ELEMENT VECTOR &KEY (ELEMENT-TYPE T) (TEST= 'EQL) (TEST< '<) (GET-ELEMENT 'AREF) (START 0) (END NIL) (NOT-FOUND NIL))
This is binary search with type declarations. It's similar to the binary-search function.
GET-BINARY-SEARCH (&KEY (ELEMENT-TYPE T) (TEST= 'EQL) (TEST< '<) (GET-ELEMENT 'AREF) (NOT-FOUND 'NIL))
This function returns a function (with type declarations) that will perform binary search.
WITH-GENSYMS ((&REST NAMES) &BODY BODY)
Expands into code that binds all names to symbols generated by (gensym).