unordered_set 채우기가 너무 느림

Question

우리는 주어진 3D 메시를 가지고 있으며 동일한 꼭지점을 제거하려고합니다. 이를 위해 정점 좌표와 해당 법선이 포함 된 자체 정의 구조체를 사용합니다.

데이터로 버텍스를 채우면 unordered_set에 추가되어 중복을 제거합니다.

struct hashVertice 
    { 
     size_t operator() (const vertice& vert) const 
     { 
      return(7*vert.p1 + 13*vert.p2 + 11*vert.p3); 
     } 
    }; 

    std::unordered_set<vertice,hashVertice> verticesSet; 

    vertice vert; 

    while(i<(scene->mMeshes[0]->mNumVertices)){ 

      vert.p1 = (float)scene->mMeshes[0]->mVertices[i].x; 
      vert.p2 = (float)scene->mMeshes[0]->mVertices[i].y; 
      vert.p3 = (float)scene->mMeshes[0]->mVertices[i].z; 

      vert.n1 = (float)scene->mMeshes[0]->mNormals[i].x; 
      vert.n2 = (float)scene->mMeshes[0]->mNormals[i].y; 
      vert.n3 = (float)scene->mMeshes[0]->mNormals[i].z; 

      verticesSet.insert(vert); 

      i = i+1; 
    } 

3.000.000 정점과 같은 데이터 양에는 너무 느리다는 것을 발견했습니다. 15 분간의 실행 후에도 프로그램이 끝나지 않았습니다. 우리가 보지 못하는 병목 현상이 있습니까? 아니면 그러한 작업을 위해 다른 데이터 구조가 더 좋습니까?

Answer 1

루프에서 verticesSet.insert(vert); 만 제거하면 어떻게됩니까?

(예상 한대로) 속도가 크게 향상되는 경우 병목 현상은 해시 테이블 인 std::unordered_set의 헛점이며 해시 테이블의 주요 성능 문제는 과도한 해시가있는 경우입니다 충돌. p1, p2 및 p3이 작은 경우 현재 구현에서

, 별개의 해시 코드의 수는 작은 것 (정수로하면 "붕괴"플로트부터)와 충돌이 많이있을 것입니다.

위의 가정이 사실로 밝혀지면 해시 함수를 다르게 구현하려고합니다 (예 : 훨씬 큰 계수로 곱하기).

---

이외의 다른 코드는 이미 제안했듯이 코드를 프로파일하십시오.

Answer 2

병목 현상이있는 경우 어떤 종류의 타이밍 조치도 포함되어 있지 않으므로 확실히 병목 현상이 보이지 않습니다.

프로파일 러를 사용하거나 수동으로 알고리즘 타이밍을 측정하십시오. 이렇게하면 병목 현상이있는 경우 병목 현상을 찾을 수 있습니다.

올바른 방법입니다. 내 경험에 비추어 볼 때 실제로 프로그램에서 시간을 측정하는 대신 눈 검사를 통해 병목 현상을 발견 할 수있는 StackOverflow 사용자는 최적화에서 실패한 시도의 가장 일반적인 원인입니다.

Answer 3

해싱 부동 소수점은 까다로울 수 있습니다. 특히 해시 루틴은 해시를 부동 소수점 값으로 계산하고 은이를 부호없는 정수 유형으로 변환합니다. 버텍스가 작 으면 문제가 심각합니다. 모든 버텍스 이 [0...1.0) 범위에있는 경우 해시 함수 은 13보다 큰 값을 반환하지 않습니다. 부호없는 정수로, 이는 최대 13 개의 다른 해시 코드 여야합니다.

해시 부동 소수점을 사용하는 일반적인 방법은 이진 코드 을 해싱하여 특수한 경우를 먼저 확인하는 것입니다. (0.0 및 -0.0 다른 바이너리 이미지를 가지고 있지만, 동일한 해시해야합니다. 그리고 당신이 NaN들과 함께 무엇을 오픈 질문 입니다.)이 특히 간단 float를 들어, 보통 int과 같은 크기를 가지고 있기 때문에, 그리고 당신은 reinterpret_cast 할 수 있습니다

내가 아는

size_t 
hash(float f) 
{ 
    assert(/* not a NaN */); 
    return f == 0.0 ? 0.0 : reinterpret_cast(unsigned&)(f); 
} 

, 공식적으로,이 정의되지 않은 동작입니다. 그러나 float와 int가 같은 크기이고 부호가없는 경우 표현 (대부분의 범용 컴퓨터의 경우는 )이 잘못된 경우이 컴파일러는 의도적으로 무뚝뚝합니다.

그런 다음 결합 알고리즘을 사용하여 세 가지 결과를 병합합니다. 당신이 사용하는 것은 다른 어떤 것보다 우수합니다 (이 경우 —입니다. 은 좋은 일반 알고리즘이 아닙니다).

내가 코멘트 중 일부는 프로파일 주장 (이 일반적으로 좋은 충고입니다) 당신이 3 개 백만 값 15분 을 복용하는 경우, 동안, 문제는 정말 단지 가난한 해시 기능이 될 수 있음을 추가 할 수 있습니다 이로 인해 많은 충돌이 발생합니다. 그 밖의 것은 없습니다 성능 저하를 일으 킵니다.그리고 내부 구현 인 std::unordered_set에 익숙하지 않으면 일반적으로 프로파일 러 출력에 많은 정보가 제공되지 않습니다. 한편, std::unordered_set은 bucket_count 및 bucket_size과 같은 함수 을 가지므로 해시 함수의 품질을 으로 분석 할 수 있습니다. 귀하의 경우에 30000 개의 항목이 포함 된 unordered_set을 만들 수없는 경우 처음으로 단계는 훨씬 더 작은 단계를 만들고이 함수를 사용하여 해시 코드의 품질을 평가해야합니다.