IntSet 整數集合

13.3 IntSet 整數集合
- 13.3.1 ADT(C#)
- 13.3.2 核心思想
- 13.3.2 實作原理
- 13.3.3 遇到的問題及教訓
- 13.3.4 仍需要解決的問題

13.3 IntSet 整數集合

13.3.1 ADT(C#)

用接口封裝類，相當于隻開放類的部分功能

eg:

public interface ISet_my<T>
    {
        uint[] GetCoordinate(T element);
        uint[] Add(T element);  //加入元素element，傳回offset
        uint[] Remove(T element);
        //bool IsMember(T element);
        string GetBinString();  //get 二進制流，其實還是string流而不是bitString
        string PrintBinString();  //傳回BinString
        string GetIntString();  //傳回intString
        string PrintIntString();  
        ISet_my<T> Union(ISet_my<T> ISet_2);  //并集
        ISet_my<T> Intersect(ISet_my<T> ISet_2);  //交集
        ISet_my<T> DiffSet(ISet_my<T> ISet_2);  //差集
        ISet_my<T> Complement();  //補集
    }

13.3.2 核心思想

IntSet (整數集合) 的核心思想就是壓縮集合存儲更多資料，比如：

用一個int32空間存32個int

比起用32個int32空間存32個int，IntSet的開銷瞬間就小了是不是！

13.3.2 實作原理

bitMap(位圖) 和 GetCoordinate()

資料結構學習手冊——IntSet 整數集合13.3 IntSet 整數集合

public class IntSet_my : ISet_my <uint>  
    {
    //member
        private readonly uint[] _bitMap;  //_bitMap的比特流表示IntSet存儲資訊
        public uint _bitSize { get; }  //_bitMap的比特流占多少位二進制
     //contributor
        public IntSet_my(uint bitSize_0)
        {
            _bitSize = bitSize_0;
            _bitMap = new uint[_bitSize / 32 + 1];  //at lease 1 int32 to store IntSet
            for (int i = 0; i < _bitMap.Length; i++)  //initialize IntSet as null
                _bitMap[i] = 0;  
        }

        //get ( index_bitMap, index_bit )
        public uint[] GetCoordinate(uint e)   
        {
            uint[] coordiante = new uint[2];  //二進制坐标
            if (e > _bitSize)  //e不在
                throw new ArgumentOutOfRangeException();
            coordiante[0] = e / 32;  // bitMap index
            coordiante[1] = e % 32;  // bit index in bitMap[ coordiante[0] ]
            return coordiante;
        }

Add()和Remove()

資料結構學習手冊——IntSet 整數集合13.3 IntSet 整數集合

//add int to IntSet
        public uint[] Add( uint e )
        {
            uint[] coordi = GetCoordinate( e ); //get coordinate
            _bitMap[coordi[0]] |= (uint)Math.Pow(2, coordi[1]);  //add 
            return coordi;  //return index
        }

        //remove int from IntSet
        public uint[] Remove(uint e)
        {
            uint[] coordi = GetCoordinate(e);  //get coordinate
            _bitMap[coordi[0]] &= (~coordi[1]);  //remove
            return coordi;  //return index
        }

GetBinString()擷取二進制字元串和 GetIntString 擷取整數字元串

資料結構學習手冊——IntSet 整數集合13.3 IntSet 整數集合

public string GetBinString()
        {
            string binString = string.Empty;  //null string
            for (int i = 0; i < _bitMap.Length;)  //each _bitMap[]
            {
                //10進制int->2進制int->2進制string, 并在左側補齊到32位2進制
                binString = Convert.ToString(_bitMap[i++], 2).PadLeft(32, '0') + binString;  //補0友善之後輸出！
            }
            return binString;
        }

        public string PrintBinString()
        {
            string result = GetBinString();  //get binString
            Console.WriteLine("\n從右往左, 第0位為表示0的二進制位\n");
            for (int i = result.Length - 1; i >= 0; )  //each _bitMap[]
            {                
                //print binString                
                for(int k = 0; k < 4; k++)  //each 4 bit intervene  " "
                    Console.Write(result[i--]);
                Console.Write(" ");
                
            }
            Console.Write("\n");
            return result;
        }

資料結構學習手冊——IntSet 整數集合13.3 IntSet 整數集合

public string GetIntString()
        {
            string binString = this.GetBinString();
            string intString = string.Empty;
            for (int i = binString.Length - 1, j = 0; i >= 0; j++)  //each _bitMap[]
            {
                //print IntString
                if (binString[i--] == '1')                
                    intString += " " + Convert.ToString(j);              
            }
            return intString;
        }


        public string PrintIntString()
        {
            string result = this.GetIntString();  //get binString  
            Console.Write("\nIntSet中元素升序排列: {0} \n", result);
            return result;
        }

Union(), Intersect(), Differ()

進行交、并、補運算的機關是bitMap[] ！

(雖然根本上是計算機中的bit )
用接口封裝！

//Intersect
        public IntSet_my Intersect(IntSet_my IntSet_2)
        {
            IntSet_my IntersectSet;
            
            IntersectSet = new IntSet_my(this._bitSize < IntSet_2._bitSize ? 
                this._bitSize : IntSet_2._bitSize);  //交集大小取小的集合大小
            for (int i = 0; i < IntersectSet._bitMap.Length; i++) // IntersectSet[0~IntSet_2.bitSize) = union                 
                IntersectSet._bitMap[i] = this._bitMap[i] & IntSet_2._bitMap[i];  //運算為&, 實質上是int32->二進制&->int32        
            return IntersectSet;
        }

        //Differ
        public IntSet_my Differ(IntSet_my IntSet_2)
        {
            IntSet_my DifferSet = new IntSet_my(_bitSize);
            int differ_Size = _bitMap.Length < IntSet_2._bitMap.Length ? this._bitMap.Length : IntSet_2._bitMap.Length;
            for (int i = 0; i < differ_Size; i++) // DifferSet[0~_bitMap.Length) = Differ                 
                DifferSet._bitMap[i] = _bitMap[i] & (~IntSet_2._bitMap[i]);
            return DifferSet;
        }

        //Complement
        public IntSet_my Complement()
        {
            IntSet_my CompliSet = new IntSet_my(_bitSize);
            for (uint i = 0; i < _bitMap.Length; i++) // CompliSet[0~IntSet_2.bitSize) = Compli                 
                CompliSet._bitMap[i] = ~this._bitMap[i];
            return CompliSet;
        }
//接口
        ISet_my<uint> ISet_my<uint>.Union(ISet_my<uint> ISet_2)
        {
            return Union(ISet_2 as IntSet_my);
        }

        ISet_my<uint> ISet_my<uint>.Intersect(ISet_my<uint> ISet_2)
        {
            return Intersect(ISet_2 as IntSet_my);
        }

        ISet_my<uint> ISet_my<uint>.DiffSet(ISet_my<uint> ISet_2)
        {
            return Differ(ISet_2 as IntSet_my);
        }

        ISet_my<uint> ISet_my<uint>.Complement()
        {
            return Complement();
        }

13.3.3 遇到的問題及教訓

Convert方法不了解

在10進制int轉二進制int時一直想着要轉成計算機bit，但不知道要用什麼方法實作

比如：

Convert.ToBase64CharArray( Byte[] inArray, Int32 offsetIn, Int32 length, Char[] outArray, Int32 offsetOut)
- inArray 為要轉化的 8-bit unsigned integer 數組
- offsetIn 為 inArray轉化部分的起始索引
- length 為 inArray轉化部分的長度
- outArray 為要輸出的字元數組
- offsetOut 為要輸出的字元數組的起始索引
ToBase64隻支援int8，bitMap的存儲機關是int32。

這個好像隻能靠積累了…
設計時，print功能和getValue功能要分開
交集差集補集合都是以int32 數組元素為機關計算
string == ‘1’ 而不是 string == “1” 或者 string == 1 ！！！
在VS裡，int 如何轉化加入string
- 不能暴力轉char ，eg: (char) j, 這樣ASCII和Unicode編碼不相容，會亂碼
- 隻有轉成Unicode的string，eg: Conver.ToString(j)

13.3.4 仍需要解決的問題

泛型接口具體使用方法???
Unicode, ASCII, Utf-8 編碼差別

資料結構學習手冊——IntSet 整數集合13.3 IntSet 整數集合

IntSet 整數集合

13.3 IntSet 整數集合

13.3.1 ADT(C#)

13.3.2 核心思想

13.3.2 實作原理

13.3.3 遇到的問題及教訓

13.3.4 仍需要解決的問題

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器