효율적으로 등가물을 저장하는 방법 (연결 구성 요소 레이블 지정 알고리즘에서)?

Question

Connected-component labeling algorithm에서 등가물을 저장하고 싶습니다. 기본적으로 하나의 값 (하나의 레이블 ID)에서 여러 값 (이전 값과 동일한 레이블의 ID)으로 맵을 만들고 있습니다.

저는 이미 이와 같은 작업을 수행했지만 실제로는 잘 작동하지 않습니다.

이 방법의 가장 큰 단점은 내가 정면 map의 크기를 선언해야한다는 것입니다

equivalences.at(i).push_back(equivalent_labels_int); 

대형에 대한 다음과 (이 충분한 크기이어야한다) :

std::map<unsigned short, std::list<unsigned int>> equivalences; 
for(int i = 0; i < MAX_NUMBER_OF_LABELS; ++i) 
{ 
    std::list<unsigned int> temp; 
    temp.push_back(i); 
    // note that a label is equivalent to itself 
    equivalences.insert(std::pair< int, std::list<unsigned int>>(i, temp)); 
} 

는 그럼으로 적절한 등가를 추가 크기 (예 : 9999) 초기화 시간은 약 2.5 초.

누구나 더 좋은 아이디어가 있습니까?

Answer 1

map의 크기를 C++ (또는 대부분의 언어)로 정할 필요는 없습니다. map은 새 요소가 추가되어 동적으로 확장 될 수 있으므로 새 키를 찾으면 언제든지지도에 추가 할 수 있습니다. 예를 들어이 아직 존재하지 않는 경우 map의 사각 괄호 연산자 (operator[])가 자동으로 지정된 키 및 디폴트 값으로 map에 새 키/값 쌍을 추가하기 때문에

equivalences[i].push_back(equivalent_labels_int); 

이 작동 .

또한 연결 머리글 시퀀스를 저장하기위한 컨테이너로 list을 사용하지 말 것을 권합니다. list은 무작위 액세스가 필요하지 않고 시퀀스 중간에서 요소를 자주 제거 할 때 유용합니다. 실제로 여기에서 수행하고 있다고 생각하지 않습니다. 대신, vector 또는 deque을 사용하는 것이 좋습니다. 그 구조는 공간 효율성이 높고 지역성이 좋기 때문입니다.

마지막으로 사용자의 필요에 따라 데이터 구조를 완전히 전환 할 수 있습니다. 알고리즘이 어떤 출발점에서 깊이 우선 검색을 실행 한 다음 발견 한 모든 결과를 저장하여 작동하는 경우 지금 접근 한 방식이 상당히 좋을 수 있습니다. 그러나 알고리즘이 유사하고 비슷한 점들의 쌍을 찾은 다음 포함 된 모양을 함께 병합하는 경우 disjoint-set forest data structure에 관심이있을 수 있습니다. 이는 간단한 구현이지만 성능은 매우 뛰어납니다. 즉,이 구조를 사용하면 주어진 지점에 어떤 점이 연결되어 있는지 확인할 수 없지만 효율성은 향상됩니다.

희망이 도움이됩니다.

Answer 2

나는 Disjoint set forests이 당신이 찾고있는 것 같아요. 다음은이 데이터 구조의 a better description입니다.