STL set 컨테이너의 키 설정 문의 드립니다.

hahaite의 이미지

안녕하세요.

특정 조건을 만족하는 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의 키값을 어떻게 생성할까로 꽉 차있는데요.
이 방법이 맞을까요?

아님, 데이터의 중복검사를 하는데 좀 더 효율적인 방법이 있을까요?

고수분들의 조언 부탁드립니다.

그럼, 즐거운 하루 보내세요.

klyx의 이미지

key 타입을 보고 추측컨데, 본래 행렬에는 대소 관계가 존재하지 않으니까 행렬의 각 요소들을 pair들에 적재해서 pair의 비교연산자가 적용되게 짜신거 같은데, 그냥 행렬을 위한 비교 연산자를 하나 정의하세요.
std::set은 비교 연산을 위한 functor를 지정할 수 있습니다.
대충 (예를 들어, 6x6행렬의 타입이 Matrix6x6이고, () 연산자로 요소에 접근할 수 있다고 하면)

struct CompareMatrix6x6ForSet {
   bool operator() const (const Matrix6x6 &lhs, const Matrix6x6 &rhs) {
      return lhs(0, 0) < rhs(0, 0) && lhs(0, 1) < rhs(0, 1) && lhs(0, 2) < rhs(0, 2)
         ... && lhs(5, 3) < rhs(5, 3) && lhs(5, 4) < rhs(5, 4) && lhs(5, 5) < rhs(5, 5);
   }
}

이런식으로 정의해서 key로는 Matrix6x6을 그냥 그대로 주고 key_compare 로 CompareMatrix6x6ForSet 을 넘겨서 std::set<Matrix6x6, CompareMatrix6x6ForSet> 처럼 선언하면 됩니다.
행렬 크기가 바뀔 수 있다면 각 요소에 대해서 for loop를 돌면서 비교해주면 되고요.
수학적으로 < 라는 비교가 가능한가는 중요하지 않습니다. 행렬을 정렬시킬 수 있는 하나의 기준만 마련해주면 됩니다.
지금 중요한건 정렬 순서가 아니라 이진검색이 가능하게 정렬만 되어있으면 되는 것이므로 위 함수에서 && 대신 모두다 || 로 해도 정렬 순서가 좀 바뀔뿐 중복 유무를 검사하는데에는 문제가 되지 않습니다.
더나아가서 이경우에는 차라리 set보다는 해쉬함수를 이용하는 unordered_set을 이용하는게 좋을 듯합니다. 단 행렬 크기가 너무 큰 경우(아마도 요소가 수천개 이상)에는 해쉬함수 자체 오버해드가 커질 수 있으므로 그 경우에는 벤치마킹을 해서 비교해보고 결정해야 할 겁니다.

hahaite의 이미지

제 공부의 부족함이었네요.

책보고 예제 만들어보고 해서 잘 해결하였습니다.

상세한 조언 정말 감사합니다. _(__)_

^^

kukyakya의 이미지

CompareMatrix6x6ForSet functor가 잘못 디자인되었습니다.

작성하신 keycomp 함수를 사용할 경우 x = (0,1)(1,0), y = (1,0)(0,1) 일 때 !(x < y) && !(y < x)를 만족하게 되어 두 행렬이 equivalent하다고 판단, 두번째 행렬이 set에 추가되지 않게 됩니다.

compare 함수를 lexicographical compare로 작성해야 제대로 동작할 것입니다.

klyx의 이미지

&&나 ||나 마찬가지일거라고 생각했는데, &&로 비교하면 말씀하신 문제가 생기네요. ||로 묶어주면 괜찮아 보이는데 맞나요?
그냥 행렬을 하나의 수열로 보고서(예시라면, x= 110, y=1001) 맨 앞자리부터 비교한다고 생각하면 되겠네요.

kukyakya의 이미지

|| 로 묶어줘도 마찬가지입니다. ||로 할 경우 (x < y) && (y < x)가 되어 strict weak ordering을 만족하지 않아 key compare로 사용할 수 없게 됩니다.

lexicographical compare가 구현이 생각보다 좀 많이 귀찮아서 std::array, std::pair, std::tuple 등이 operator<로 지원됩니다.

hahaite의 이미지

질문자입니다.

일단, 컨테이너에 배열을 직접 삽입할 수는 없는 듯 합니다.
이래저래 시도하다가 아래 글을 읽고 구조체 안에 변수로 설정하였습니다.

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 ;
}

^^

kukyakya의 이미지

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;
  }
}

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.