CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3
  1. #1
    Join Date
    Jan 2011
    Posts
    1

    Set Comparison Data Structures

    I have two sets S1 and S2. I need to be able to carry out the following operations: intersect, union, relative complement.

    I store S1 and S2 in BSTs so I can search elements in them. What data structure is most efficient to carry out operations above? Where can I find implementation of algorithms for above operations?

    Thanks,

    Monte

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Set Comparison Data Structures

    Quote Originally Posted by Monte_Carlo View Post
    What data structure is most efficient to carry out operations above? Where can I find implementation of algorithms for above operations?
    Where applicable the most efficient set implementation is the bitset. A set simply is represented by an integral data type (such as an unsigned int). It requires that the set elements are known beforehand and are fewer than the number of bits in the largest available integer primitive, typically 64. With two sets a and b represented like that you use the bitwise logical operators to conduct basic set operations, like

    intersection = a & b
    union = a | b
    relative complement = ~a & b

    In C++ there's a standard implementation called <bitset>.
    Last edited by nuzzle; January 29th, 2011 at 07:58 AM.

  3. #3
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    Re: Set Comparison Data Structures

    For the general case when you don't know the elements in advance, you could just keep everything in binary search trees and return a BST. For arrays of size n and m with n < m that will give you (I think...):

    Intersect: O(n log m)
    Union: O((n+m) log (n+m)) ~ O( m log m )
    Relative complement*: O(n log m)

    *Not sure about relative complement. Not sure of the exact functional definition.

    Just do them in the most obvious way possible, e.g. for intersection, ...

    Code:
    BST result
    foreach item in S1
       if item in S2
          add item to result
    return result
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured