Re: Arrays Intersection
- From: Gordon Sande <g.sande@xxxxxxxxxxxxxxxx>
- Date: Fri, 30 May 2008 13:36:58 GMT
On 2008-05-30 09:53:27 -0300, Arjen Markus <arjen.markus@xxxxxxxxxx> said:
On 30 mei, 13:34, Infinity77 <andrea.gav...@xxxxxxxxx> wrote:Hi All,
I have received so many nice answers in this newsgroup that I
thought I could ask one more question. I am trying to find the
intersection of 2 one-dimensional integer arrays, where "intersection"
means the common elements in both arrays, i.e.:
a = [1,2,3,4,5,6]
b = [5, 6, 7]
intersection(a, b) ==> [5, 6]
At the moment I am working with Python, which handles very well sets,
lists and structures for which it's easy to define an "intersection",
but as I have many many arrays to compare, this is becoming a bit slow
so I thought to use fortran. Unfortunately, my google-fu failed me as
I couldn't find anything related to "array intersection" in Fortran.
Does anyone know what I should do in order to achieve a fast solution
to this problem?
Thank you very much for your suggestions.
Andrea.
You might use:
pack( array1, (/ (any(array1(i) == array2), i=1,size(array1)) /) )
Tis may require some explanation:
- (/ ... /) is an array constructor
- in this statement it constructs an array of logical
values where the value is true if the element from the
first array coincides with one from the other
- the result is used to extract (via pack()) only those
elements for which that condition holds.
Here is your example:
program intersect
integer, dimension(6) :: array1 = (/ 1, 2, 3, 4, 5, 6 /)
integer, dimension(3) :: array2 = (/ 5, 6, 7 /)
integer :: i
write(*,*) &
pack( array1, (/ (any(array1(i) == array2), i=1,size(array1)) /) )
end program
One tricky thing though:
As you do not know in advance how large this resulting array
is, you can best pass it on to a subroutine:
subroutine copy( array, result )
integer, dimension(:) :: array
integer, dimension(:), pointer :: result
allocate( result(1:size(array)) )
result => array
end subroutine
as otherwise you have to compute the size in advance and
allocate an array of that size.
Regards,
Arjen
Set intersection is an old war horse of a problem in computer alogorithms.
Assumptions matter as unordered vrs ordered lists change things. Small vrs
large. Dynamic vrs static problem.
If it small enough then almost anything should not much matter. Above would
be usually called an n^2 algorithm. Next would be to sort and compare for an
n log n logarithm. After that consult a decent algorithm text for set
intersection. It should be a bit worse than linear but below n log n at a
price of considerable algorithm complexity. (I would guess that this may be
built into Python.)
.
- Follow-Ups:
- Re: Arrays Intersection
- From: Arjen Markus
- Re: Arrays Intersection
- References:
- Arrays Intersection
- From: Infinity77
- Re: Arrays Intersection
- From: Arjen Markus
- Arrays Intersection
- Prev by Date: warning on running image !!!!!
- Next by Date: Re: Arrays Intersection
- Previous by thread: Re: Arrays Intersection
- Next by thread: Re: Arrays Intersection
- Index(es):
Relevant Pages
|
|
