숫자가 주어진 범위에 이미 존재하는지 확인해야합니다.

Question

동적으로 증가/감소 할 수있는 여러 범위가 구성되었으므로 주어진 수의 존재 여부를 찾기 위해 가장 빠른 방법을 찾아야합니다. 범위를 돌려 주시겠습니까? 누군가가 C에서 가장 빠른 알고리즘이나 데이터 구조를 제안하여 이러한 작업을 수행 할 수 있습니까? 다음

코드 조각은 :

위의 코드에서

addr = GET_U32BIT(buf); 

    /* Search for the corresponding address */ 
    while(i < addr_table_size) 
    { 
     if((addr >= ntohl(table->addr_id[i].start_addr)) && \ 
       (addr <= ntohl(table->addr_id[i].end_addr))) 
     { 
      addr_present = 1; 
      range_id = i; 
      break;   
     } 
     i++; 
    } 

가 ADDR은 버퍼로부터 유도 된 4 바이트 번호는 런타임에서 수신되는 테이블에 선형 검색을 수행하는 동안 위치를 시작할 end addr가 저장되면 테이블에 약 50,000 ~ 100,000 개의 항목이있을 수 있으므로 성능이 매우 낮습니다.

감사합니다.

Answer 1

간격 트리를 사용하여이를 수행 할 수 있습니다. 각 범위에 대해 간격 트리에 항목을 하나씩 삽입하십시오.

이제 'k'가 속하는 범위를 검색하려고합니다. 간격 트리에서 검색하십시오. 또한 범위가 변경 될 때마다 해당 범위를 간격에서 삭제하고 새 값으로 다시 삽입하십시오.