hello there, 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?
any advice is very much appreciated!
p.s. apologies for my ignorance, i'm just starting here...
-- danja http://k0a1a.net
Here's a possibility. Not very elegant, but it works. Replace the list and the numberboxes with whatever input and output you need and it ought to work, if the differences are smaller than 100000. -Chuckk
On 6/18/07, danja binary.koala@gmail.com wrote:
hello there, 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?
any advice is very much appreciated!
p.s. apologies for my ignorance, i'm just starting here...
-- danja http://k0a1a.net
PD-list@iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Hey ! Nice. That's what I was looking for to improve my closest-note abstraction. See http://wiki.dataflow.ws/PdMtlAbstractions/Contents#head-musical
It is currently only "flooring" the values, I think. Closest is what it really means to be. (with floats, not just integers.
Cheers !
a
2007/6/18, Chuckk Hubbard badmuthahubbard@gmail.com:
Here's a possibility. Not very elegant, but it works. Replace the list and the numberboxes with whatever input and output you need and it ought to work, if the differences are smaller than 100000. -Chuckk
On 6/18/07, danja binary.koala@gmail.com wrote:
hello there, 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?
any advice is very much appreciated!
p.s. apologies for my ignorance, i'm just starting here...
-- danja http://k0a1a.net
PD-list@iem.at mailing list UNSUBSCRIBE and account-management ->
http://lists.puredata.info/listinfo/pd-list
-- http://www.badmuthahubbard.com _______________________________________________ PD-list@iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
if you use [drip] from zexy, you can build a patch with [simile] from my ekext externals.
Alternatively, you could turn the problem on its head. Feed the list into [sieve] via [drip] into a [set $1 1( message, run sieve in mode 1 (nearest value), and fire the value (rather than the list) into sieve each time the list is updated. [sieve] is also part of the ekext externals.
When I get my [listmatch] object finished I'll let you know, but I'm quite busy right now!
Best, Ed
danja binary.koala@gmail.com wrote: hello there, 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?
any advice is very much appreciated!
p.s. apologies for my ignorance, i'm just starting here...
-- danja http://k0a1a.net
PD-list@iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Lone Shark "Aviation" out now on http://www.pyramidtransmissions.com http://www.myspace.com/sharktracks
Yahoo! Answers - Get better answers from someone who knows. Tryit now.
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__
On Mon, 2007-06-18 at 22:54 +0200, Frank Barknecht wrote:
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. ;)
wow, very good example of showing how powerfull list-abs are. cool work!
roman
Telefonate ohne weitere Kosten vom PC zum PC: http://messenger.yahoo.de
Wow Frank, the hidden patch is so elegant! I'm currently implementing it in my layout, it does exactly what i was looking for. As i could see it shall handle negative numbers just as fine, i hope it does! :) I will report performance soon, I have rather big lists to go through.
Thanks for the great input, Danja
Frank Barknecht wrote: ...
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. ;)
I agree this is neat write-up and demonstration Frank made!
On 18/06/2007, at 23.44, danja wrote:
I will report performance soon, I have rather big lists to go through.
If you have big lists and if matches may occur, then maybe a routine
that checks if the difference is 0 (i.e. a match) and then just
output that corresponding number (which is the same as the search
number) and exit the search right away might be desirable? In this
case uniqueness is not a problem, naturally.
-
Alexandre Quessy -
Chuckk Hubbard -
danja -
Ed Kelly -
Frank Barknecht -
Roman Haefeli -
Steffen