comp.lang.idl-pvwave archive - RDF feed
type: channel
description: Messages from Usenet group comp.lang.idl-pvwave, compiled by Paulo Penteado
items: Search routines
items: Re: Search routines
items: Re: search routine

Search routines
type: item
description: IDL has a pretty good SORT routine, but no SEARCH routine that I have been able to find (that is, a procedure to find the index of the closest/first match in an ordered list). Once again, this can be done with loops, but such an implementation would almost certainly be much slower than a built-in function. Since searching and sorting are such basic operations, does anyone know why there is no SEARCH in IDL? Ken Bowman -- Dr. Kenneth P. Bowman, Professor 409-862-4060 Department of Meteorology 409-862-4466 fax Texas A&M University bowmanATcsrp.tamu.edu College Station, TX 77843-3150 Replace AT with @
creator: bowman
date: 1998-09-18T07:00:00-00:00

Re: Search routines
type: item
description: Kenneth P. Bowman wrote: > >> Kenneth P. Bowman wrote: >>> IDL has a pretty good SORT routine, but no SEARCH routine [...] Well, how about the one attached? I tested it with a 10000 element array, and it is in fact about a factor of ten faster than MIN or WHERE. Enjoy, Martin. ------------------------------------------------------------ ------- Dr. Martin Schultz Department for Earth&Planetary Sciences, Harvard University 109 Pierce Hall, 29 Oxford St., Cambridge, MA-02138, USA phone: (617)-496-8318 fax : (617)-495-4551 e-mail: mgs@io.harvard.edu Internet-homepage: http://www-as.harvard.edu/people/staff/mgs/ ------------------------------------------------------------ ------- ;----------------------------------------------------------- -- ;+ ; NAME: ; SEARCH (function) ; ; PURPOSE: ; Perform a binary search for the data point closest ; to a given value. Data must be sorted. ; ; CATEGORY: ; Math ; ; CALLING SEQUENCE: ; index = SEARCH( DATA, VALUE ) ; ; INPUTS: ; DATA -> a sorted data vector ; ; VALUE -> the value to look for ; ; KEYWORD PARAMETERS: ; none. ; ; OUTPUTS: ; The function returns the index of the nearest data ; point. ; ; SUBROUTINES: ; ; REQUIREMENTS: ; ; NOTES: ; This routine is much faster than WHERE or MIN for ; large arrays. It was written in response to a newsgroup ; request by K.P. Bowman. ; ; EXAMPLE: ; test = findgen(10000) ; print,search(test,532.3) ; ; prints 532 ; ; MODIFICATION HISTORY: ; mgs, 21 Sep 1998: VERSION 1.00 ; ;- ; Copyright (C) 1998, Martin Schultz, Harvard University ; This software is provided as is without any warranty ; whatsoever. It may be freely used, copied or distributed ; for non-commercial purposes. This copyright notice must be ; kept with any copy of this software. If this software shall ; be used commercially or sold as part of a larger package, ; please contact the author to arrange payment. ; Bugs and comments should be directed to mgs@io.harvard.edu ; with subject "IDL routine search" ;----------------------------…
creator: Martin Schultz
date: 1998-09-21T07:00:00-00:00

Re: Search routines
type: item
description: Kenneth P. Bowman wrote: > In article <3602D89B.15BF8C2D@ssec.wisc.edu>, Liam Gumley > <Liam.Gumley@ssec.wisc.edu> wrote: > >> Kenneth P. Bowman wrote: >>> IDL has a pretty good SORT routine, but no SEARCH routine that I have been >>> able to find (that is, a procedure to find the index of the closest/first >>> match in an ordered list). Once again, this can be done with loops, but >>> such an implementation would almost certainly be much slower than a >>> built-in function. Since searching and sorting are such basic operations, >>> does anyone know why there is no SEARCH in IDL? >> >> How about the MIN function, e.g. >> >> array = findgen(100) >> value = 37.2 >> result = min( abs( value - array ), location ) >> help, location > > Again, I'm sure this is an order-N operation, as MIN has to check every > element, just like WHERE. It has no knowledge that the list is ordered. > > Ken > Hi Ken, look at this routine. The name should mean find_middling_indices. It was written in the past where we have not the possibilty to use long names. The help part could be added if you are interested. In addition to a normal search this routine is able to use a window which is usefull for some algorithm we have written. We are thinking that's this routine is very fast, but any ideas to get it faster are welcome. Reimar -- R.Bauer Institut fuer Stratosphaerische Chemie (ICG-1) Forschungszentrum Juelich email: R.Bauer@fz-juelich.de ; ; Copyright (c) 1996, Forschungszentrum Juelich GmbH ICG-1 ; All rights reserved. ; Unauthorized reproduction prohibited. ; This software may be used, copied, or redistributed as long as it is not ; sold and this copyright notice is reproduced on each copy made. This ; routine is provided as is without any express or implied warranties ; whatsoever. ;+ ; NAME: ; fi_mi_in ; ; PURPOSE: ; The result of this function is a two dimensional indexfield. ; It is used to find the indices which overlaps in client time depending on master time and time_window ; The f…
creator: R. Bauer
date: 1998-09-26T07:00:00-00:00

Re: search routine
type: item
description: Laurens wrote: > Hi folks, > > From Martin Schultz (posted in 1999) I found the following array-search > algorithm which seems to do a fine job. > Except that i'm not able to catch the first element in the array. > > Example: > > Array = [0,80,100,120,180,300] > result = search, Array, 4.53 > > It should return index 0, if I understand it correctly, but it returns 1 > instead. Now I don't quite follow the logic of the function, so maybe > someone for which it's easy to see can help me in the right direction? You could use the built-in function value_locate instead: result=value_locate(array,4.53) which returns 0. Ciao, Paolo
creator: Paolo Grigis
date: 2007-06-01T13:11:38-00:00

Re: search routine
type: item
description: On Jun 1, 9:11 am, Paolo Grigis <pgri...@astro.phys.ethz.ch> wrote: > Laurens wrote: >> Hi folks, > >> From Martin Schultz (posted in 1999) I found the following array-search >> algorithm which seems to do a fine job. >> Except that i'm not able to catch the first element in the array. > >> Example: > >> Array = [0,80,100,120,180,300] >> result = search, Array, 4.53 > >> It should return index 0, if I understand it correctly, but it returns 1 >> instead. Now I don't quite follow the logic of the function, so maybe >> someone for which it's easy to see can help me in the right direction? > > You could use the built-in function value_locate instead: > > result=value_locate(array,4.53) > > which returns 0. > > Ciao, > Paolo If you wanted to program it up, you'd be better off with array operations anyway, something like this: function search_array, arr, val w = where( arr - val le 0 AND shift(arr,-1) - val ge 0 ) return,w
creator: cmancone
date: 2007-06-01T13:32:58-00:00

Re: search routine
type: item
description: On Jun 1, 9:11 am, Paolo Grigis <pgri...@astro.phys.ethz.ch> wrote: > Laurens wrote: >> Hi folks, > >> From Martin Schultz (posted in 1999) I found the following array-search >> algorithm which seems to do a fine job. >> Except that i'm not able to catch the first element in the array. > >> Example: > >> Array = [0,80,100,120,180,300] >> result = search, Array, 4.53 > >> It should return index 0, if I understand it correctly, but it returns 1 >> instead. Now I don't quite follow the logic of the function, so maybe >> someone for which it's easy to see can help me in the right direction? > > You could use the built-in function value_locate instead: > > result=value_locate(array,4.53) > > which returns 0. > > Ciao, > Paolo Actually, that's not so good. It assumes your array is always increasing, and positive. If you used positive values, you would find that my above example would report the index AFTER where the value appears...
creator: cmancone
date: 2007-06-01T13:34:47-00:00

Re: search routine
type: item
description: Paolo Grigis wrote: > > > Laurens wrote: >> Hi folks, >> >> From Martin Schultz (posted in 1999) I found the following >> array-search algorithm which seems to do a fine job. >> Except that i'm not able to catch the first element in the array. >> >> Example: >> >> Array = [0,80,100,120,180,300] >> result = search, Array, 4.53 >> >> It should return index 0, if I understand it correctly, but it returns >> 1 instead. Now I don't quite follow the logic of the function, so >> maybe someone for which it's easy to see can help me in the right >> direction? > > You could use the built-in function value_locate instead: > > result=value_locate(array,4.53) > > which returns 0. > > Ciao, > Paolo > hehe, thanks a lot~! That's the one I was looking for...
creator: Laurens
date: 2007-06-01T13:38:26-00:00

Re: search routine
type: item
description: Paolo Grigis wrote: > > > Laurens wrote: >> Hi folks, >> >> From Martin Schultz (posted in 1999) I found the following >> array-search algorithm which seems to do a fine job. >> Except that i'm not able to catch the first element in the array. >> >> Example: >> >> Array = [0,80,100,120,180,300] >> result = search, Array, 4.53 >> >> It should return index 0, if I understand it correctly, but it returns >> 1 instead. Now I don't quite follow the logic of the function, so >> maybe someone for which it's easy to see can help me in the right >> direction? > > You could use the built-in function value_locate instead: > > result=value_locate(array,4.53) > > which returns 0. > > Ciao, > Paolo > though i'm noticing that it takes its ground number to be returned. If my array has [0,10,20,30] and i'm searching for 18, it will return 10. Now its just that would want to get 20 instead of 10 :) regards, Laurens
creator: Laurens
date: 2007-06-01T13:42:39-00:00

Re: search routine
type: item
description: cmancone@ufl.edu wrote: > On Jun 1, 9:11 am, Paolo Grigis <pgri...@astro.phys.ethz.ch> wrote: >> Laurens wrote: >>> Hi folks, >>> From Martin Schultz (posted in 1999) I found the following array-search >>> algorithm which seems to do a fine job. >>> Except that i'm not able to catch the first element in the array. >>> Example: >>> Array = [0,80,100,120,180,300] >>> result = search, Array, 4.53 >>> It should return index 0, if I understand it correctly, but it returns 1 >>> instead. Now I don't quite follow the logic of the function, so maybe >>> someone for which it's easy to see can help me in the right direction? >> You could use the built-in function value_locate instead: >> >> result=value_locate(array,4.53) >> >> which returns 0. >> >> Ciao, >> Paolo > > > If you wanted to program it up, you'd be better off with array > operations anyway, something like this: > > function search_array, arr, val > w = where( arr - val le 0 AND shift(arr,-1) - val ge 0 ) > return,w "where" is much slower, so I would not recommend it. Ciao, Paolo >
creator: Paolo Grigis
date: 2007-06-01T14:20:04-00:00

Re: search routine
type: item
description: cmancone@ufl.edu wrote: > On Jun 1, 9:11 am, Paolo Grigis <pgri...@astro.phys.ethz.ch> wrote: >> Laurens wrote: >>> Hi folks, >>> From Martin Schultz (posted in 1999) I found the following array-search >>> algorithm which seems to do a fine job. >>> Except that i'm not able to catch the first element in the array. >>> Example: >>> Array = [0,80,100,120,180,300] >>> result = search, Array, 4.53 >>> It should return index 0, if I understand it correctly, but it returns 1 >>> instead. Now I don't quite follow the logic of the function, so maybe >>> someone for which it's easy to see can help me in the right direction? >> You could use the built-in function value_locate instead: >> >> result=value_locate(array,4.53) >> >> which returns 0. >> >> Ciao, >> Paolo > > Actually, that's not so good. It assumes your array is always > increasing, and positive. Yes, the array has to be sorted. No, it doesn't have to be positive. Ciao, Paolo If you used positive values, you would find > that my above example would report the index AFTER where the value > appears... >
creator: Paolo Grigis
date: 2007-06-01T14:23:06-00:00

Re: search routine
type: item
description: Laurens wrote: > Paolo Grigis wrote: >> >> >> Laurens wrote: >>> Hi folks, >>> >>> From Martin Schultz (posted in 1999) I found the following >>> array-search algorithm which seems to do a fine job. >>> Except that i'm not able to catch the first element in the array. >>> >>> Example: >>> >>> Array = [0,80,100,120,180,300] >>> result = search, Array, 4.53 >>> >>> It should return index 0, if I understand it correctly, but it >>> returns 1 instead. Now I don't quite follow the logic of the >>> function, so maybe someone for which it's easy to see can help me in >>> the right direction? >> >> You could use the built-in function value_locate instead: >> >> result=value_locate(array,4.53) >> >> which returns 0. >> >> Ciao, >> Paolo >> > though i'm noticing that it takes its ground number to be returned. > If my array has [0,10,20,30] and i'm searching for 18, it will return > 10. Now its just that would want to get 20 instead of 10 :) well, in that case, just increase the index of the returned value by one (though you'd better check that it wasn't the *last* element...). Ciao, Paolo > > regards, Laurens
creator: Paolo Grigis
date: 2007-06-01T14:27:24-00:00