Re: Arrays Intersection

On 30 mei, 16:08, Gordon Sande <g.sa...@xxxxxxxxxxxxxxxx> wrote:
On 2008-05-30 10:42:33 -0300, Arjen Markus <arjen.mar...@xxxxxxxxxx> said:





On 30 mei, 15:36, Gordon Sande <g.sa...@xxxxxxxxxxxxxxxx> wrote:
On 2008-05-30 09:53:27 -0300, Arjen Markus <arjen.mar...@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 woul
d
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 b
e
built into Python.)- Tekst uit oorspronkelijk bericht niet weergeven -

- Tekst uit oorspronkelijk bericht weergeven -

True, but the code is quite concise :)

And allows for demonstration of arcane usage of litle used (by many)
fetures that would make an APLer proud. If the following programmers
can not follow the code it is a disservice.

If the OP had to ask it is a fair bet that arcane responses are not the
most helpful. If the OP were into serious obscure algorithms of import
to a larger code then there probably would not have been a question.
There is a well know quote on pricing of yachts that seems suited to
these situations after trivial modification.



and however you solve
the first step, you end up with an array whose length you do
not know in advance. So part of the problem will be to handle
that situation.

Regards,

Arjen- Tekst uit oorspronkelijk bericht niet weergeven -

- Tekst uit oorspronkelijk bericht weergeven -- Tekst uit oorspronkelijk bericht niet weergeven -

- Tekst uit oorspronkelijk bericht weergeven -

:)

How about:

subroutine intersect( array1, array2, result )
integer, dimension(:) :: array1, array2
integer, dimension(:), pointer :: result

logical, dimension(size(array1)) :: keep

keep = (/ ( any(array1(i) == array2, i=1,size(array1) ) /)

allocate( result(count(keep)) )

result = pack( array1, keep )

end subroutine

Still O(N**2) of course, but useful as a start, and less
convoluted.

Regards,

Arjen
.

Relevant Pages

  • Re: What is the name of this function...
    ... represents the rectangular intersection of two or more ranges.." ... The Union method would return the combination of two or more ranges. ... > =(some column array) ...
    (microsoft.public.excel.programming)
  • Re: Arrays Intersection
    ... intersection of 2 one-dimensional integer arrays, ... I couldn't find anything related to "array intersection" in Fortran. ...   values where the value is true if the element from the ... price of considerable algorithm complexity. ...
    (comp.lang.fortran)
  • Re: Arrays Intersection
    ... intersection of 2 one-dimensional integer arrays, ... I couldn't find anything related to "array intersection" in Fortran. ... Assumptions matter as unordered vrs ordered lists change things. ... After that consult a decent algorithm text for set ...
    (comp.lang.fortran)
  • Re: =INDEX(C3:N22,MATCH(G26,B3:B22),MATCH(H26,C2:N2))
    ... I think of any array as ... remove caps from email ... INDEX can be used to find the value of an intersection ... So the INDEX function returns the value at the intersection of the eighth ...
    (microsoft.public.excel.misc)
  • Re: Arrays Intersection
    ...     I have received so many nice answers in this newsgroup that I ... intersection of 2 one-dimensional integer arrays, ... I couldn't find anything related to "array intersection" in Fortran. ... you can best pass it on to a subroutine: ...
    (comp.lang.fortran)