complexity - unordered_map c++>



unordered_map에서 무작위 요소를 선택하십시오. (3)

다음과 같이 unordered_map 정의합니다.

std::unordered_map<std::string, Edge> edges;

unordered_map 가장자리에서 임의의 가장자리를 선택하는 효율적인 방법이 있습니까?

https://ffff65535.com


unordered_map 가장자리에서 임의의 가장자리를 선택하는 효율적인 방법이 있습니까?

효율적으로 O (1)을 의미한다면, 아니오, 불가능합니다.

unordered_map::begin / end 의해 반환되는 반복자는 ForwardIterator , 단순히 std::advance 를 사용하는 접근법은 요소의 수에서 O (n)입니다.

특정 용도로 허용되는 경우 효율을 위해 임의성을 교환 할 수 있습니다.

랜덤 버킷 (O (1)에서 액세스 할 수 있음)을 선택한 다음 해당 버킷 안의 임의의 요소를 선택할 수 있습니다.

int bucket, bucket_size;
do
{ 
    bucket = rnd(edges.bucket_count());
}
while ( (bucket_size = edges.bucket_size(bucket)) == 0 );

auto element = std::next(edges.begin(bucket), rnd(bucket_size));

여기서 rnd(n) 는 [0, n] 범위의 난수를 반환합니다.

실제로 괜찮은 해시를 사용하면 대부분의 버킷에는 정확히 하나의 요소가 포함됩니다. 그렇지 않으면이 함수는 버킷에 홀로있는 요소에 약간의 권한을 부여합니다.


Pre-C ++ 11 솔루션 :

std::tr1::unordered_map<std::string, Edge> edges;
std::tr1::unordered_map<std::string, Edge>::iterator random_it = edges.begin();
std::advance(random_it, rand_between(0, edges.size()));

C ++ 11 이후 솔루션 :

std::unordered_map<std::string, Edge> edges;
auto random_it = std::next(std::begin(edges), rand_between(0, edges.size()));

유효한 임의의 숫자를 선택하는 함수는 원하는대로 선택할 수 있지만 범위 [0 ; edges.size() - 1] edges 가 비어 있지 않으면 [0 ; edges.size() - 1] .

std::next 함수는 직접 할당을 허용하는 방식으로 std::advance 함수를 단순히 래핑합니다.


버킷이없는 엄격한 O (1) 솔루션 :

  1. 벡터에서 임의의 요소를 가져와야 할 때 벡터의 키 벡터를 유지하고 벡터에서 임의의 키를 선택하고지도에서 해당 값을 반환합니다. 일정 시간이 걸립니다.
  2. 지도에 키 - 값 쌍을 삽입 한 경우 해당 키가 이미 있는지 확인하고, 그렇지 않은 경우 해당 키를 키 벡터에 추가합니다. 일정 시간이 걸립니다
  3. 지도를 선택한 후에지도에서 요소를 제거하려면 선택한 키를 키 벡터의 back () 요소로 바꾸고 pop_back ()을 호출 한 다음 요소를지도에서 지우고 값을 반환합니다.-takes 일정 시간

그러나 제한이 있습니다 : 무작위 따기를 제외하고 맵에서 요소를 삭제하려면 키 벡터를 수정해야합니다. 이는 순진한 접근 방식으로 O (n)을 취합니다. 그러나 여전히 O (1) 성능을 얻는 방법이 있습니다 : 키가 키 벡터의 어디에 있는지 알려주는지도를 유지하고 스왑으로 업데이트하십시오 :)





prims-algorithm