현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

해쉬 테이블간의 제일 빠른 교집합 알고리즘을 알고 싶습니다..

kleinstein의 이미지
글쓴이: kleinstein / 작성시간: 수, 2006/11/15 - 10:54오후

2개의 덩치가 큰 그러나 크기가 같은(백만개) multimap A와 B가 있는데요..

각각의 key 값에는 임의의 double 값이 들어 있고 value 값에는 int 값이 들어 있습니다..

int값으로는 1에서 1,000,000 까지의 값만이 들어있구요..

물론 두개의 멀티맵에서 key값이 서로 다른 의미를 지닌 double값이기때문에 각각 서로 정렬되어 있어서 value값으로 들어있는 int값들은 뒤죽박죽으로 섞여 있습니다.

음.. 그림으로 그려보면..

A
key : 0.2 0.7 0.95 0.99 1.45 1.68 ...
value: 5 103 88 1 15 7 ...

B
key : 11.2 17.7 20.95 21.99 22.99 31.68 ...
value: 405 109 5 1 105 7 ...

이렇게 되어 있습니다..(위에서 잠깐 언급한것 처럼 A와 B에서 각각의 원소갯수는 똑같고 value값도 동일한 범위에서 나온 정수입니다.)

그리고 찾아야 할 교집합은
A의 1번째부터 3000번째까지의 value값과
B의 10000번째부터 20000번째까지의 vaule값을 비교해서 두군데에 동시에 들어있는 value값들의 교집합을 구해야 합니다.

이런 경우에 가장빨리 교집합을 구할수 있는 알고리즘은 어떤게 있을까요?

Forums: 
프로그래밍 QnA
jiee의 이미지

글쓴이: jiee / 작성시간: 목, 2006/11/16 - 12:18오전

C++를 사용한다면, 다음과 같은 순서로 진행 할 겁니다.

1. multimap A, B에서 교집합을 찾고자 하는 범위의 value값들을 multiset으로 복사함.
2. set_intersection알고리즘으로 교집합구함.

C++이 아니라면, 위와 같은 작업을 직접해주면 될 듯합니다.

ps. set_intersection은 algorithm헤더파일에 작성된 거 보면 간단합니다.

토나오게...

kalstein의 이미지

글쓴이: kalstein / 작성시간: 목, 2006/11/16 - 12:31오전

굳이 value값들을 multiset으로 할 필요는 없어보입니다만...그냥 set을 2개 만들어서
각각 넣어도될것 같네요.

좀더 나은건...set_intersection을 직접 구현하면서 그냥 vector에 밀어넣기 한판;하는것도 괜찮을겁니다.

vector에 죽 다 넣고 (매우 빠르죠. memory reserve까지쓰면 더더욱) sort 한번 하는겁니다.

그게 set or multiset 쓰는것보다 성능은 월등합니다. (set계열은 insert 시마다 정렬작업해주는거니까요)

근데...해쉬테이블은 어디에 쓰신다는건지요? 질문에 해쉬관련은 전혀 안보여서요;;;

혹여 hash_multimap을 쓰시는거라면...hash 특성상 key order로 정렬되어있지않습니다.

그럴경우 님이 원하시는 결과는 아예 시작부터 다르게 생각해야겠지요 ^^


------------------------------------------
Let`s Smart Move!!
http://kalstein.tistory.com/

jiee의 이미지

글쓴이: jiee / 작성시간: 목, 2006/11/16 - 1:31오전

multiset으로 해야 한다고 했던 것은 위에서 각 multimap A, B에 중복없는 value값이 입력된다는 전제 조건이 없어서 그렇게 생각한 것입니다. 중복값이 없다면 물론 set으로 해야겠죠.^^

그리고, 옛 기억을 더듬어 알고리즘의 성능 분석을 해보면,
1. vector에 N개를 입력한 뒤 sort하고 구하는 것은 O(N) + O(NlogN)입니다.

2. set에 넣은 뒤 구하는 것은, STL의 set은 Red-Black트리이므로 삽입시 시간복잡도가 O(logN)입니다. 따라서, set에 N개를 입력하면 O(NlogN)으로 정렬되어 삽입될 것입니다.

따라서, 둘의 성능차는 거의 없을 것입니다.

근데, 위에 제 얘기가 맞나요?..-_-;;; 틀렸으면 지적해주세요.. : )
(기억이 가물...)

토나오게...

kalstein의 이미지

글쓴이: kalstein / 작성시간: 목, 2006/11/16 - 1:50오전

말그대로 대충 이정도~ 란 거라서요...

즉 루프 두번 돌면 O(N^2) 이지요. 근데...그 루프 안에서 무슨짓을 하는지는 상관없이 나타내니까요 ㅎㅎ

그냥 상식적으로 생각했을때...그렇다는거지요

정확한 걸 증명하기란...무척 어렵네요;; 하지만...

수식적 증명대신 공학적 입장에서 접근하자면

Effetive STL 의 항복 23을 보시면 되겠습니다 ^^

특히나...빈번한 삭제, 삽입이 없는 경우에 더욱 vector 사용을 추천하므로

님의 작업에는 더욱 어울리지않나 싶습니다... 혹여 책이 없으실 경우를 대비해 간단히 설명드리면...

- vector는 연속된 메모리 공간이므로, cache가 아주 잘 일어날것이며,

(정렬연관 컨테이너는 이어지는게 포인터로 되어있으므로...page fault가 일어날 가능성이 vector보단 높죠?)

그리고 더불어 메모리 사용량이 줄어들어서 cache에 더 큰 효과를 볼수있다. - 가 주 요지입니다.

뭐...스캇마이어스님의 글귀니까...믿을만 하겠지요 ㅡ _-; (무책임발언인가요 ㅎㅎ)


------------------------------------------
Let`s Smart Move!!
http://kalstein.tistory.com/

댓글 달기

텍스트 포맷에 대한 자세한 정보

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.