본문 바로가기

자료구조 & 알고리즘

[박혜웅] 비트 벡터 (bit vector)

  • bit-vector for set 의 특징

    • 원소(문헌)을 정수로 식별할 수 있어야 한다.

      • 비트벡터의 각 비트가 각각 정수로 식별되기 때문
    • 처리 속도는 빠름

      • 비트연산을 이용하므로
    • 원소의 값 영역이 작을 때 유용

      • 원소의 간격(원소값이나 원소식별자번호)이 클 경우, 공간을 많이 사용함
    • 원소들 각각에 대해 한 비트를 할당하며, 집합을 일련의 비트로 표현

      • 집합안에 해당 원소가 있다면 비트를 1(TRUE)로, 없으면 0(FALSE)으로 표현
      • 비트에 접근하기 위하여, mask와 shift를 이용

 

  • 정보검색에서 비트벡터의 사용 예

    •  

 

  • bit-vector for set 의 성능

    • 삽입,삭제

      • O(C)
      • 하드웨어의 나눗셈 연산 속도에 의해 좌우됨
      • 하드웨어의 비트연산속도는 매우 빠르므로 성능에 끼치는 영향이 매우 작음
    • 반복회수

      • O( N/WORDSIZE ): 일반적인 연산시
      • O( N ): Iterate() 연산시
    • 저장공간

      • MAX_ELEMENT/WORDSIZE + sizeof(int)*2

        • sizeof(int)*2 = lower, upper 변수

 

  • 값이 i인 원소가 있는지(또는 원소식별자가 i인 원소가 있는지) 확인하는 코드

    1. ( vector[ (i-1)/8<< (i-1)%8 ) & 0x01
    2. vector[ (i-1)/8 ] & ( 0x01 >> (i-1)%8 )
    • 8 = sizeof(vector[0])

      • 위 식에서 8은 vector[x]의 크기
      • 일반적으로 1바이트(8비트)의 크기를 사용함
      • 컴퓨터 의 처리단위와 같도록 8의 배수(16,32....) 로 변경 가능
    • i-1

      • i번째 비트를 의미, 실제로 비트번호나 배열인덱스번호가 0에서 시작하므로
    • (i-1)/8

      • vector[ x ] 배열에서 i번째 원소의 정보가 저장된 배열 인덱스 x를 구함
    • (i-1)%8

      • vector[ x ]안에서 i번째 원소의 정보가 존재하는 비트번호
      •