Arrays Intersection : Programming Fortran
5/10/11 4:37 AM
Home Technology Sports Entertainment Lifestyle
Home Technology Programming Programming Languages Programming Fortran
Arrays Intersection
NEW TOPIC
Page 1 of 1
POST REPLY
[ 9 posts ]
Print view
Infinity77
Post subject: Arrays Intersection
Hi All,
I have received so many nice answers in this newsgr
thought I could ask one more question. I am trying
intersection of 2 one-dimensional integer arrays, w
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 ha
lists and structures for which it's easy to define an "
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.
Arjen Markus
Post subject: Re: Arrays Intersection
On 30 mei, 13:34, Infinity77 wrote:
Quote:
Hi All,
http://www.0x61.com/forum/programming-fortran-f230/arrays-intersection-t219892.html
Page 1 of 16
Arrays Intersection : Programming Fortran
5/10/11 4:37 AM
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:
http://www.0x61.com/forum/programming-fortran-f230/arrays-intersection-t219892.html
Page 2 of 16
Arrays Intersection : Programming Fortran
5/10/11 4:37 AM
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
Arjen Markus
Post subject: Re: Arrays Intersection
On 30 mei, 15:36, Gordon Sande wrote:
Quote:
On 2008-05-30 09:53:27 -0300, Arjen Markus said:
On 30 mei, 13:34, Infinity77 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
http://www.0x61.com/forum/programming-fortran-f230/arrays-intersection-t219892.html
Page 3 of 16
Arrays Intersection : Programming Fortran
5/10/11 4:37 AM
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.
http://www.0x61.com/forum/programming-fortran-f230/arrays-intersection-t219892.html
Page 4 of 16
Arrays Intersection : Programming Fortran
5/10/11 4:37 AM
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.)- Tekst uit oorspronkelijk bericht niet weergeven - Tekst uit oorspronkelijk bericht weergeven -
True, but the code is quite concise
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
Arjen Markus
Post subject: Re: Arrays Intersection
On 30 mei, 16:08, Gordon Sande wrote:
Quote:
On 2008-05-30 10:42:33 -0300, Arjen Markus said:
On 30 mei, 15:36, Gordon Sande wrote:
On 2008-05-30 09:53:27 -0300, Arjen Markus said:
On 30 mei, 13:34, Infinity77 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]
http://www.0x61.com/forum/programming-fortran-f230/arrays-intersection-t219892.html
Page 5 of 16
Arrays Intersection : Programming Fortran
5/10/11 4:37 AM
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
http://www.0x61.com/forum/programming-fortran-f230/arrays-intersection-t219892.html
Page 6 of 16
Arrays Intersection : Programming Fortran
5/10/11 4:37 AM
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 http://www.0x61.com/forum/programming-fortran-f230/arrays-intersection-t219892.html
Page 7 of 16
Arrays Intersection : Programming Fortran
5/10/11 4:37 AM
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
Arjen Markus
Post subject: Re: Arrays Intersection
On 30 mei, 16:34, Paul van Delst wrote:
Quote:
On 30 mei, 13:34, Infinity77 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]
On 2008-05-30 09:53:27 -0300, Arjen Markus said:
You might use:
pack( array1, (/ (any(array1(i) == array2), i=1,size(array1)) /) )
On 30 mei, 16:08, Gordon Sande wrote:
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
http://www.0x61.com/forum/programming-fortran-f230/arrays-intersection-t219892.html
Page 8 of 16
Arrays Intersection : Programming Fortran
5/10/11 4:37 AM
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.
FWIW, I don't think the code above is arcane at all. Yes, it uses two new f90/95
intrinsics, PACK and ALL, but once you know what they do, it seems quite clear.
Comparing to current scripting languages like python and ruby, the above code snippet is
positively crystal like in it's clarity. I doubt coding one's own versions of PACK and ALL
would be quite as readable.
We (for some suitable definition of "we") need to stop thinking that we must write code
that can be understood by both our grand-children and -parents. We've got to assume the
person reading the code in the future has some capability for analytical thought when they
come across something they don't immediately grok.
And, besides, isn't reading other's codes and trying to understand them how we all learned
Fortran?
cheers,
paulv- Tekst uit oorspronkelijk bericht niet weergeven - Tekst uit oorspronkelijk bericht weergeven -
Hear, hear
No, seriously, I think you are right - that is one of the
reasons I wrote the article about array operations and a
"functional" style of programming that appeared in the
Fortran Forum last month.
Well, the one-liner was a bit tough, but splitting it
up a bit makes it very digestible in my opinion and
easier to check than a version with explicit do-loops
(two of them!).
Regards,
Arjen
Gordon Sande
Post subject: Re: Arrays Intersection
On 2008-05-30 09:53:27 -0300, Arjen Markus said:
Quote:
http://www.0x61.com/forum/programming-fortran-f230/arrays-intersection-t219892.html
Page 9 of 16
Arrays Intersection : Programming Fortran
5/10/11 4:37 AM
On 30 mei, 13:34, Infinity77 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
http://www.0x61.com/forum/programming-fortran-f230/arrays-intersection-t219892.html
Page 10 of 16
Arrays Intersection : Programming Fortran
5/10/11 4:37 AM
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.)
glen herrmannsfeldt
Post subject: Re: Arrays Intersection
Infinity77 wrote:
Quote:
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]
Did someone else ask this recently? It sounds familiar.
http://www.0x61.com/forum/programming-fortran-f230/arrays-intersection-t219892.html
Page 11 of 16
Arrays Intersection : Programming Fortran
5/10/11 4:37 AM
Sort the two lists, if they aren't already.
You need an output array at least as long as the
shortest list. (Or it can be done in place, destroying
the input data.)
Initialize two index variables, one to the beginning
of each list, and start a loop. If the two elements
are equal, add to the output list and increment both
index variables. Otherwise increment the index variable
of the lower list element. Repeat until one is past the
end of its list.
-- glen
Gordon Sande
Post subject: Re: Arrays Intersection
On 2008-05-30 10:42:33 -0300, Arjen Markus said:
Quote:
On 30 mei, 15:36, Gordon Sande wrote:
On 2008-05-30 09:53:27 -0300, Arjen Markus said:
On 30 mei, 13:34, Infinity77 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.
http://www.0x61.com/forum/programming-fortran-f230/arrays-intersection-t219892.html
Page 12 of 16
Arrays Intersection : Programming Fortran
5/10/11 4:37 AM
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,
http://www.0x61.com/forum/programming-fortran-f230/arrays-intersection-t219892.html
Page 13 of 16
Arrays Intersection : Programming Fortran
5/10/11 4:37 AM
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.
Quote:
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
Paul van Delst
Post subject: Re: Arrays Intersection
Quote:
http://www.0x61.com/forum/programming-fortran-f230/arrays-intersection-t219892.html
Page 14 of 16
Arrays Intersection : Programming Fortran
5/10/11 4:37 AM
On 30 mei, 13:34, Infinity77 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]
On 2008-05-30 09:53:27 -0300, Arjen Markus said:
You might use:
pack( array1, (/ (any(array1(i) == array2), i=1,size(array1)) /) )
On 30 mei, 16:08, Gordon Sande wrote:
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.
FWIW, I don't think the code above is arcane at all. Yes, it uses two new f90/95
intrinsics, PACK and ALL, but once you know what they do, it seems quite clear.
Comparing to current scripting languages like python and ruby, the above code snippet is
positively crystal like in it's clarity. I doubt coding one's own versions of PACK and ALL
would be quite as readable.
We (for some suitable definition of "we") need to stop thinking that we must write code
that can be understood by both our grand-children and -parents. We've got to assume the
person reading the code in the future has some capability for analytical thought when they
come across something they don't immediately grok.
And, besides, isn't reading other's codes and trying to understand them how we all learned
Fortran?
cheers,
paulv
NEW TOPIC
POST REPLY
Page 1 of 1
[ 9 posts ]
http://www.0x61.com/forum/programming-fortran-f230/arrays-intersection-t219892.html
Page 15 of 16
Arrays Intersection : Programming Fortran
5/10/11 4:37 AM
SitemapIndex
RSS Feed
Channel list
0x61.com 2009-2010 - Internet Forums and much more!
http://www.0x61.com/forum/programming-fortran-f230/arrays-intersection-t219892.html
Page 16 of 16
