Problem in search of an elegant solution

For the Compleat Fan
Locked
cormullion
Posts: 2038
Joined: Tue Nov 29, 2005 8:28 pm
Location: latiitude 50N longitude 3W
Contact:

Problem in search of an elegant solution

Post by cormullion »

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?

Lutz
Posts: 5289
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California
Contact:

Post by Lutz »

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.

Kazimir Majorinc
Posts: 388
Joined: Thu May 08, 2008 1:24 am
Location: Croatia
Contact:

Post by Kazimir Majorinc »

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)))

Cyril
Posts: 183
Joined: Tue Oct 30, 2007 6:27 pm
Location: Moscow, Russia
Contact:

Re: Problem in search of an elegant solution

Post by Cyril »

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))
With newLISP you can grow your lists from the right side!

cormullion
Posts: 2038
Joined: Tue Nov 29, 2005 8:28 pm
Location: latiitude 50N longitude 3W
Contact:

Post by cormullion »

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!

unixtechie
Posts: 65
Joined: Sat Sep 06, 2008 6:30 am

implicit ordering of newlisp hashes

Post by unixtechie »

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.

cormullion
Posts: 2038
Joined: Tue Nov 29, 2005 8:28 pm
Location: latiitude 50N longitude 3W
Contact:

Post by cormullion »

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!

rickyboy
Posts: 607
Joined: Fri Apr 08, 2005 7:13 pm
Location: Front Royal, Virginia

Re: Problem in search of an elegant solution

Post by rickyboy »

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!
(λx. x x) (λx. x x)

cormullion
Posts: 2038
Joined: Tue Nov 29, 2005 8:28 pm
Location: latiitude 50N longitude 3W
Contact:

Post by cormullion »

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... :)

rickyboy
Posts: 607
Joined: Fri Apr 08, 2005 7:13 pm
Location: Front Royal, Virginia

Post by rickyboy »

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.
(λx. x x) (λx. x x)

cormullion
Posts: 2038
Joined: Tue Nov 29, 2005 8:28 pm
Location: latiitude 50N longitude 3W
Contact:

Post by cormullion »

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

Locked