整数の集合和

二つの整数配列があって、それぞれを集合の要素だと思って、二つの配列の集合和をとることを考える。

それは二つの配列を単純に合併したあとで 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