이럴 땐 어떤 자료구조가 좋을까요?
글쓴이: shodhpfooqmm / 작성시간: 일, 2012/01/22 - 1:16오전
내용은 이렇습니다.
각 라인에 하나의 레코드가 들어있는 정렬된 큰 파일을 읽은 후
검색을 하는 프로그램입니다.
복잡한 자료구조를 사용하지 않고 구현해 봤는데요
우선 처음 읽을 때 라인수와 크기 등을 저장한 후에
구조체에 공간을 동적으로 할당하고
두 번째 읽으면서 할당된 구조체에 자료를 저장한 후
검색을 시작하는 구조입니다.
하지만 두 번 읽기 때문에(물론 두 번째 읽을 때는 메모리 캐쉬 내에서 읽지만)
시간이 오래 걸립니다.
그래서 생각해본 방법이 B-Tree 혹은 AVL-Tree인데요.
이 방법을 사용하면 성능 효과가 많이 있을까요?
혹은 적합한 다른 자료구조가 있을까요?
단순 시간 복잡도 계산으로만은 시간을 예측하기가 힘드네요.
시간이 많으면 많은 방법을 구현해 보고 싶지만, 사정상 그렇게 되지는 않아 아쉽습니다.
선배님들의 조언 부탁드릴게요.
감사합니다.
Forums:
B-Tree를 추천합니다.
제가 말씀하신 사항들을 제대로 이해했는진 모르겠지만, 질문자님의 상황이라면 아래 두가지에 대해 생각해 보시는 것도 괜찮을 것 같습니다.
1. 이진검색을 활용
현재 선형검색방식(1번부터 끝번 레코드까지 순차적으로 검색)으로 만들어져 있다면 질문자님께서 말씀하신 것 처럼 이진검색이 훌륭한 대안이 될 것입니다.
거창하게 트리 클래스를 정의하거나 하지 않아도, 이진검색의 메커니즘만 이해하고 계신다면 프로젝트에 맞게 적용하실 수 있을거라 봅니다.
(검색함수를 만들어 재귀호출하는 방법 등..)
2. 꼭 모든 레코드를 메모리로 읽어들여야 하는가
일반적으로 메모리에서 검색하는 비용보다는 보조저장매체의 I/O를 처리하는 시간이 더 많이 소요됩니다.
따라서 모든 데이터를 일단 메모리로 읽어와야 할 필요가 없고, 그냥 검색이 주목적이라면
검색하는 중간중간에 필요한 레코드만 부분적으로 읽어도 됩니다.
그런데 질문자님꼐서 언급하신 제반사항으로 봐서는 레코드가 가변적인 것 같은데,
이럴 경우 이진검색 시 Byte 용량을 기준으로 가장 중앙에 있는 레코드를 읽어와서 비교연산을 하면 되겠습니다.
만약 프로젝트 성격상 꼭 모든 레코드를 일단 메모리로 올려야 한다면, 한 줄씩 읽기 보다는 통버퍼에 파일을 몽땅 읽은 뒤 메모리끼리 이동/복사하는 것도 속도향상에 간혹 도움이 될 수 있습니다.
답글 감사드립니다.
현재 이진검색을 활용해 구현한 상태인데요.
말씀하신 2번의 방법과 같이 하기는 프로그램 성격상 무리가 있을 것 같습니다.
왜냐하면 메모리에 모두 올린 후 장기간 대기하고, 쿼리가 날라오면 서치를 하는 형태라
그때 그때 디스크 I/O로 이진 검색을 하면 시간이 상당히 많이 소요될 것으로 보이기 때문이에요.
자면서 생각해본 결과 다른 대안이 생각났는데,
큰 메모리버퍼를 할당 후(예를 들어 128메가) 버퍼에에 파일 내용을 계속 읽고
구조체 안에 포인터를 넣어 각 레코드마다 해당 메모리 버퍼를 포인터 하도록 하는 방법입니다.
읽다가 메모리가 부족하면 realloc를 사용해 추가로 메모리를 할당하는 방법으로요.
이렇게 하면 두 번 읽기 때문에 생기는 속도 문제를 해결할 수 있을 것 같은데
그럴듯 한가요?
B-Tree도 좋은 방법이 될 것 같은데, 레코드가 이미 정렬이 되어있고, 삭제되는 경우도 없어
삽입 하는데 O(logn)의 복잡도가 약간 부담되네요.
실력이 충분하지 않아 에러 없는 B-Tree를 바로 구현하기가 힘들어 구현된 소스들을 참조해봐야 겠네요.
답변 너무 감사드립니다.
너무 큰 malloc은 좋지 않습니다
malloc을 큰 단위로 하면 그만큼 크기의 연속된 메모리 공간을 마련해야 하기 때문에 메모리 요구량이 더 커질 수 있습니다. (예를 들면 프로그램이 10K짜리를 malloc/free를 수백번 해서 10K짜리 빈 공간이 100개쯤 있다고 해도, 이게 연속되어 있지 않으면 1M짜리 malloc 요청이 들어왔을 때 OS를 불러 새로 연속된 메모리를 받아와야 합니다.)
물론, 반대로 너무 작은 malloc을 남발하는 것도 좋지 않습니다만... 128M를 한번에 malloc해야 한다면 구조를 다시 생각해 보시는 게 좋겠습니다.
각 레코드의 크기가 얼마인지는 모르지만 수백 byte 정도라면 하나씩 읽으면서 그때그때 malloc한다고 별로 성능이 떨어지지 않습니다. malloc 갯수 줄이려고 파일 두 번 읽는 것보다는 훨씬 낫습니다.
네 그것도 멋진 방법 같습니다!
좀 거시적 관점에서 이진검색을 추천드렸는데, 이미 이진검색 형태로 동작하고있는 상황에서 별도로 B-tree를 구현할지를 고민하고 계셨던 거군요..
이미 이진검색을 사용하고 계신다면 굳이 B-tree까지 구현할 필요가 있을지 잘 모르겠습니다 ^^;
말씀하신대로 노드 추가/삭제 시 비용이 들고, 무엇보다 추후 소스 유지관리 차원에서 가독성을 해칠 가능성이 크기 때문입니다.
말씀하신 구조체에 메모리 포인터를 두는 것도 좋은 방법이 될 것 같습니다.
단, 큰메모리 버퍼를 할당받는 방법대신 Memory Mapped File이라는 기능을 살며시 추천드려봅니다. (줄여서 MMF)
파일을 마치 메모리처럼 접근하여 읽기/쓰기가 가능하며 OS레벨에서 캐싱 같은 것들을 지원해 줍니다.
아래는 GPG사이트의 MMF에 대한 토론입니다.
http://www.gpgstudy.com/forum/viewtopic.php?t=3400&sid=6523ba0a365b5259d8fc5a5b52f02fab
답변 감사합니다.
덕분에 몰랐던 mmap 이라는 함수에 대해서도 공부하게 되었네요.
감사합니다.
큰 메모리를 malloc 하는 방법과 mmap 방법을 비교해 보겠습니다.(아마 mmap 방법이 더 빠를 것 같습니다.)
정말 큰 도움이 된 것 같습니다.
즐거운 설 명절 보내시길 바랍니다.
사용처나 컴퓨터 사양, 데이터 특성 등에 따라 다를 것 같네요
트리들에 대해 궁금하신 것 같으니 많이 알려진 트리들 세개를 비교하자면, 일반적인 선호도는,
데이터 수정이 많이 일어나면 RB-tree > AVL-tree > B-tree
Lookup 이 많이 일어나거나, 데이터 수가 극히 많거나 (그래서 in-memory 저장을 못하거나) 하면 B-tree
Memory 에 다 넣을 수 있고, lookup 과 수정중 하나가 극단적으로 일어나지 않으면 AVL-tree
라고들 합니다. 물론 데이터의 특성이나 implementation 의 완성도에 따라 다르겠죠. 그리고 이것들 이외에도 정말 수많은 트리가 있습니다.
그런데 높여야 하는 성능이 뭔가요?
언뜻 보기에 데이터를 일단 한번 다 메모리에 읽은 후 그 후로는 거의 query 만 일어나는 것 같기도 한데
query 성능이 이슈라면 단연 tree 보단 hash table 이 먼저 고려되어야 할 것 같습니다.
그냥 메모리에 거대한 hash table 을 올려놓는거죠.
데이터가 string 이고 수정이 좀 일어나면 trie 를 살펴보세요.
그리고 메모리가 문제라면 아마도 profiling 을 할 수 있겠군요.
자료가 string 이고 A,B,C,D,E 중 한 글자로 시작한다고 가정하면
일단 메모리가 허용하는 만큼 거대한 hash table 을 만들고
가장 검색 빈도가 높은 순으로 메모리에 채워 넣고
검색이 이중 하나로 시작하면 hash table 에서 읽어오고
아니면 그때 disk 를 찾아봐도 되겠네요.
disk 도 그냥 찾지 말고 데이터가 정렬되어 있으니까 각 글자마다 시작 지점을 기억해놓은 다음에
그곳으로 바로 점프하여 거기에서부터 검색을 시작하면 되겠습니다.
삭제가 일어나지 않으니까 거기에서부터 밑으로만 찾으면 되겠죠.
답글 감사드립니다.
문제를 조금 구체적으로 써보면
컴퓨터 사양은 메모리가 64GB 입니다.
데이터는 20기가가 넘는데 이 데이터를 모두 메모리에 올린 후 검색 작업을 할 예정입니다. (주 연산이 검색입니다.)
문제를 다시 말씀드리면 20기가가 넘는 데이터를 메모리로 읽어올 때
보다 효율적으로 읽을 수 있게 하고 싶은데요, 현재는 단순하게 처음 읽을 때 라인수와 크기를 읽고
해당 라인수 만큼 구조체를 동적 할당하여 두 번째 읽을 때 데이터를 읽게 됩니다.
따라서 읽는 속도가 느려지게 됩니다.(메모리 내에서 검색을 하기 때문에 이진 검색 속도는 충분히 빠른 것 같습니다.)
검색 속도는 차치하고 읽는 속도를 향상 시킬 다른 방법이 있을까요?
이렇게 큰 데이터를 만지는 것이 처음이라 어떤 방법이 효율적인지 한 번에 감이 오지 않네요ㅠ
핵심은 이것 같은데요, (1) 라인이 몇 개인지 실제
핵심은 이것 같은데요,
(1) 라인이 몇 개인지 실제 읽어 보기 전까지는 모르기 때문에, 라인 개수와 각 라인의 크기를 알기 위해 한번 읽고,
(2) 메모리를 할당한 다음, 실제 데이터를 읽어서 메모리에 저장하기 위해 한번 더 읽는데,
(3) 이를 한번으로 줄이고 싶다
한 라인을 저장할 수 있는 구조체를 A 라고 한다면, 이런 식으로 하면 되지 않을까요?
1. 충분히 큰 A* 배열를 할당해 놓고,
2. 한 라인을 읽고 A 구조체 하나를 동적으로 할당, 읽어들인 라인을 A에 저장
3. 2의 결과를 1의 A* 배열에 저장
4. 2 ~ 3을 반복 (만의 하나, 읽어 들인 라인의 수가 1의 A* 배열의 크기보다 크다면 그때 A* 배열을 realloc)
답글 감사드립니다.
현재 여러가지 방법을 구현하여 시간 측정을 목표로 하고 있습니다.
조언 감사드립니다.
댓글 달기