Good day list,
I believe the code below might meet the conservative standards of Alexandria.
What do you think?
(defun bisect (test n &optional (base 0)) "Find, using bisection, the largest positive integer below N and above, or equal to BASE, which satisfies TEST of one argument. Assumes monotonous truth value of TEST." (labels ((traverse (x fallback attack) (if (funcall test x) (cond ((zerop attack) x) ((= attack 1) (if (funcall test (1+ x)) (1+ x) x)) (t (rebalance x (1+ attack)))) (cond ((= fallback 1) (when (funcall test (1- x)) (1- x))) (t (rebalance (- x fallback) fallback))))) (rebalance (origin span &aux (middle (ash span -1))) (traverse (+ origin middle) middle (- span middle 1)))) (rebalance base (- n base))))
regards, Samium Gromoff
On Mon, Apr 14, 2008 at 8:56 PM, Samium Gromoff _deepfire@feelingofgreen.ru wrote:
Good day list,
I believe the code below might meet the conservative standards of Alexandria.
What do you think?
(defun bisect (test n &optional (base 0)) "Find, using bisection, the largest positive integer below N and above, or equal to BASE, which satisfies TEST of one argument. Assumes monotonous truth value of TEST."
I can't claim I have thought this thru, but I the interface seems a bit strange to me. I would have thought that something like the following would be a more natural, and maybe even a more flexible approach:
function BISECT value sequence &key start end key
Binary search for VALUE in SEQUENCE. KEY must return a monotonically increasing real value for all elements of SEQUENCE: if I > J, then (FUNCALL KEY (ELT SEQUENCE I)) > (FUNCALL KEY (ELT SEQUENCE J)). Values obtained by KEY are compared against VALUE, and the element is considered to match if all earlier elements in the sequence are smaller then VALUE, and all later elements are greater.
...that's not quite right either: it doesn't say if the return value is the element or the index (or both), it doesn't describe START and END, and the later/earlier language is a bit vague.
But speaking in the abstract, I think BISECT / BINARY-SEARCH is within the scope of Alexandria. Sorry for the slow reply.
Cheers,
-- Nikodemus
From: "Nikodemus Siivola" nikodemus@random-state.net
I can't claim I have thought this thru, but I the interface seems a bit strange to me. I would have thought that something like the following would be a more natural, and maybe even a more flexible approach:
function BISECT value sequence &key start end key
I'll try to defend the more abstract (?) approach I took, and I'll address the differences you introduced piecemeal, the sequences-instead-of-numbers first, and immediate-value-instead-of -discrete/analytic- function specification next.
The specification of BISECT, as you have presented, confines its usage to sequences. I believe that it constitutes a serious reduction of generality[1].
To illustrate this, BISECT-SEQUENCE (if you'll allow me to re-nickname your version) might be easily implemented on top of BISECT, albeit lacking the prospect of optimisation for the list case, whereas the opposite is tentatively harder/less efficient to pull off, as you'd have to evaluate the discrete function for every value of the argument, to produce the sequence to operate on. Moreover, you'd have to provide a way to map the value back to the argument of the discrete function.
Moving on to the immediate function specification (this might be a non-traditional way to word this, but I hope it's sufficiently clear what I mean). Here I perceive another reduction in generality, even more severe, as there might be discrete functions with no easy or even reliable way to construct a mapping to a sequence of real numbers, whereas constructing a discrete function flipping its truth value at a given real number is indeed trivial.
But I /think/, I can see the usage concern you addressed with your proposed change to the BISECT's contract. Perhaps we can supply both the more general BISECT and BISECT-SEQUENCE[2] together?
I guess I'll hold my updated version of the docstring contract for BISECT, until I hear more of what you think about the issue.
regards, Samium Gromoff
1. Still I can see potential benefits here (there is an obvious optimisation in the case of lists, for example).
2. BISECT-SEQUENCE as you have provided it, and perhaps BISECT-SEQUENCE-IF too, a compromise version between BISECT and BISECT-SEQUENCE, which is to search the sequence for predicate satisfaction, rather than specific real value.
alexandria-devel@common-lisp.net
-
Nikodemus Siivola -
Samium Gromoff