[PD] match the closest number

[Frank Barknecht]

Hallo,
danja hat gesagt: // danja wrote:

> i have a [list] of numbers and i'd like to search through it for the
> value closest to the search subject. so to say, if i have '22 31 47 86'
> in my list and i match it with '45' the answer would be '47' (closest in
> the list). this rather useful function (fuzzy integer search?) must have
> been written by someone already, it's just that i can't find it :)
> i wouldn't ask if i could patch it myself, but i know how it might work:
> all integers from the list are compared to the reference (subject)
> number, and the integer in subtraction closest to '0' would be the
> hit... you know what i mean?

Yes, that's the general idea: You calculate the distance using: 

 [- 45]
 |
 [abs]

and then you look for the smallest distance and use the number(s) of
the original list that have this distance as your result. 

Attached patch shows several ways to achieve this result. One is using
a bunch of abstractions from the [list]-abs collection. First it
calculates a distance list made like: x for x in abs(x-45). 

For the list: "22 31 47 86" and the comparison value "45" this would
be: "23 14 2 41".

Then we find the minimum using [list-minmax] which is 2. Then, using
[list-find] we look up the position of 2 in the distance list: It's at
index 2 (counting is starting with 0!). 

Then finally we retrieve the number at that position in the original
list using [list-idx]. 

This will also find numbers with the same distance.

Another approach is illustrated on the right side of the patch. It
doesn't involve any abstractions, but won't find more than one number.

The basic idea is to calculate the distance for every list element,
and if that distance is smaller than the distance of the previous
element, store the current item in a [f] element at the bottom. 

The first item is treated in a special way in that its distance is
compared to itself, so that it will always be stored in the lower [f].

Finally when the whole list was consumed, the final result in the
lower [f] is bang'd as result. Of course this will only give one result.

And finally, hidden in the subpatch [pd with-list-reduce] is a version
that has a functional programming flavour and uses [list-reduce].

[list-reduce] calls whatever functionality  you patch and crossconnect
to the right oulets on pairs of list items: First on the first and
second element, then on the result of that computation and the third
element, then on the next result and the fourth element and so on, and
finally returns the last result to its left outlet.

In attached patch, the distances of both items in a pair are compared
to each other. The number with the smaller distance is sent back to
[list-reduce] where it is compared to the next element. 

So at first you get a comparison of the distances of 22 and 31 to 45.
31 obviously is closest so next its distance is compared to the
distance of the next element, 47. Now 47 is closer, so 47 is sent back
to list-reduce which pairs it up with 86. 47 still is closer, and as
the list is fully parsed now, 47 is sent to the outlet.

This solution also only returns one result, but personally I think
it's the most elegant of the three and looks really neat, if you put
the comparision into a subpatch: 

 [list-reduce]x[pd compare-two]

And I'd always prefer a good looking patch. ;)

Ciao
-- 
 Frank Barknecht                 _ ______footils.org_ __goto10.org__
-------------- next part --------------
A non-text attachment was scrubbed...
Name: closest.pd
Type: application/puredata
Size: 4822 bytes
Desc: not available
URL: <http://lists.puredata.info/pipermail/pd-list/attachments/20070618/015def0a/attachment.bin>