c#中数值型集合加速运算

为了专门针对数值类型的集合，使用BitArray类会更加合适。 使用BitArray来存储整数集合成员的好处很多： 1.由于实际上只是存储布尔类型的数值，所以对于存储空间的要求很小。 2.对于并集，交集，差集，子集的计算会更加快速。 策略如下：

  如果要添加成员1到集合，这里就把索引位置为1的数组设置为true。如果要把4添加到集合中，就把位置为4的元素设置为true。通过简单测试数组位置上那个为true就可以确定那个成员在集合中了。

using System; using System.Collections; using System.Collections.Generic; using System.Configuration; using System.Runtime.InteropServices.ComTypes; public class CSet { private BitArray data; public CSet() { data=new BitArray(5); //构造这数组 } public void Add(int item) { data[item] = true; //将需要添加的位置上的数值设置为true } public bool IsMember(int item) { return data[item]; //是否包含在数组中 } public void Remove(int item) { data[item] = false; //将这个位置上的值设置为false } public CSet Union(CSet aset) { CSet tempset=new CSet(); for (int i = 0; i < data.Count; i++) { tempset.data[i] = (this.data[i] || aset.data[i]); } return tempset; //返回这个数组 } public CSet Intersection(CSet aset) { CSet tempset=new CSet(); for (int i = 0; i < data.Count; i++) {//如果连个数组都是true才是交集 tempset.data[i] = (this.data[i] && aset.data[i]); } return tempset; } public CSet Difference(CSet aset) { CSet tempset=new CSet(); for (int i = 0; i < data.Count; i++) {//计算a包含b不包含 tempset.data[i] = (this.data[i] && (!aset.data[i])); } return tempset; } public bool IsSubset(CSet aset) {//循环a，一旦a包含b不包含立马退出 CSet tempset=new CSet(); for(int i=0;i<data.Count;i++) if (this.data[i] && (!aset.data[i])) return false; return true; } public override string ToString() { string s = " "; for(int i=0;i<data.Count;i++) if (data[i]) s += i+" "; return s; } } public class Test { public static void Main() { CSet setA=new CSet(); CSet setB=new CSet(); setA.Add(1); setA.Add(2); setA.Add(3); setB.Add(2); setB.Add(3); CSet setC = setA.Union(setB); Console.WriteLine(setC.ToString()); } }

改进版

using System; using System.Collections.Generic; using System.Collections; public class CSet { public BitArray data; //定义二值数组 public CSet() { data=new BitArray(10); //定义大小为10的数组 } //添加 public void Add(int i) { data[i] = true; } //移除 public void Remove(int i) { data[i] = false; } //计算并集 public CSet Union(CSet bset) { CSet newset=new CSet(); newset.data = data.Or(bset.data); //进行或运算 return newset; } //计算交集 public CSet Inter(CSet bset) { CSet newset=new CSet(); newset.data = data.And(bset.data); return newset; } //计算差集 public CSet Different(CSet bset) { CSet newset=new CSet(); newset.data = bset.data.Not().And(data); return newset; } //是否为子集 public bool IsSubSet(CSet bset) { for(int i=0;i<data.Count;i++) if (data[i]&&(!bset.data[i])) return false; return true; } //输出 public override string ToString() { string s = " "; for (int i = 0; i < data.Count; i++) if(data[i]) s += i.ToString() + " "; return s; } } public class Test { public static void Main() { CSet aset=new CSet(); CSet bset=new CSet(); aset.Add(1); aset.Add(3); aset.Add(4); bset.Add(1); bset.Add(2); bset.Add(4); bool cset = aset.IsSubSet(bset); Console.WriteLine(cset); } }