비트 배열을 사용 하시겠습니까?

Question

고정 된 일정한 '옵션'(예 : 기술) 세트가 있다고 상상해보십시오. 모든 객체 (예 : 인간)는 옵션을 갖거나 갖지 않을 수 있습니다.

모든 개체에 대해 member-list-of-options를 유지 관리하고 옵션으로 채워야합니까?

OR :

인가 그것을보다 효율적으로 (빠르게) 각 비트가 각각의 옵션의 촬영 (또는 촬영되지 않음) 상태를 나타내는 bitarray를 사용하는?

가 -edited : -

더 구체적으로, 기술의 목록은 문자열 (옵션 이름), 확실히 미만 256 프로그램이 가능한 한 빨리하는 대상은 (의 벡터이다 메모리 걱정 없음).

Answer 1

다소 다릅니다. 옵션 수가 적 으면 여러 개의 bool 멤버를 사용하여 옵션을 나타냅니다. 목록이 커질 경우, 두 옵션은 실행 가능한이 될 :

• 비트 세트 (이 적절한 상징적으로 옵션을 대표하는 enum) 공간, 일정, 매우 적은 양이 소요되며, 특정 옵션이 필요지고 O (1) 시간;
• 옵션 목록 또는 그 중 std::set 또는 unordered_set은 공간 효율성이 더 좋을 수 있지만 옵션 수가 많으면 만이고 매우 작은 수가 설정 될 것으로 예상됩니다 개체 당.

확실치 않은 경우 bool 개의 무리 또는 bitset을 사용하십시오. 프로파일 링에서 저장 옵션이 부담이된다는 것을 보여줄 때에 만 동적 목록이나 표현을 고려해야합니다. 그런 다음에도 디자인을 다시 생각해보십시오.

: 256 개 미만의 옵션으로 bitset은 최대 64 바이트를 차지하며 메모리 및 예상 속도와 관련하여 모든 목록 또는 세트 표현을 확실히 능가합니다. bool 또는 심지어 unsigned char의 배열은 바이트 액세스가 일반적으로 비트 액세스보다 빠르기 때문에 여전히 더 빠를 수 있습니다. 그러나 구조를 복사하는 것이 더 느릴 것이므로 몇 가지 옵션을 시도하고 결과를 측정하십시오. YMMV.

Answer 2

한 번의 작업으로 여러 스킬이 있는지 테스트 할 때 비트 배열을 사용하는 것이 더 빠릅니다.

옵션 목록을 사용하는 경우 한 번에 한 항목 씩 목록을 검토하여 스킬 세트가 종료되는지 확인해야합니다. 그러면 분명히 시간이 오래 걸리고 많은 비교 작업이 필요합니다.

Answer 3

일반적으로 비트 배열의 편집 속도가 빠르고 검색 속도가 빠릅니다. 필요한 공간은 수학 만 수행하면됩니다. 옵션 목록에는 동적으로 크기가 지정된 배열이 필요합니다 (이는 옵션 세트 자체에 약간의 오버 헤드가 있습니다). 그러나 많은 수의 옵션이있는 경우, (일반적으로) 소수의 옵션 만 설정하면 더 작아 질 수 있습니다.