How to find the nearest interval of two items in a collection?
Closed this issue · 6 comments
Hello Scott,
This question is certainly more general than FSet, but I thought it would be interesting to put this concrete use case in practice.
The problem is simple: let's take for example an ordered collection of stock quotes (a stock quote is a structure consisting of a date and a value) and draw a chart from them, the date on the abscissae and the value on the ordinates. Then I would like to lookup which pair of stock quotes falling under my mouse pointer.
For this, I could simply search the collection and find the interval. I have read that a binary search is a simple and fast solution.
Is there in FSet a data structure that readily provides an answer to this problem? I was thinking about wb-trees but I'm afraid this is too low level. What do you think?
Thank you very much in advance!
Cam
Here is an attempt (I'm still interested in your expertise!).
(defun interval-search (seq value &key (key #'identity))
"Search members of SEQ for an interval containing VALUE. Return two
values being the boundary elements of the interval found, one value on
an exact match, or NIL otherwise."
(labels ((rec (low high)
(cond
((eq (- low high) 1)
(values (fset:@ seq high)
(fset:@ seq low)))
((< high low)
nil)
(t
(let* ((mid (floor (/ (+ low high) 2)))
(mid-value (funcall key (fset:@ seq mid))))
(case (fset:compare mid-value value)
(:greater (rec low (- mid 1)))
(:less (rec (+ mid 1) high))
(t (fset:@ seq mid))))))))
(unless (fset:empty? seq)
(rec 0 (- (fset:size seq) 1)))))There's an existing operation 'rank' that will do what you need. Put your
values in a map, and then call 'rank' to find the nearest key. Use
'at-rank' to extract the key/value pairs of that and the previous rank, as
appropriate.
(It annoys me that I defined 'rank' to return the higher index rather than
the lower one in the case of a miss; returning the lower one would have
been more natural. But I don't think I should risk breaking users' code by
changing it now.)
-- Scott
On Fri, Mar 21, 2014 at 2:59 AM, Camille Troillard <notifications@github.com
wrote:
Here is an attempt (I'm still interested in your expertise!).
(defun interval-search (seq value &key (key #'identity))
"Search members of SEQ for an interval containing VALUE. Return twovalues being the boundary elements of the interval found, one value onan exact match, or NIL otherwise."
(labels ((rec (low high)
(cond
((eq (- low high) 1)
(values (fset:@ seq high)
(fset:@ seq low)))
((< high low)
nil)
(t
(let* ((mid (floor (/ (+ low high) 2)))
(mid-value (funcall key (fset:@ seq mid))))
(case (fset:compare mid-value value)
(:greater (rec low (- mid 1)))
(:less (rec (+ mid 1) high))
(t (fset:@ seq mid))))))))
(unless (fset:empty? seq)
(rec 0 (- (fset:size seq) 1)))))Reply to this email directly or view it on GitHubhttps://github.com//issues/5#issuecomment-38261919
.
Thanks Scott!
I will have a look at RANK.
Just an additional comment:
RANK is internal to the FSET package, so I don't believe it is much used.
I guess you could change it in a future release, don't you think?
Ah, I never exported RANK or AT-RANK; alas, that probably means I never
tested them very much either. If you could code-review and/or test them,
that would be great.
Nonetheless, since RANK wasn't exported, as you suggest I feel free to
tweak its interface. I have done so, and exported both symbols.
-- Scott
On Fri, Mar 21, 2014 at 1:23 PM, Camille Troillard <notifications@github.com
wrote:
Just an additional comment:
RANK is internal to the FSET package, so I don't believe it is much used.
I guess you could change it in a future release, don't you think?Reply to this email directly or view it on GitHubhttps://github.com//issues/5#issuecomment-38319850
.
The updated version works fine, thank you for making this adjustment!