1 백만 개의 데이터에 대한 C++ 해시 테이블

Question

1 백만 개의 데이터 개체가 있고 이러한 개체를 구성하고 어떤 개체가 가장 많이 반복되는지 계산해야하며 해시 테이블을 사용하여이 작업을 수행 할 수있는 방법을 나열해야합니다.

Answer 1

모두가 반복하는 작업에 따라 다릅니다.

1. 벡터
   장점 : 빠른 인덱스에 의해 액세스 요소에 다음 데이터 구조 및 자신의 장점/단점 몇입니다. O (1) 시간에 완료됩니다.
   단점 : 삽입 된 객체 뒤에 삽입 된 모든 객체를 이동해야하므로 삽입 속도가 느립니다. 이것은 O (n) 시간에 수행됩니다. 데이터가 뒤에서 푸시 되더라도 O (1)에서 실행되는 메모리를 다시 할당해야하므로 벡터 삽입이 느려지지만이 경우 상수는 상당히 큽니다.

2. 목록
   전문가 : 데이터를 삽입하는 위치에 관계없이 목록을 매우 빠르게 삽입 할 수 있습니다. O (1) 시간에 완료됩니다.
   단점 : 다음 요소가 포인터에 의해 액세스 될 때 데이터에 액세스하는 데 필요한 시간이 선형이므로 원하는 값에 도달 할 때까지 모든 것을 반복해야합니다. 이것은 O (n)에서 수행됩니다.

3. 지도 및 순서가 지정되지 않은지도
   전문가 : 요소에 액세스하기 위해 해시 테이블을 사용하므로 액세스 시간이 O (1)와 O (n) 사이에서 다릅니다. 단점 : 재연해야 할 수도 있습니다. 매우 느립니다.

매우 많은 요소에 액세스 할 때 벡터를 사용하는 것이 더 빠릅니다. 더 나은 데이터 구조를 제안 할 수 있도록 알고리즘을 보여줄 수 있습니까?

그렇지 않은 경우 Mark Allen Weiss가 C++에서 데이터 구조 및 알고리즘 분석을 읽는 것이 좋습니다. 그것은 당신이 찾고있는 것에 대한 완전한 가이드를 제공합니다.