二つの整数配列があって、それぞれを集合の要素だと思って、二つの配列の集合和をとることを考える。
それは二つの配列を単純に合併したあとで quick sort の微妙な変形で、重複する要素を省きながら sort する関数に掛けることで実現できる。
実行結果
再帰そのままのへっぽこ quick sort モドキなので遅いが、まぁ百万と百万で 1~2 秒くらい?
・空集合と空集合の和
・空集合と集合の和
・集合と集合の和
・乱数で生成した大きな集合(百万要素)同士の和の重ならない率
1 2 3
1 2 3 4 5 7
86.49100 %
続行するには何かキーを押してください . . .
ソース・プログラム
Fortran 2003 / 手抜きなのでスタックサイズを大きくしないとまずい。
module m_sub
implicit none
contains
function iset_union(ia, ib)
integer, allocatable :: iset_union(:)
integer, intent(in) :: ia(:), ib(:)
iset_union = pseud_qsort([ia, ib])
end function iset_union
recursive function pseud_qsort(m) result(iret)
integer, intent(in) :: m(:)
integer, allocatable :: iret(:)
iret = [integer::]
if (size(m) < 1) return
iret = [pseud_qsort(pack(m, m < m(1))), m(1), pseud_qsort(pack(m, m > m(1)))]
end function pseud_qsort
end module m_sub
program test
use m_sub
implicit none
integer, parameter :: n = 10**6
integer, allocatable :: ia(:), ib(:)
real , allocatable :: tmp(:)
print *, iset_union([integer::], [integer::])
print *, iset_union([integer::], [3,2,1])
print *, iset_union([1,3,5,7], [4,3,2,1])
allocate(ia(n), ib(n), tmp(n))
call random_number(tmp)
ia = n * tmp
call random_number(tmp)
ib = n * tmp
print *, size(iset_union(ia, ib)) * 100.0 / n, '%'
end program test