golang 位运算与位向量求交集/并集/对称差/差集

集合的交集,并集,对称差,差集是经常会遇到的算法,尤其是交集,并集。go 语言的集合通常使用 map[T]bool 来实现,其中 T 是元素类型。但是它不是最优的设计,今天我们要使用位向量数据结构来求解它们。介绍位向量求解交集,并集之前,我们要先了解一下位运算。几乎每门编程语言都支持位运算,而且基本一致。
&       位运算 AND (交集)
|         位运算 OR (并集)
^       位运算 XOR (对称差)
&^    位运算 AND NOT (差集)
 

位运算


首先用一个简单的例子来介绍位运算与集合的关系,将一个 uint8 值(00000010)作为位集,其含有 8 个独立的位,我们可以将每个位理解成一个集合原始。 将 01000010 表示一个集合 {1, 6}。由于只有 8 个位,它仅仅能表达 0-7 的8个集合元素,更大的数字比如元素 168 如何用位表示呢,后面也会介绍。如下定义两个用位表示的变量:x,y
x
1 0 0 1 0 0 1 0
集合 {1, 4, 7}
y
0 1 0 0 0 0 1 0
集合 {4, 6}
 
 
 
package main

import "fmt"

func main() {
   var x uint8 = 1<<1 | 1<<4 | 1<<7
   var y uint8 = 1<<4 | 1<<6

   fmt.Printf("%08b\n", x)  // 10010010,代表集合 {1, 4, 7}
   fmt.Printf("%08b\n", y)  // 01010000,代表集合 {4, 6}
   fmt.Printf("%08b\n", x&y) // 00010000,代表交集 {4}
   fmt.Printf("%08b\n", x|y) // 11010010,代表并集 {1, 4, 6, 7}
   fmt.Printf("%08b\n", x^y) // 11000010,代表对称差 {1, 6, 7}
   fmt.Printf("%08b\n", x&^y) // 10000010,代表差集 {1, 7}

   // 打印集合 x 将输出 1 4 7
   for i := uint(0); i < 8; i++ {
      if x&(1<<i) != 0 {
         fmt.Println(i)
      }
   }
   // 打印集合 y 将输出 4 6
   for i := uint(0); i < 8; i++ {
      if y&(1<<i) != 0 {
         fmt.Println(i)
      }
   }
}
上面代码执行结果如下
 

位向量


如果理解了上面的位运算,接下来的交集,并集,对称差,差集就不难理解了,也是运用了上面原理。比如上面提到的元素 168 如何用位来表示呢?先看看集合的定义与元素是如何添加的:
// 定义一个无符号的整型集合(小的非负整数)
type IntSet struct {
   words []uint64
}
// 添加集合元素
func (s *IntSet) Add(x int) {
   word, bit := x/64, uint(x%64)
   for word >= len(s.words) {
      s.words = append(s.words, 0)
   }
   s.words[word] |= 1 << bit
}
集合的元素将存储在这个 words 中,但是并非一一对应的存储到每个索引,比如我们要向集合添加元素 168,它并非直接 append(words, 168),而是对168/64=2,168%64=40,它将跨 3 个索引值来表达 168,words[0],words[1],words[2],调试可见它的值,前两个都是 0,第三个值非常大 1099511627776,它是 2 的 40 次方,所以它只适应比较小的整数集合,元素值太大将报错 fatal error: out of memory,添加元素 16800000000,能够成功完成集合并集,但是比较费时,花费 10 秒上下,百万级别的数值,能在2毫秒内完成,所以我们的集合元素只要不大于1000000,性能基本问题不大。到这里,我们应该大概明白原理,它与之前的位运算是一样的,之前是用 8 个位来存储 0-7,而这里是用 64 个位来存储元素的取模(168/64=40)。


同时,我们还可以发现一个规律,如果我们向集合添加 0-63,这些小整数,它都被存储在 words[0],而 64-127 被存储在 words[1],以此类推。。。
 
下面的全量代码,包含并集,可以直接执行调试
package main

import (
   "bytes"
   "fmt"
)

func main() {
   // 定义集合 x, y,并添加整型元素
   var x, y IntSet
   x.Add(1)
   x.Add(168)
   x.Add(9)
   x.Add(88)
   fmt.Printf("集合x\t%s\n", x.String())

   y.Add(9)
   y.Add(42)
   fmt.Printf("集合y\t%s\n", y.String())

   x.UnionWith(&y)
   fmt.Printf("xy的并集:\t%s\n", x.String())

   fmt.Printf("xy的并集是否包含9%txy的并集是否包含123%t", x.Has(9), x.Has(123))
}

// 定义一个无符号的整型集合(小的非负整数)
type IntSet struct {
   words []uint64
}

// 集合是否包含元素
func (s *IntSet) Has(x int) bool {
   word, bit := x/64, uint(x%64)
   return word < len(s.words) && s.words[word]&(1<<bit) != 0
}

// 添加集合元素
func (s *IntSet) Add(x int) {
   word, bit := x/64, uint(x%64)
   for word >= len(s.words) {
      s.words = append(s.words, 0)
   }
   s.words[word] |= 1 << bit
}

// 计算两个集合的并集
func (s *IntSet) UnionWith(t *IntSet) {
   for i, tword := range t.words {
      if i < len(s.words) {
         s.words[i] |= tword
      } else {
         s.words = append(s.words, tword)
      }
   }
}

// 输出集合
func (s *IntSet) String() string {
   var buf bytes.Buffer
   buf.WriteByte('{')
   for i, word := range s.words {
      if word == 0 {
         continue
      }
      for j := 0; j < 64; j++ {
         if word&(1<<uint(j)) != 0 {
            if buf.Len() > len("{") {
               buf.WriteByte(' ')
            }
            fmt.Fprintf(&buf, "%d", 64*i+j)
         }
      }
   }
   buf.WriteByte('}')
   return buf.String()
}
上面程序执行结果如何
 
交集方法
func (s *IntSet) Intersection(t *IntSet) {
   result := new(IntSet)
   for i, w := range t.words {
      if i < len(s.words) {
         result.words = append(result.words, w & s.words[i])
      }
   }

   s.words = result.words
}
对称差方法 
func (s *IntSet) SymmetricDifference(t *IntSet) {
   for i, tword := range t.words {
      if i < len(s.words) {
         s.words[i] ^= tword
      } else {
         s.words = append(s.words, tword)
      }
   }
}
差集方法
func (s *IntSet) DifferenceSet(t *IntSet) {
   for i, tword := range t.words {
      if i < len(s.words) {
         s.words[i] &^= tword
      }
   }
}
Posted by 何敏 on 2020-02-20 08:40:33