newlispfanclub.alh.net

Posted: **Mon Jun 29, 2009 4:17 pm**

Here's a little problem I'm trying to solve. Given a value, and a list/association list, find the entry that provides the nearest match for the first element. For example:

Code: Select all

(set 'target 200906281845)

(set 'data '(
(200906282050 "29003KT" "CAVOK" "19/13" "Q1015=") 
(200906281950 "05004KT" "CAVOK" "19/13" "Q1014=") 
(200906281750 "12010KT" "9999" "FEW020" "20/13" "Q1014=") ; <- this is the one to be found
(200906281700 "12010KT" "9999" nil "20/14" "Q1015=") 
(200906280000 "12010KT" "9999" "FEW020" "20/14" nil)
; ...
))

The elegant solution is currently eluding me... Can I do it with ref/ref-all or do I need a state-keeping function?

Posted: **Mon Jun 29, 2009 5:20 pm**

This would return a list of indices where the first number differs less then maxdiff from target:

Code: Select all

(set 'target '205)
(set 'maxdiff 30)

(set 'data '(
(101 a b c)
(200 c d e)
(230 x y z)
(250 f g h)))


(find-all 205 data $it (fn (x y) (< (abs (- x (y 0))) maxdiff)))

=> ((200 c d e) (230 x y z))


(find-all 205 data (rest $it) (fn (x y) (< (abs (- x (y 0))) maxdiff)))

=> ((c d e) (x y z))

In the comparison function x is 205 and y is each of the sublists.

Posted: **Mon Jun 29, 2009 9:10 pm**

Additionally, Lutz's solution with maxdiff defined automatically:

Code: Select all

(set 'target '205)
(set 'maxdiff 30)

(set 'data '((101 a b c)
             (200 c d e)
             (230 x y z)
             (250 f g h)))

(println ((lambda(t)(ref (apply min t) t)) 
          (map (lambda(y)(abs (- target y)))
               (map first data))))

I think that whole situation suggests defining functions as refmin and refclose :

Code: Select all

(set 'target '205)
(set 'maxdiff 30)

(set 'data '((101 a b c)
             (200 c d e)
             (230 x y z)
             (250 f g h)))

(set 'refmin (lambda(t)(ref (apply min t) t)))

(set 'refclose 
     (lambda(target L) 
        (refmin (map (lambda(y)(abs (- target y)))
                      L))))
                         
(println (refclose target (map first data)))

Posted: **Mon Jun 29, 2009 9:30 pm**

cormullion wrote:The elegant solution is currently eluding me... Can I do it with ref/ref-all or do I need a state-keeping function?

Is using apply for state keeping elegant enough?

Code: Select all

(define (df datum) (abs (- target (datum 0))))
(define (choose x y) (if (< (df x) (df y)) x y))
(println (apply choose data 2))

Posted: **Mon Jun 29, 2009 10:00 pm**

Ah, these are all looking great. When in doubt, ask the experts! My attempt was functional (hah) but basic and inelegant.

Code: Select all

(context 'nearest-record)
(set 'error-margin 1000000000 'best nil)

(define (nearest-record:nearest-record lst target)
    (when (< (abs (sub target (first lst))) error-margin)
        (set 'error-margin (abs (sub target (first lst))))
        (set 'best lst)))

(context MAIN)

(dolist (record data) (nearest-record record target))

and the best score is in the context.

Thanks!

Posted: **Tue Jun 30, 2009 4:40 am**

err.. if you stop keeping it all as lists, but create a hash with the first member as its key and the rest as a list it refers to, you could use the fact that red-black trees used for hashes in newlisp are implicitly ordered.

Then iterating over them will give you a numerically growing sequence - and so you won't need to go through all your data. You will just compare until the elements become bigger than the given value (and/or compare it to the given value plus or minus the "maxdeviation"), then stop, as you got your solution.

This should make this snippet faster.

Posted: **Tue Jun 30, 2009 5:37 pm**

It is difficult to evaluate the elegance of imaginary code ... :)

But seriously, yes, that's a very good point. In fact I could even do a binary search, to narrow down the area of the data file even quicker. (Although I'm not worried about speed, much, in this application.)

Thanks!

Posted: **Mon Jul 06, 2009 3:42 pm**

Cyril wrote:Is using apply for state keeping elegant enough?

Yup. Sure is. Your code showed the general power of the folding operation. Folding doesn't necessarily have to accumulate, as the canonical examples of it, like sums, seem to indicate. Good job, Cyril!

Posted: **Mon Jul 06, 2009 3:58 pm**

I ended up using Cyril's solution (refactored slightly) because it was the simplest and the coolest.

I'm going to have to think about why it's called 'folding' - my mental picture of apply-reduce involves walking along the seashore picking up pebbles, which shows how far away from being a real programmer I am... :)

Posted: **Mon Jul 06, 2009 3:59 pm**

Hi cormullion,

Here is a suggested interface to Cyril's code. (But you will know best what you need, of course.)

Code: Select all

(define (find-nearest db tgt)
  (let ((target tgt))
    (apply choose db 2)))

In action:

Code: Select all

> (find-nearest data 205)
(200 c d e)
> (find-nearest data 228)
(230 x y z)
> (find-nearest data 500)
(250 f g h)
>

It should not be lost on the reader/programmer that this interface takes advantage of dynamic binding. How? Notice that function find-nearest binds the symbol target to the value of its parameter tgt (in the let expression). The function df, when it gets called down the stack, will "see" this value in target.

Posted: **Mon Jul 06, 2009 9:13 pm**

Thanks Rick! Good to see you round here occasionally...

newlispfanclub.alh.net

Problem in search of an elegant solution

Problem in search of an elegant solution

Re: Problem in search of an elegant solution

implicit ordering of newlisp hashes

Re: Problem in search of an elegant solution