빠른 버킷 구현

Question

그래프 클래스에서 정수 값 (주로 1 ~ 1000)을 가진 노드를 처리해야합니다. 모든 단계에서 그래프에서 노드와 모든 이웃을 제거하려고합니다. 또한 나는 항상 최소값의 노드로 시작하고 싶다. 나는 가장 빠른 방법으로이 작업을 수행하는 방법에 대해 오랫동안 생각하고 다음을 수행하기로 결정 adjancency 목록을 사용하여 저장됩니다

• 그래프
• 값
하여 노드를 저장하는 거대한 배열 std::vector<Node*> bucket[1000]이있다
• 가장 낮은 비어 있지 않은 버킷의 인덱스는 항상 통이 비어 증가는 이미 인덱스
• 경우 내가 그 인덱스의 임의의 요소를 선택하여 매우 빠른 최소 값의 노드를 찾거나 할 수 저장
• 오프 트랙을 유지 선택한 노드 제거하기 버킷은 분명히 O (1)에서 수행 할 수 있지만 문제는 이웃 노드를 제거하기 위해 모든 이웃 노드에 대해 버킷 버킷 [이웃 노드의 값]을 검색해야한다는 것인데, 이는 실제로 빠르지 않습니다.

더 효율적인 방법이 있습니까?

나는 std::list<Node*> bucket[1000]과 같은 것을 사용하고 모든 노드에 O (1)의 목록에서 노드를 제거 할 수 있도록 "list element"에 대한 포인터를 할당 할 것을 고려했습니다. 이것은 stl리스트에서 가능합니까? 분명히 손으로 구현할 수있는 정상적인 이중 링크리스트로 할 수 있습니까?

Answer 1

최근 버킷을 사용하는 우선 순위 큐 구현에 대해 이와 비슷한 작업을했습니다.

해시 테이블 (unordered_map)을 사용하면 1000 개의 빈 벡터를 저장할 필요가 없으며 여전히 O (1) 임의 액세스 (일반적인 경우, 보장되지 않음)를 얻을 수 있습니다. 자,이 그래프 클래스를 한 번만 저장/생성해야한다면 아마도 중요하지 않을 것입니다. 필자의 경우 우선 순위 큐를 초당 수십/수백 번 생성해야했으며 해시 맵을 사용하여 큰 차이를 만들 필요가있었습니다 (실제로 우선 순위의 요소가있을 때 unordered_sets 만 작성했기 때문에 1000 개의 빈 해시 세트 초기화). 해시 세트와 맵은 C++ 11에서 새로 추가되었지만 현재 std :: tr1에서 잠시 동안 사용 가능하거나 Boost 라이브러리를 사용할 수 있습니다.

내 & 사이에서 볼 수있는 유일한 차이점은 인접 노드를 제거 할 수 있어야한다는 것입니다. 나는 모든 노드가 그것의 이웃에 대한 포인터의리스트를 가지고 있다고 가정하고있다. 그렇다면, 이웃들의 삭제는 k 이웃들의 수 (일반적으로 O (1), 보장되지 않음, 최악의 경우는 unordered_map/set에서 O (n) 임)로 k * O(1)을 취해야합니다. 모든 이웃 노드로 가서 우선 순위를 얻으면 해시 맵에 올바른 색인을 제공합니다. 그런 다음 우선 순위가 매핑되는 해시 집합에서 포인터를 찾으면이 검색은 일반적으로 O (1)가되고 요소를 제거하는 것은 일반적으로 다시 O (1)가됩니다.

모두 당신이해야 할 일에 대해 꽤 좋은 아이디어가 있다고 생각하지만 해시지도/세트를 사용하면 코드 사용 속도가 상당히 빨라질 것이라고 생각합니다 (정확한 사용법에 따라 다름). 필자의 경우 unordered_map<int, unordered_set> 대 vector<set>의 구현 속도 향상은 약 50 배였습니다.

Answer 2

다음은 내가하는 일입니다. 노드 구조 :

struct Node { 
    std::vector<Node*>::const_iterator first_neighbor; 
    std::vector<Node*>::const_iterator last_neighbor; 
    int value; 
    bool deleted; 
}; 

이 인접 목록을 연결하고 메모리 관리의 오버 헤드를 낮추기 위해 하나의 std::vector<Node*>에 넣어. 업데이트 속도가 중요하지 않기 때문에 소프트 삭제 기능을 사용하고 있습니다.

값을 기준으로 노드에 대한 포인터를 counting sort 인 또 다른 std::vector<Node*>에 정렬하십시오. 모든 노드를 삭제되지 않은 것으로 표시하십시오.

정렬 된 순서로 노드를 반복합니다. 고려중인 노드가 삭제 된 경우 다음 노드로 이동하십시오. 그렇지 않으면 삭제 된 것으로 표시하고 이웃을 반복하여 삭제 된 것으로 표시합니다. 당신의 노드가 메모리에 연속적으로 저장되어있는 경우 노드의 last_neighbor이 성공 노드의 first_neighbor 때문에

, 당신은, 구조의 끝에 추가 감시 림프절의 비용 last_neighbor를 생략 할 수 있습니다.