STL set 컨테이너의 키 설정 문의 드립니다.
글쓴이: hahaite / 작성시간: 월, 2014/01/20 - 1:45오후
안녕하세요.
특정 조건을 만족하는 6x6 행렬 데이터를 map에 담아 관리하는 프로그램을 짜고 있는데요.
새로 입력하는 6x6 데이터가 중복이 아닌지 체크를 합니다.
이 때, map.begin() ~ map.end() 까지 iterator++ 로 검색하니 30초가 걸리더군요.
그래서 list로 바꿔봤더니 20초가 걸렸습니다.
중복검사를 어찌할까 고민하다가 6x6 행렬을 숫자화 시켜서 set에 때려 넣었더니 1초만에 끝~!! 오예~
문제는 아래처럼 set key를 생성하는 코드가 지저분해지더군요. (pair가 4개나...)
typedef unsigned long long ULL ; typedef pair<pair<pair<ULL, ULL>, pair<ULL, ULL> >, unsigned int > SetKey ;
게다가 6x6 이 아닌, 동적크기의 배열인 경우 크기를 알 수 없으니 위 키생성 코드를
적용하기 힘든...
지금 머릿속엔 set의 키값을 어떻게 생성할까로 꽉 차있는데요.
이 방법이 맞을까요?
아님, 데이터의 중복검사를 하는데 좀 더 효율적인 방법이 있을까요?
고수분들의 조언 부탁드립니다.
그럼, 즐거운 하루 보내세요.
Forums:
key 타입을 보고 추측컨데, 본래 행렬에는 대소
key 타입을 보고 추측컨데, 본래 행렬에는 대소 관계가 존재하지 않으니까 행렬의 각 요소들을 pair들에 적재해서 pair의 비교연산자가 적용되게 짜신거 같은데, 그냥 행렬을 위한 비교 연산자를 하나 정의하세요.
std::set은 비교 연산을 위한 functor를 지정할 수 있습니다.
대충 (예를 들어, 6x6행렬의 타입이 Matrix6x6이고, () 연산자로 요소에 접근할 수 있다고 하면)
이런식으로 정의해서 key로는 Matrix6x6을 그냥 그대로 주고 key_compare 로 CompareMatrix6x6ForSet 을 넘겨서 std::set<Matrix6x6, CompareMatrix6x6ForSet> 처럼 선언하면 됩니다.
행렬 크기가 바뀔 수 있다면 각 요소에 대해서 for loop를 돌면서 비교해주면 되고요.
수학적으로 < 라는 비교가 가능한가는 중요하지 않습니다. 행렬을 정렬시킬 수 있는 하나의 기준만 마련해주면 됩니다.
지금 중요한건 정렬 순서가 아니라 이진검색이 가능하게 정렬만 되어있으면 되는 것이므로 위 함수에서 && 대신 모두다 || 로 해도 정렬 순서가 좀 바뀔뿐 중복 유무를 검사하는데에는 문제가 되지 않습니다.
더나아가서 이경우에는 차라리 set보다는 해쉬함수를 이용하는 unordered_set을 이용하는게 좋을 듯합니다. 단 행렬 크기가 너무 큰 경우(아마도 요소가 수천개 이상)에는 해쉬함수 자체 오버해드가 커질 수 있으므로 그 경우에는 벤치마킹을 해서 비교해보고 결정해야 할 겁니다.
친절한 가이드 감사합니다.
제 공부의 부족함이었네요.
책보고 예제 만들어보고 해서 잘 해결하였습니다.
상세한 조언 정말 감사합니다. _(__)_
^^
CompareMatrix6x6ForSet
CompareMatrix6x6ForSet functor가 잘못 디자인되었습니다.
작성하신 keycomp 함수를 사용할 경우 x = (0,1)(1,0), y = (1,0)(0,1) 일 때 !(x < y) && !(y < x)를 만족하게 되어 두 행렬이 equivalent하다고 판단, 두번째 행렬이 set에 추가되지 않게 됩니다.
compare 함수를 lexicographical compare로 작성해야 제대로 동작할 것입니다.
&&나 ||나 마찬가지일거라고 생각했는데, &&로
&&나 ||나 마찬가지일거라고 생각했는데, &&로 비교하면 말씀하신 문제가 생기네요. ||로 묶어주면 괜찮아 보이는데 맞나요?
그냥 행렬을 하나의 수열로 보고서(예시라면, x= 110, y=1001) 맨 앞자리부터 비교한다고 생각하면 되겠네요.
|| 로 묶어줘도 마찬가지입니다. ||로 할 경우
|| 로 묶어줘도 마찬가지입니다. ||로 할 경우 (x < y) && (y < x)가 되어 strict weak ordering을 만족하지 않아 key compare로 사용할 수 없게 됩니다.
lexicographical compare가 구현이 생각보다 좀 많이 귀찮아서 std::array, std::pair, std::tuple 등이 operator<로 지원됩니다.
이렇게 처리하였습니다.
질문자입니다.
일단, 컨테이너에 배열을 직접 삽입할 수는 없는 듯 합니다.
이래저래 시도하다가 아래 글을 읽고 구조체 안에 변수로 설정하였습니다.
http://kuaaan.tistory.com/167 : ( STL의 원소로 배열(Array)을 사용할 수 없는 이유)
for문을 사용하여 값 하나하나 크기를 비교하였습니다.
memcmp() 를 써서 깔끔하게 처리하나 했더니,
배열의 값이 음수일 땐 memcmp() 가 음수가 크다고 판단하더군요.
아래와 같이 작성하여 테스트 하였습니다.
^^
c++11을 지원하는 컴파일러를 사용 중이시면
memcmp는 메모리의 내용을 byte by byte로 비교하므로 현재의 경우에는 사용하실 수 없습니다.
c++11을 지원하는 컴파일러를 사용 중이시면 std::array를, 아니라면 boost::array를 사용하시는 것이 더 나아보입니다.
댓글 달기