저전력 프로세서 용 빠른 검색 - 삽입 - 삭제 알고리즘

Question

들어오는 데이터에 빠르게 응답해야하는 저전력 프로세서에서 실행되는 응용 프로그램이 있습니다. 데이터는 연관된 키와 함께 제공됩니다. 각 키의 범위는 0 - 0xFE (최대 0xFF)입니다. 데이터 자체의 크기는 1kB에서 4kB까지입니다. 시스템은 다음과 같은 데이터를 처리합니다.

data in 
key lookup -> insert key & data if not found 
buffer data in existing key 

일부 이벤트가 발생하면 키와 관련 데이터가 삭제됩니다.

우리는 솔루션의 몇 시운전됩니다

1. 사전 할당 std::vector<std::pair<int,unsigned char *>>를, 인덱스 위치를 기반으로 키 값을 보이는. 이진 정렬과 이진 검색과

2. std::map<int, unsigned char *>

3. 레드 - 블랙 트리

4. std::vector<...> 키의

삽입 -에 빨리 수있는 다른 알고리즘이 있습니까 검색 삭제?

감사합니다. 키 범위 [0, 0xFF)에있는 경우

Answer 1

, 당신은이를 사용할 수 있습니다 : 그 데이터를 나타 내기 위해 빈 문자열을 사용

std::vector<std::string> lut(0xFF); //lookup table 

//insert 
lut[key] = data; //insert data at position 'key' 

//delete 
lut[key].clear(); //clear - it means data empty 

//search 
if(lut[key].empty())  //empty string means no key, no data! 
{ 
    //key not found 
} 
else 
{ 
    std::string & data = lut[key]; //found 
} 

참고가 존재하지 않습니다.

Answer 2

std::map은 균형 잡힌 나무 (예 : 빨강 검정 나무)를 사용하므로 다시 구현할 필요가 없습니다.

이진 검색을 사용하여 std::vector을 정렬하면 균형 조정 된 이진 트리와 동일한 성능을 보입니다. 차이점은 벡터의 중간에 키를 배치하는 것이 비용이 많이 든다는 것입니다. 열쇠는 매우 제한된 범위를 가지고 있기 때문에

, 당신의 최선의 선택은 첫 번째 제안과 유사합니다

std::vector<unsigned char *> data(0xFF); // no need to have a pair 

이 방법은 data[key] == NULL의 간단한 확인이 키에 대한 데이터가 존재하는지 여부를 보여줍니다.

unsigned char *data[0xFF];