unordered_map에 삽입하는 데 너무 많은 시간이 걸립니다.

Question

파일 (약 500,000 개)에서 숫자를 읽고 데이터 구조에 삽입하는 프로그램을 작성했습니다. 숫자는 별개입니다. 내가. std::make_pair(myNumber, emptyStruct))를 사용하여 다른 구조체 (와

을 unordered_map에 번호를 삽입하는거야 그리고 모든 숫자의 삽입 후, 나는 단지 몇 백의 배를 검색하는 데 사용하고 있습니다. 나는 때까지 DS를 삭제하지 프로그래밍이 끝났습니다.

프로파일 링이 끝나면 삽입 작업이 실행 시간의 약 50 %를 차지한다는 것을 알았습니다 (삽입과 같은 횟수만큼 실행되는 다른 코드도 있지만, t 시간이 많이 걸릴 것입니다.)

아마도 크기 조정에 시간이 걸릴 것으로 생각했기 때문에 500,000으로 예약 기능을 사용했지만 결과는 여전히 동일합니다.

내가 아는 한,이 DS는 O (1) 삽입 및 검색이되어야하며 (트레이드 오프는 대용량 메모리이므로) 삽입하기에 너무 많은 시간이 걸리는 이유는 알 수 없습니다. 결과를 어떻게 개선 할 수 있습니까?

Answer 1

값을 사용하지 않고 존재만을 검색하기 때문에 std :: unordered_set을 사용하십시오. 더미의 값을 만들어지도의 모든 키와 함께 갈 때 원하는 것을합니다.

먼저 모든 사람이 말한 것을 다시 반복하고 싶습니다. 500,000 개의 항목을 삽입하여 수백 번 사용하면 상당한 시간이 걸릴 것이므로 가능한 한 그렇게 할 수 없다면 실제로 피할 수는 없습니다. 그것을 돌아서 - 당신이 찾고있는 것들의 세트를 만들고 그 다음 500,000 번 찾으십시오.

모든 말했다, 내가 계정으로 해시 테이블의 성격 복용하여 테스트 응용 프로그램에서 50 개 항목의 삽입에 대한 몇 가지 개선을 얻을 수있었습니다 :

:

이 http://en.cppreference.com/w/cpp/container/unordered_map을 검토하기를, 나는이 발견

[삽입] 복잡성 : 보통의 경우 : O (1), 최악의 경우 O (크기()) 기본적

, unordered_map도 용기 1.0 max_load_factor있다.

500000 개 항목의 공간을 예약하면 500000 개의 버킷이 생성됩니다. 5 만개의 버킷에 500,000 개의 데이터를 넣으면 충돌이 많이 발생할 것입니다. 여분의 공간을 확보했으며 더 빨랐습니다.

속도가 정말로 필요하고 오류가 발생하면 블룸 필터를 살펴보십시오.

Answer 2

정렬되지 않은 맵은 해시 테이블로 구현됩니다. 일정한 삽입 시간을 상각했습니다. 지도에 크기를 할당하면 너무 많은 도움이되지 않지만 도움이됩니다. 당신이 그것을 삽입하는 측면에서 할 수있는 일은별로 없습니다.

즉, 시간을 절약 할 수는 있지만 한계가있을 수 있습니다. 예를 들어 벡터에 삽입하는 것은 약간 빠르지 만 상각 시간도 상각됩니다. 따라서 검색 비용으로 삽입에 몇 초를 면도 할 것입니다.

데이터베이스가 도움이되는 곳입니다. 대신 sqlite 데이터베이스에 데이터가 있다고 가정 해보십시오. 데이터베이스를 만들고 검색 값을 기본 키로 사용하여 테이블을 만들고 다른 특성으로 데이터 값을 한 번 테이블에 삽입합니다. 이제 프로그램은 데이터베이스를 실행하고 쿼리합니다. 최소한 필요한 것만 읽습니다. 이 경우 sqlite 데이터베이스는 사용중인 정렬되지 않은 맵의 역할을합니다.