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() 가 음수가 크다고 판단하더군요.
아래와 같이 작성하여 테스트 하였습니다.
#include <cstdio> #include <set> using namespace std ; #define ARRAY_ROW 2 #define ARRAY_COL 3 typedef int (Array)[ARRAY_ROW][ARRAY_COL] ; struct Data { static int row ; static int col ; Array array ; }; int Data::row = ARRAY_ROW ; int Data::col = ARRAY_COL ; struct DataCompare { bool operator() (const Data& lhs, const Data& rhs) const { // memcmp를 쓰면 안된다. 음수값의 비교가 안된다. // int ret = memcmp(&lhs.array, &rhs.array, sizeof(lhs.array)) ; for(int ii = 0; ii < lhs.row; ii++) { for(int jj = 0; jj < lhs.col; jj++) { if( lhs.array[ii][jj] < rhs.array[ii][jj]) return 1 ; else if( lhs.array[ii][jj] > rhs.array[ii][jj]) return 0 ; } } return 0 ; } }; int main() { set<Data, DataCompare> setData ; set<Data, DataCompare>::const_iterator setDataIter ; Data data1 = {{{8,7,0}, {8,1,3}}}; setData.insert(data1) ; Data data2 = {{{2,3,4}, {4,5,7}}}; setData.insert(data2) ; Data data3 = {{{2,3,4}, {4,5,6}}}; setData.insert(data3) ; Data data4 = {{{-1,3,4}, {4,-1,6}}}; setData.insert(data4) ; Data data5 = {{{2,3,4}, {4,5,6}}}; setData.insert(data5) ; Data data6 = {{{-1,3,4}, {4,1,6}}}; setData.insert(data6) ; setDataIter = setData.begin() ; for(; setDataIter != setData.end(); setDataIter++) { printf("================\n") ; for(int ii = 0; ii < 2; ii++) { for(int jj = 0; jj < 3; jj++) printf("%d ", setDataIter->array[ii][jj]) ; printf("\n") ; } } Data data7 = {{{-1,3,4}, {4,-1,6}}}; setDataIter = setData.find(data7) ; if(setDataIter != setData.end()) { printf("find~!!\n") ; } Data data8 = {{{0,0,4}, {4,-1,6}}}; setDataIter = setData.find(data8) ; if(setDataIter == setData.end()) { printf("cannot Find~!!\n") ; } return 1 ; }^^
c++11을 지원하는 컴파일러를 사용 중이시면
memcmp는 메모리의 내용을 byte by byte로 비교하므로 현재의 경우에는 사용하실 수 없습니다.
c++11을 지원하는 컴파일러를 사용 중이시면 std::array를, 아니라면 boost::array를 사용하시는 것이 더 나아보입니다.
#include <iostream> #include <set> #include <array> // #include <boost/array.hpp> // If the compiler does not support c++11 #define ROW 2 #define COL 3 typedef std::array<std::array<int, COL>, ROW> matrix; // typedef boost::array<boost::array<int, COL>, ROW> matrix; int main() { std::set<matrix> set_of_matrix; matrix m1 = {{{8,7,0}, {8,1,3}}}; matrix m2 = {{{2,3,4}, {4,5,7}}}; matrix m3 = {{{2,3,4}, {4,5,6}}}; matrix m4 = {{{-1,3,4}, {4,-1,6}}}; matrix m5 = {{{2,3,4}, {4,5,6}}}; // m5 == m3 matrix m6 = {{{-1,3,4}, {4,1,6}}}; set_of_matrix.insert(m1); set_of_matrix.insert(m2); set_of_matrix.insert(m3); set_of_matrix.insert(m4); set_of_matrix.insert(m5); // will not be inserted set_of_matrix.insert(m6); std::cout << "set_of_matrix.size() = " << set_of_matrix.size() << std::endl; matrix m7 = {{{-1,3,4}, {4,-1,6}}}; if(set_of_matrix.find(m7) != set_of_matrix.end()) { std::cout << "Found m7 as expected" << std::endl; } matrix m8 = {{{0,0,4}, {4,-1,6}}}; if(set_of_matrix.find(m8) == set_of_matrix.end()) { std::cout << "m8 not found as expected" << std::endl; } }댓글 달기