Computing array intersections

baxy77bax has asked for the wisdom of the Perl Monks concerning the following question:

Hi,

I was wondering did anyone seen anything like this before and knows a solution to this problem ?

Problem:

Given an unsorted array of N numbers such that N[i] not equal to N[j] for j,i <= N, find an intersect between subarray N[x..y] and N[k..l] for x,y,k,l in N, when elements in N[x..y] are enlarged by a constant factor z

Example:

let say I have an array like this:

N = [1,3,5,2,6,7,55,14,23,54,56,15,44,11,9,87,10,58,19,17,26, ...]

And let say that I am given an interval I(4,8) and another one II(14,18), that is :
I(4,8) = [6,7,55,14,23]
II(14,18) = [9,87,10,58,19]
[download]
Now given that the z = 3 the intersect between I and II would be
I inters II = [9,10,58]
[download]
In the initial array N there cannot be any duplicates and the numbers span from 1..N. I know that I can do this by matching every number in I to every number in II but this would be an algorithm with a nested loop. And that is bad if my arrays are big (as they turn out to be) plus i have to repeat this for a large number of intervals (I'(a,b)) and different z in every iteration.
So my question is: what would be an alternative to this naive approach? Does anyone know how to pre-processes N to make those queries in O(1) time because this would be ideal.

cheers

baxy

Comment on Computing array intersections Select or Download Code

Replies are listed 'Best First'.
Re: Computing array intersections by BrowserUk (Patriarch) on Mar 31, 2012 at 16:39 UTC
Does anyone know how to pre-processes N to make those queries in O(1) time because this would be ideal. Not possible. At least not without infinite memory capacity. About the best you could do is create a hash or bit-vector from the larger of the two intervals suitably adjusted (+/-Z), so that you can do O(1) lookups of the values in the smaller interval, within that. If you can arrange to deal with all the Z=x in one pass and Z=y in the next and so on, then you could build a suitably adjusted array the same size as the original from which you can build your lookup hashes/vectors for each new range pair, but its unlikely to make a huge difference. The lookup removes one level of nested loop from the problem, but I see no way of reducing the others. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. The start of some sanity?	[reply]
Re: Computing array intersections by mbethke (Hermit) on Mar 31, 2012 at 16:17 UTC
Well, O(1) is a bit much to ask but O(y-x+l-k) is quite possible :) That's the classic application for a hash: First, transform your first slice to the keys of a hash while doing the incrementing: `my %h = map { $_+$inc => 1 } @a[$x .. $y];` Then your result list is the result of a `grep` on those elements that exist in the hash: `@result = grep { exists $h{$_} } @a[$k .. $l]; say join ', ', @result;` [download]	[reply] [d/l] [select]