c에서 일정 시간 동안 배열에서 3D 점 제거

Question

여기에 O (n)의 배열에서 3D 점을 제거하는 함수가 있습니다. 그러나 코드를 실행했을 때 어레이에서 약 16000 포인트가되면 제거하기에는 너무 길어졌습니다. 내 제거 코드를 더 빨리 만들고 싶습니다. 어떻게하면 코드를 변경하여 일정 시간 내에 제거하겠습니까?

int point_array_remove(point_array_t* pa, unsigned int i) 
{ 
    assert(pa); 
    if(i >= pa->len) 
     return 1; 
    pa->points[i] = pa->points[pa->len-1]; 
    while(i < pa->len-1) 
    { 
     pa->points[i] = pa->points[i+1]; 
     i++; 
    } 
    pa->len--; 
    return 0; 
} 

Answer 1

문제는 당신이 선형 이동하고있다 : 여기

typedef struct point 
{ 
    double x, y, z; 
} point_t; 

typedef struct 
{ 
    size_t len; 
    point_t* points; 
    size_t reserved; 

} point_array_t; 

이 배열의 3D 점을 제거하는 제 기능입니다 : 여기

내가 만든 구조체이다 간격을 좁히는 항목의 수. 필요한 경우 선형 시간 요구 사항을 피할 수 없습니다.

그러나 배열의 요소 순서가 중요하지 않은 경우 마지막 요소를 바로 간격으로 이동할 수 있습니다. 즉, 한 요소 만 이동하는 것입니다. 일정한 시간에 일정량의 작업을 수행 할 수 있습니다.

아직 마지막 요소를 검색해야하며 선형 시간이 필요하므로 문제가 있습니다. 그러나 배열의 크기를 알면 일정 시간 내에 마지막 항목으로 직접 이동할 수 있으므로 크기를 추적해야합니다. 정수 변수에 저장하고 배열 크기가 변경되면 업데이트하십시오.

주의 할 점이 하나 있습니다. 은 마지막 항목 인입니다.

편집

위가 허용되지 않는 경우, 당신이 할 수있는 모든 다른 데이터 구조와 배열을 대체합니다. 상수 시간 삽입 및 삭제에 대한 고전적인 데이터 구조 (올바른 항목/위치를 이미 찾았고 나머지 항목의 순서는 유지해야 함)가 링크 된 목록입니다.

링크 된 목록은 배열과 비교하여 비용이 많이 들기 때문에 준비가 되었으면 링크 된 목록과 배열을 결합하는 옵션이 있습니다. 링크 된 작은 배열 목록이 있습니다. 작은 배열은 고정 된 최대 크기를 가지며 포함 된 요소의 수를 알 수 있습니다. 삽입 및 삭제는 일정한 시간입니다. 왜냐하면 각각의 작은 배열은 이동할 요소의 일정한 수 (최대로) - 그 배열의 최대 크기 (이 경우에는 부정 행위)가 없기 때문입니다.

그래서 노드 유형 내가 아마도 너무 C++이 아닌 C로 사용이 약간 잘못있어 ... 같은

typedef struct 
{ 
    chain_node_t *next; 
    chain_node_t *prev; 
    unsigned  num_in_this_chunk; 
    point_t point [CHAIN_CHUNK_MAX]; 

} chain_node_t; 

을 보일 수 있지만, 쉽게 고칠 수 있어야한다.