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

Re: matching lists
type: item
description: "J.D. Smith" <jdsmith@astro.cornell.edu> writes: > > Mark Fardal wrote: >> >> Hi, >> >> I have been looking at properties of particles in a simulation, and >> sometimes need to match up the particles in two different subsets. I >> typically have (quantity A, index #) for one set of particles, and >> (quantity B, index #) for another set, and want to compare quantities >> A and B for the particles that are in both sets. >> >> As of late last night I could not think of a good way to do this; >> WHERE inside a for-loop would be very slow. Maybe I'm missing >> something easy, but in any case here's a solution inspired by the >> recently submitted SETINTERSECTION function. Hope somebody finds >> it useful. >> > > The standard where_array, as posted a few years back, and modified > slightly for the case of the null intersection, is attached. It > will work with floating point and other data types also. It works > by inflating the vectors input to 2-d and testing for equality in > one go. It will also handle the case of repeated entries. > ... I also submit CMSET_OP, a function I recently posted on my web page. (Actually, I'm not sure if Mark is referring to that by SETINTERSECTION). Advantages are: * works on any numeric or string data type * works in order (n1+n2)*log(n1+n2) time or better, rather than n1*n2 * uses the histogram technique for short integer lists as JD suggests * also does "union" and "exclusive or" * also does A and NOT B or vice versa Disadvantages: * it removes duplicates, treating the two lists strictly as sets. * returns values, not indices Craig http://cow.physics.wisc.edu/~craigm/idl/idl.html -- ------------------------------------------------------------ -------------- Craig B. Markwardt, Ph.D. EMAIL: craigmnet@cow.physics.wisc.edu Astrophysics, IDL, Finance, Derivatives | Remove "net" for better response ------------------------------------------------------------ --------------
creator: Craig Markwardt
date: 2000-03-10T08:00:00-00:00

Re: matching lists
type: item
description: ; RESTRICTIONS: ; if the indices are not unique some matching elements may be skipped... ; or is it worse than that? Maybe worse than that... Isn't a significant restriction that the lists must be numeric? Or does it actually work for alpha-numeric lists? Mark Fardal wrote: > > Hi, > > I have been looking at properties of particles in a simulation, and > sometimes need to match up the particles in two different subsets. I > typically have (quantity A, index #) for one set of particles, and > (quantity B, index #) for another set, and want to compare quantities > A and B for the particles that are in both sets. > > As of late last night I could not think of a good way to do this; > WHERE inside a for-loop would be very slow. Maybe I'm missing > something easy, but in any case here's a solution inspired by the > recently submitted SETINTERSECTION function. Hope somebody finds > it useful. > > Mark Fardal > UMass > > ;+ > ; NAME: > ; LISTMATCH > ; > ; PURPOSE: > ; find the indices where a matches b > ; works only for SETS OF UNIQUE INTEGERS, e.g., array indices > ; > ; for example: suppose you have a list of people with their ages and > ; social security numbers (AGE, AGE_SS), and a partially overlapping > ; list of people with their incomes and s.s. numbers (INCOME, > ; INCOME_SS). And you want to correlate ages with incomes in the > ; overlapping subset. Call > ; LISTMATCH, AGE_SS, INCOME_SS, AGE_IND, INCOME_IND > ; then AGE[AGE_IND] and INCOME[INCOME_IND] will be the desired > ; pair of variables. > ; > ; AUTHOR: > ; Mark Fardal > ; UMass (fardal@weka.astro.umass.edu) > ; > ; CALLING SEQUENCE: > ; LISTMATCH, a, b, a_ind, b_ind > ; > ; INPUTS: > ; a and b are sets of unique integers (no duplicate elements) > ; > ; OUTPUTS: > ; a_ind, b_ind are the indices indicating which elements of a and b > ; are in common > ; > ; RESTRICTIONS: > ; if the indices are not unique some matching elements may be skipped... > ; or is it worse than that? > ; EXAMPLE: > ; a = [2,4,6,8] > …
creator: Andy Loughe
date: 2000-03-10T08:00:00-00:00

Re: matching lists
type: item
description: Mark Fardal wrote: > > Hi, > > I have been looking at properties of particles in a simulation, and > sometimes need to match up the particles in two different subsets. I > typically have (quantity A, index #) for one set of particles, and > (quantity B, index #) for another set, and want to compare quantities > A and B for the particles that are in both sets. > > As of late last night I could not think of a good way to do this; > WHERE inside a for-loop would be very slow. Maybe I'm missing > something easy, but in any case here's a solution inspired by the > recently submitted SETINTERSECTION function. Hope somebody finds > it useful. > The standard where_array, as posted a few years back, and modified slightly for the case of the null intersection, is attached. It will work with floating point and other data types also. It works by inflating the vectors input to 2-d and testing for equality in one go. It will also handle the case of repeated entries. For sparse integer data sets, such as the SSN example you give in the routine documentation, it will be vastly superior. Let's take your SSN for an example. If collected from random geographic locations and age brackets, the range of integers might span a billion. Suppose you had 1000 entries in your survey. The histograms will each return a vector of length 1-billion (almost all zeroes), whereas two 1-million entry arrays would be made using where_array... the difference between uncomfortable and easy. In the other extreme, in which the data are well grouped (not sparse) and you have a lot of them (e.g. a set of particles labelled from 1-1e6), you will be better off with histogram... and now that I think about it, why can't we formulate it like this: n_hist=maxab-minab n_arr= n_elements(a) * n_elements(b) if n_hist lt n_arr then ; use set_intersection method else ; use array inflation method endif to get the best of both worlds. Hmm... maybe if I'm bored someday. By the way, you could fix your method to deal with rep…
creator: John-David T. Smith
date: 2000-03-10T08:00:00-00:00

Re: matching lists
type: item
description: Craig Markwardt wrote: > > "J.D. Smith" <jdsmith@astro.cornell.edu> writes: >> >> Mark Fardal wrote: >>> >>> Hi, >>> >>> I have been looking at properties of particles in a simulation, and >>> sometimes need to match up the particles in two different subsets. I >>> typically have (quantity A, index #) for one set of particles, and >>> (quantity B, index #) for another set, and want to compare quantities >>> A and B for the particles that are in both sets. >>> >>> As of late last night I could not think of a good way to do this; >>> WHERE inside a for-loop would be very slow. Maybe I'm missing >>> something easy, but in any case here's a solution inspired by the >>> recently submitted SETINTERSECTION function. Hope somebody finds >>> it useful. >>> >> >> The standard where_array, as posted a few years back, and modified >> slightly for the case of the null intersection, is attached. It >> will work with floating point and other data types also. It works >> by inflating the vectors input to 2-d and testing for equality in >> one go. It will also handle the case of repeated entries. >> ... > > I also submit CMSET_OP, a function I recently posted on my web page. > (Actually, I'm not sure if Mark is referring to that by > SETINTERSECTION). > > Advantages are: > * works on any numeric or string data type > * works in order (n1+n2)*log(n1+n2) time or better, rather than n1*n2 > * uses the histogram technique for short integer lists as JD suggests > * also does "union" and "exclusive or" > * also does A and NOT B or vice versa > > Disadvantages: > * it removes duplicates, treating the two lists strictly as sets. > * returns values, not indices > The flag+shift method which I came up with a few years back (search for "Efficient comparison of arrays", circa 1997) was surrounded by a great deal of discussion about the best type of algorithm for this method. I'll quote from one of my postings at that time: ============================================================ ===========…
creator: John-David T. Smith
date: 2000-03-12T08:00:00-00:00

Re: matching lists
type: item
description: Mark Fardal wrote: > > Hi, > > Somehow I knew that if I mentioned HISTOGRAM, that would stir up some > real IDL programmers. :-> > > J.D.'s sort method seems like the winner. The modest speed advantage > of the histogram method in certain cases is not important. If you are > in a situation where just matching up the elements is the limitation, > you are probably going to be in trouble doing any analysis with them > (let alone reading them in). > > The problem of repeated elements, which is the only advantage of > WHERE_ARRAY, is not of any concern, at least to me. The point of > the key variables a and b is that they are supposed to be unique > identifiers. I would just like the routine not to break completely > in case the same element was copied into the arrays twice. The > sort method does fine in that respect (finds the last of the > duplicate elements in a and the first in b). By the way, I found an implementation I had mentioned a while back on the news group but had forgotten about from the nasa lib called "match" which does pretty much the same thing. It's probably less efficient, since it uses an auxiliary list of indices in addition to the flag vector, instead of just using the sort() results directly, and performs a few more "where" tests as a result. But a similar idea, written first in 1986! Match() is also more immune to changes in sort() than my routine, as a result of carrying around these additional index arrays. Take a look. JD -- J.D. Smith |*| WORK: (607) 255-5842 Cornell University Dept. of Astronomy |*| (607) 255-6263 304 Space Sciences Bldg. |*| FAX: (607) 255-5875 Ithaca, NY 14853 |*|
creator: John-David T. Smith
date: 2000-03-13T08:00:00-00:00

Re: matching lists
type: item
description: Hi, Somehow I knew that if I mentioned HISTOGRAM, that would stir up some real IDL programmers. :-> J.D.'s sort method seems like the winner. The modest speed advantage of the histogram method in certain cases is not important. If you are in a situation where just matching up the elements is the limitation, you are probably going to be in trouble doing any analysis with them (let alone reading them in). The problem of repeated elements, which is the only advantage of WHERE_ARRAY, is not of any concern, at least to me. The point of the key variables a and b is that they are supposed to be unique identifiers. I would just like the routine not to break completely in case the same element was copied into the arrays twice. The sort method does fine in that respect (finds the last of the duplicate elements in a and the first in b). The only flaw with the sort method is that sooner or later RSI is going to break its own SORT function, just like it does with all of its other code... > The standard where_array, as posted a few years back, and modified slightly for > the case of the null intersection, is attached. It will work with floating > point and other data types also. It works by inflating the vectors input to 2-d > and testing for equality in one go. It will also handle the case of repeated entries. Hope WHERE_ARRAY does not become "standard", since it's clearly inferior to the sort method. For completeness, using the sort method inside the calling sequence I originally posted would look like: pro listmatch, a, b, a_ind, b_ind flag=[replicate(0b,n_elements(a)),replicate(1b,n_elements(b) )] s=[a,b] srt=sort(s) s=s[srt] & flag=flag[srt] wh=where(s eq shift(s,-1) and flag ne shift(flag, -1),cnt) if cnt ne 0 then begin a_ind = srt[wh] b_ind = srt[wh+1] - n_elements(a) endif else begin a_ind = -1 b_ind = -1 return endelse end Mark Fardal UMass
creator: Mark Fardal
date: 2000-03-13T08:00:00-00:00

Re: matching lists
type: item
description: "J.D. Smith" <jdsmith@astro.cornell.edu> writes: > ... > > The point of which is that cmset_op, while a very complete and > feature-packed collection of the various *value-based* set > algorithms proposed over the years, does not solve the *index-based* > set intersection operation originally requested. This is a harder > problem, also solveable for non-sparse sets with histogram and > reverse indices, or with the full n-squared array comparison. > > ... A truly excellent analysis. Thanks. Craig -- ------------------------------------------------------------ -------------- Craig B. Markwardt, Ph.D. EMAIL: craigmnet@cow.physics.wisc.edu Astrophysics, IDL, Finance, Derivatives | Remove "net" for better response ------------------------------------------------------------ --------------
creator: Craig Markwardt
date: 2000-03-13T08:00:00-00:00