二つの整数配列があって、それぞれを集合の要素だと思って、二つの配列の集合和をとることを考える。
それは二つの配列を単純に合併したあとで 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) ! deletes duplicate element 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
