C\#비트 맵 BitArray 사용

앞에서 부 릉 필터 에 대해 이 야 기 를 나 누 었 고 비트 맵 BitMap 을 알 아 보 았 습 니 다.앞의 글 을 읽 은 학생 들 은 부 릉 필터 자체 가 비트 맵 에 기반 한 것 이 고 비트 맵 의 개선 이라는 것 을 알 게 되 었 을 것 입 니 다.
비트 맵
먼저 문 제 를 살 펴 보 자.만약 에 1 천만 개의 정수 가 있다 면 정수 범 위 는 1 억 에서 1 억 사이 에 있 는데 어떻게 특정한 정수 가 이 1 천만 개의 정수 에 있 는 지 신속하게 확인 할 수 있 을 까?
얼핏 보면 문 제 를 찾 는 것 이 고 순환,2 분 검색 은 모두 일반적인 사고 이다.

좋 은 답 은 저장 구조 와 알고리즘 의 완벽 한 결합 이다.문제 의 특징 과 조건 을 바탕 으로 우리 가 다른 사고방식 을 가지 고 있 는 지 여부 다.
문제 에 대해 우 리 는 고등학교 배열 조합의 사 고 를 사용한다.1 억 개의 번호 가 있 는 빈 바구니 가 있 는데 우 리 는 이 1 천만 개의 숫자 가 있 는 공 을 꺼 내 해당 하 는 바구니 에 넣는다.

마지막 으로 모든 바 구 니 는 두 가지 상태 가 있다.공이 있 는 지 없 는 지,우 리 는 어떤 숫자 가 존재 하 는 지 확인 하려 면 해당 바구니 가 비어 있 는 지 를 봐 야 한다.
비트 맵 이 무엇 입 니까?모든 사람 이 특정한 상 태 를 저장 하고 대량의 데 이 터 를 저장 하 며 데이터 가 존재 하 는 지 여 부 를 판단 하 는 데 사용 된다.비트 맵 의 공간 은 데이터 의 최대 값 에 의 해 결정 된다.
비트 맵 이라는 데이터 구 조 는 메모리 의 사용량 을 크게 절약 할 수 있다.
우 리 는 길이 가 1 억 인 bit 배열 을 만 들 고 공의 위 치 를 1 로 표시 하 며 공 없 는 위 치 는 기본적으로 0 으로 기록 해 야 한다.이렇게 해서 우 리 는 숫자 를 압축 된 치밀 한 배열 색인 으로 바 꾸 었 고 1 억 bit 배열 은 16M 공간 이 되 지 않 았 다.
어떤 위치 에 공이 있 는 지 확인 하려 면 O(1)의 시간 복잡 도 만 필요 하 다.
상용 속성
Count BitArray 에 인 스 턴 스 를 포함 하 는 개수
IsReadOnly 에서 값 을 가 져 옵 니 다.이 값 은 BitArray 가 읽 기만 하 는 지 여 부 를 표시 합 니 다.
Item BitArray 의 특정 위치 값 가 져 오기 또는 설정
Length BitArray 에서 요소 의 수 를 가 져 오 거나 설정 합 니 다.
상용 방법
And 지정 한 BitArray 에 해당 하 는 요소 와 and 연산 하기
Or 비트 또는 연산
Xor 비트 별 또는 연산
모든 요 소 를 되 돌리 지 않 음
Get 특정 위치의 값 가 져 오기
Set 특정 위치 값 설정
SetAll 은 BitArray 의 모든 요 소 를 지정 한 값 으로 설정 합 니 다. 

public sealed class BitArray : ICollection, IEnumerable, ICloneable
{
    public BitArray(BitArray bits); //    BitArray   BitArray   
    
    public BitArray(bool[] values); //        
    
    public BitArray(byte[] bytes);  //        
    
    public BitArray(int length);    //         ，           
    
    public BitArray(int[] values);  // int     
    
    public BitArray(int length, bool defaultValue); //         
    
    public int Count { get; }   //           
    
    public bool IsReadOnly { get; } //         

    public bool IsSynchronized { get; } //      BitArray   ，       
    
    public int Length { get; set; }   //      

    public object SyncRoot { get; }
    
    public bool this[int index] { get; set; } //   ，       
    
    public BitArray And(BitArray value);  //   

    public object Clone();  //  BitArray      。
    
    public void CopyTo(Array array, int index);  // BitArray        
    
    public bool Get(int index);    //       

    public IEnumerator GetEnumerator(); //      BitArray     

    public BitArray Not();  //   

    public BitArray Or(BitArray value);  //   
    
    public void Set(int index, bool value);  //     
    
    public void SetAll(bool value); //         

    public BitArray Xor(BitArray value);  //    
}

C\#전문 적 인 비트 맵 배열 이 있 습 니 다:BitArray

using System;
using System.Collections;

namespace Bitmap
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine();
            var num = int.Parse(input);
            var bitmap = InitBitMap();
            if (bitmap.Get(num))
            {
                Console.WriteLine($"    {num}");
            }
            else
            {
                Console.WriteLine($"     {num}");
            }
        }
        public static BitArray InitBitMap()
        {
            var myBA1 = new BitArray(10000);
            var arr1 = new int[] { 1, 2, 4, 6, 77, 77, 88, 99, 100, 500, 600, 700, 999, 8888 };
            foreach (int element in arr1)
            {
                myBA1[element] = true;
            }
            return myBA1;
        }
    }
}

BitArray 는 비트 값 을 관리 하 는 빈 틈 없 는 배열 로,그 중에서 true 는 비트 가 열 려 있 음(1),false 는 비트 가 닫 혀 있 음(0)을 나타 내 는 인용 형식 으로 System.Collections 네 임 스페이스 에 있 습 니 다.
이상 은 소 칼 시험 일 뿐 입 니 다.우 리 는 원 제 를 대상 으로 다시 한 번 발산 합 니 다.어떻게 상기 1 천만 숫자 에서 중복 되 는 숫자 를 찾 습 니까?
아니면 바구니 에서 공 을 넣 는 사고 인지 이번 에는 두 줄 의 바구니,즉 두 개의 비트 맵 을 원 합 니 다.비트 AND 연산(동시에 True,결과 가 True)을 이용 하여 두 줄 의 바구니 에 모두 공이 있 는 위 치 를 찾 아야 합 니 다.

using System;
using System.Collections;

namespace Bitmap
{
    class Program
    {
        static void Main(string[] args)
        {
            var bitmap = InitBitMap();
            for (int i = 0; i < bitmap.Length; i++)
            {
                if(bitmap[i] == true)
                {
                    Console.WriteLine(i);
                }
            }
        }
        public static BitArray InitBitMap()
        {
            var myBA1 = new BitArray(10000);
            var myBA2 = new BitArray(10000);
            var arr1 = new int[] { 1, 2, 4, 6, 77, 77, 88, 99, 100, 500, 600, 700, 999, 8888 };
            foreach (int element in arr1)
            {
                if (myBA1[element] == false)
                {
                    myBA1[element] = true;
                }
                else
                {
                    myBA2[element] = true;
                }
            }
            myBA1 = myBA1.And(myBA2);
            return myBA1;
        }
    }
}

마지막 알림:보물 구성 요소 Redis 천연 지원 비트 맵

C\#비트 맵 BitArray 사용 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C\#비트 맵 BitArray 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!