C++ map의 find 함수는 연관 컨테이너니깐 less 함수를 이용해서 객체를 일일이 비교하면서 찾으려는 객체가 있는지를 알아보는게 맞나요?
이러면 분명히 선형적(O(N))으로 시간이 걸리니깐 key-value 저장을 하면서 빠른 탐색이 필요하면 map이 아닌 해시 테이블을 쓰는건가요?
맵은 검색시 로그스케일이고 이게 장점입니다만 이렇게 로그스케일 검색을 구현하기 위해(바이너리 트리로 정렬하기 위해) 데이타의 삽입과 삭제에 비용이 비쌉니다. 이게 단점이예요.
해쉬테이블을 쓰면 정렬을 하지 않는 장점이 있고 해시함수로 검색과 삽입을 하기 때문에 복잡도가 항상 상수 복잡도 입니다. 이 장점을 누리기 위해 해쉬테이블을 사용한다고 알고 있습니다. 그런데 이 상수값이 무시못하기 때문에 데이타 사이즈가 어느정도 클 때라야 맵과 비교해서 장점이 나타납니다. 데이타가 작으면 상수 시간보다 싼 값으로 맵을 사용할 수 있거든요..
저도 최근에 STL 을 보고 있는 중이라 답변해봅니다. C++11 이 아니면 아직은 부스트의 해시테이블을 많이 쓰는 것 같습니다. 저는 사용해본 적 없지만요..
Thanks for being one of those who care for people and mankind.
I'd like to be one of those as well.
> "이 상수값이 무시못하기 때문에 데이타 사이즈가 어느정도 클 때라야 맵과 비교해서 장점이 나타납니다."
실제로 테스트를 해보면 원소 수가 20~30개 수준에서도 gcc나 msvc의 구현에서 모두 해쉬 쪽이 더 빠릅니다.
원소 수가 몇 개 수준이면 그냥 벡터나 배열을 스캔하는 쪽이 차라리 빠릅니다.
원소 수가 아주 많아지면 해쉬가 트리보다 메모리를 더 먹습니다. 고려에 넣어야 할 수준입니다.
먼저 종종 간과되는 것중에 하나로 해쉬 함수의 오버해드가 있습니다.
이는 map이 대소 관계만 비교하면 되는 반면에 unordered_map은 무조건 키를 전부 읽어서 해쉬값을 계산해야 하기 때문입니다.
예를 들어 키값으로 문자열 "aaa"와 "bbb"가 있을 때, map은 처음 한글자씩만 비교해봐도 바로 결과가 나오지만,
일반적으로 해쉬 함수는 두 문자열을 전부 읽어서 각각의 해쉬값을 계산해야 하기 때문에 특히 키값으로 긴 문자열이 많이 들어가는 경우에는 map에 비해서 해쉬가 많이 느려질 수 있습니다.
효율적인 해쉬 함수의 구현도 중요한 문제입니다.
그리고 map은 upper_bound나 lower_bound와 같은 정렬된 데이터의 '경계 검색'이 가능하다는 장점이 있습니다.
이는 정렬된 배열이나 벡터도 가능하지만 연관 컨테이너중에서는 map만이 가능합니다.
정말 잘 읽었습니다!
아, 그리고 해시 테이블에서 find를 할 때의 과정이 제가 알고 있는게 맞나요?
저는 해시 테이블에 삽입할 때 <키, 밸류>로 넣으면 이게 해시 테이블의 해시 펑션에 의해서 <해싱된 키, 밸류>의 형식으로 테이블에 들어가서
인덱스는 "해싱된 키"가 되는 것이고 find를 할 때는 해시 테이블이 키를 인자로 받아들여서 해시 펑션으로 계산한 키의 해싱값을 기준으로 find를 하는걸로 아는데요.
그런데, xylosper님이 적어주신 "반면에 unordered_map은 무조건 키를 전부 읽어서 해쉬값을 계산해야 하기 때문입니다."라는 말이 잘 이해가 가질 않네요ㅠ
해시된 값이 테이블의 index로 들어가는게 아니었나요? 아니면 제가 말을 잘못 이해한건지...
아니면 제가 해시 테이블의 삽입/검색 로직을 잘못 알고 있는건지...ㅠ
키를 전부 읽는다는게 오해의 소지가 있네요.
컨테이너의 모든 키를 읽는다는 뜻이 아니라, 해당 키값(배열)을 전부 읽어야 한다는 뜻이었습니다.
예를 들어 "aaa" 이라는 키가 map과 unordered_map에 들어있다고 할 때, "bbb"라는 키를 삽입하려고 합니다.
이때 map은 "aaa"의 첫글자와 한번만 비교하면 삽입할 위치를 찾을 수 있습니다.
반면에 unordered_map은 먼저 "bbb"의 세글자를 전부 읽어와서 해쉬값을 생성해야 합니다.
따라서 긴 문자열을 키로 가지는 매우 큰 컨테이너를 생성할 때, map은 경우에 따라서는 문자열을 끝까지 안읽어도 (그리고 간단한 비교 연산만으로) 삽입 위치를 찾을수 있지만, unordered_map의 경우는 매번 해쉬함수를 호출하여 해쉬값을 계산하여 삽입할 위치를 정해야 합니다.
따라서 대량의 문자열 키를 삽입/삭제하는 경우에는 map이 unordered_map보다 훨씬 빠른 경우도 있습니다.
해시는 한 번만 계산하면 됩니다. 반면에 트리는 삽입 위치를 찾을 때 까지 여러 번 (로그 N 스케일) 비교를 해야합니다.
고로 키의 일부만 읽어도 되는 이점은 사실 그리 크지 않습니다.
효율적인 해시 함수가 중요하기는 하지만 말씀하신 오버 헤드는 실제 사용시에 고려해야할 사항은 아닌 것 같습니다.
하나 삽입할때 한번이고, 10개 삽입하려면 10번 계산해야되고, 1000개 삽입하려면 1000번 계산해야됩니다.
문자열이 길어지면 해쉬 계산 자체가 오래걸리기 때문에 그게 상수 시간에 끝난다고 해도 짧은 시간(문자열 대소 비교)에 대한 로그 스케일이 더 빠를 수 있습니다.
STL은 아니지만, Qt의 연관 컨테이너인 QMap과 QHash를 대상으로 벤치마킹한 결과,
문자열이 짧은 경우는 QHash가, 문자열이 긴경우에는 QMap이 각각 '훨씬' 빠르다는 결과를 보았습니다.
map은 정렬된 연관 컨테이너입니다. 이진탐색을 하기
map은 정렬된 연관 컨테이너입니다. 이진탐색을 하기 때문에 탐색에 걸리는 시간은 로그스케일입니다.
맵은 로그스케일이고,해쉬테이블을 쓰면 정렬을 하지
맵은 검색시 로그스케일이고 이게 장점입니다만 이렇게 로그스케일 검색을 구현하기 위해(바이너리 트리로 정렬하기 위해) 데이타의 삽입과 삭제에 비용이 비쌉니다. 이게 단점이예요.
해쉬테이블을 쓰면 정렬을 하지 않는 장점이 있고 해시함수로 검색과 삽입을 하기 때문에 복잡도가 항상 상수 복잡도 입니다. 이 장점을 누리기 위해 해쉬테이블을 사용한다고 알고 있습니다. 그런데 이 상수값이 무시못하기 때문에 데이타 사이즈가 어느정도 클 때라야 맵과 비교해서 장점이 나타납니다. 데이타가 작으면 상수 시간보다 싼 값으로 맵을 사용할 수 있거든요..
저도 최근에 STL 을 보고 있는 중이라 답변해봅니다. C++11 이 아니면 아직은 부스트의 해시테이블을 많이 쓰는 것 같습니다. 저는 사용해본 적 없지만요..
Thanks for being one of those who care for people and mankind.
I'd like to be one of those as well.
> "이 상수값이 무시못하기 때문에 데이타 사이즈가
> "이 상수값이 무시못하기 때문에 데이타 사이즈가 어느정도 클 때라야 맵과 비교해서 장점이 나타납니다."
실제로 테스트를 해보면 원소 수가 20~30개 수준에서도 gcc나 msvc의 구현에서 모두 해쉬 쪽이 더 빠릅니다.
원소 수가 몇 개 수준이면 그냥 벡터나 배열을 스캔하는 쪽이 차라리 빠릅니다.
원소 수가 아주 많아지면 해쉬가 트리보다 메모리를 더 먹습니다. 고려에 넣어야 할 수준입니다.
위쪽에 두분이 좋은글 적어주셔서, 언급되지 않은것중에
위쪽에 두분이 좋은글 적어주셔서, 언급되지 않은것중에 제가 알고 있는걸 적어보겠습니다.
먼저 종종 간과되는 것중에 하나로 해쉬 함수의 오버해드가 있습니다.
이는 map이 대소 관계만 비교하면 되는 반면에 unordered_map은 무조건 키를 전부 읽어서 해쉬값을 계산해야 하기 때문입니다.
예를 들어 키값으로 문자열 "aaa"와 "bbb"가 있을 때, map은 처음 한글자씩만 비교해봐도 바로 결과가 나오지만,
일반적으로 해쉬 함수는 두 문자열을 전부 읽어서 각각의 해쉬값을 계산해야 하기 때문에 특히 키값으로 긴 문자열이 많이 들어가는 경우에는 map에 비해서 해쉬가 많이 느려질 수 있습니다.
효율적인 해쉬 함수의 구현도 중요한 문제입니다.
그리고 map은 upper_bound나 lower_bound와 같은 정렬된 데이터의 '경계 검색'이 가능하다는 장점이 있습니다.
이는 정렬된 배열이나 벡터도 가능하지만 연관 컨테이너중에서는 map만이 가능합니다.
감사합니다~!
정말 잘 읽었습니다!
아, 그리고 해시 테이블에서 find를 할 때의 과정이 제가 알고 있는게 맞나요?
저는 해시 테이블에 삽입할 때 <키, 밸류>로 넣으면 이게 해시 테이블의 해시 펑션에 의해서 <해싱된 키, 밸류>의 형식으로 테이블에 들어가서
인덱스는 "해싱된 키"가 되는 것이고 find를 할 때는 해시 테이블이 키를 인자로 받아들여서 해시 펑션으로 계산한 키의 해싱값을 기준으로 find를 하는걸로 아는데요.
그런데, xylosper님이 적어주신 "반면에 unordered_map은 무조건 키를 전부 읽어서 해쉬값을 계산해야 하기 때문입니다."라는 말이 잘 이해가 가질 않네요ㅠ
해시된 값이 테이블의 index로 들어가는게 아니었나요? 아니면 제가 말을 잘못 이해한건지...
아니면 제가 해시 테이블의 삽입/검색 로직을 잘못 알고 있는건지...ㅠ
키를 전부 읽는다는게 오해의 소지가
키를 전부 읽는다는게 오해의 소지가 있네요.
컨테이너의 모든 키를 읽는다는 뜻이 아니라, 해당 키값(배열)을 전부 읽어야 한다는 뜻이었습니다.
예를 들어 "aaa" 이라는 키가 map과 unordered_map에 들어있다고 할 때, "bbb"라는 키를 삽입하려고 합니다.
이때 map은 "aaa"의 첫글자와 한번만 비교하면 삽입할 위치를 찾을 수 있습니다.
반면에 unordered_map은 먼저 "bbb"의 세글자를 전부 읽어와서 해쉬값을 생성해야 합니다.
따라서 긴 문자열을 키로 가지는 매우 큰 컨테이너를 생성할 때, map은 경우에 따라서는 문자열을 끝까지 안읽어도 (그리고 간단한 비교 연산만으로) 삽입 위치를 찾을수 있지만, unordered_map의 경우는 매번 해쉬함수를 호출하여 해쉬값을 계산하여 삽입할 위치를 정해야 합니다.
따라서 대량의 문자열 키를 삽입/삭제하는 경우에는 map이 unordered_map보다 훨씬 빠른 경우도 있습니다.
해시는 한 번만 계산하면 됩니다. 반면에 트리는 삽입
해시는 한 번만 계산하면 됩니다. 반면에 트리는 삽입 위치를 찾을 때 까지 여러 번 (로그 N 스케일) 비교를 해야합니다.
고로 키의 일부만 읽어도 되는 이점은 사실 그리 크지 않습니다.
효율적인 해시 함수가 중요하기는 하지만 말씀하신 오버 헤드는 실제 사용시에 고려해야할 사항은 아닌 것 같습니다.
하나 삽입할때 한번이고, 10개 삽입하려면 10번
하나 삽입할때 한번이고, 10개 삽입하려면 10번 계산해야되고, 1000개 삽입하려면 1000번 계산해야됩니다.
문자열이 길어지면 해쉬 계산 자체가 오래걸리기 때문에 그게 상수 시간에 끝난다고 해도 짧은 시간(문자열 대소 비교)에 대한 로그 스케일이 더 빠를 수 있습니다.
STL은 아니지만, Qt의 연관 컨테이너인 QMap과 QHash를 대상으로 벤치마킹한 결과,
문자열이 짧은 경우는 QHash가, 문자열이 긴경우에는 QMap이 각각 '훨씬' 빠르다는 결과를 보았습니다.
결론은
키값의 길이가 짧으면 해시 테이블을 써도 되는데 키값의 길이가 길면 맵을 쓰는게 낫다는건가요?
아뇨 생각보다 고려해야할 사항이 많다는 뜻입니다.
아뇨 생각보다 고려해야할 사항이 많다는 뜻입니다. '길다'는 것도 그 기준이 애매모호하니까요.
수요가 예측하기 어렵다면 일반적인 논리를 따라가는게 좋겠지만, 수요가 예측가능하다면 실제로 벤치마킹을 해보고 빠른쪽을 선택하는게 좋을 것입니다.
댓글 달기