구조체간의 비교 하기
글쓴이: 서건우 / 작성시간: 목, 2008/07/03 - 3:29오후
a{
int *test;
int count;
}
b{
int *a;
int *yy;
}a,b 구조체가 있는데요.
a구조체와 b 구조체의 test. a 값이 동일한 값을 지는 것만
따로 Temp 구조체에 담을려고 합니다.
a 구조체에서 test값이 된느 경우가 최대 10만건 정도 들어가구요.
b 구조체에서는 40만건의 자료가 거의 고정이며 순차적으로 구성되어 있어요.
단순히 중첩 for을 돌렸을 때 속도가 상당히 느리네요..
for()
{
for(){
if test , a값 비교해서 동일할 경우
{
temp 구조체에 데이터 입력
break;
}
}Forums:
sort한 다음 앞에서부터 순서대로 비교하세요.
중첩 for loop에 비해 믿기지 않는 눈부신 성능 향상 효과를 체험하게 되실 것입니다.
(말투가 꼭 약장수 같다는 생각이 잠시... -.-)
아마
데이터가 굉장히 많으면 오히려 sort에 무리가 따를 수도 있을것 같습니다만...
10만건이라는데 소트가 얼마나 걸릴지..(..............
b구조체 자료는 40만건이라는데 순차적이라는게 소트가 돼있다는건지 아닌지 모르겠습니다.
소트가 되어있다면 b를 대상으로 a 값으로 바이너리 서치같은것을 이용해도 효과를 볼 수 있을것도 같습니다만...
이러한 부분을
이러한 부분을 위해서 알고리즘이 필요하게 되는 것이죠. tree 등의 구조로 변경하시면, jick님이 말씀하신 것처럼 눈부신 성능 향상 효과를 체험하게 되실겁니다.
(저도 약장수로... ㅎㅎ)
------------------------------------------------------
아직은 젊다. 모든 것을 할 수 있는 나이란 말이지.
------------------------------------------------------
아직은 젊다. 모든 것을 할 수 있는 나이란 말이지.
한번만 하면 되는
한번만 하면 되는 작업이라면, 파일로 덤프 후
sort 후에 비교. (중복이 있으면 uniq도 걸어줌).
자주 여러번 해야한다면 (빈번히 데이터가 변경된다면), 둘중에 하나를 해쉬테이블에 넣고 lookup 하거나,
맘편하게 DB에 밀어넣어서 sql로 조작.
-----
오늘 나의 취미는 끝없는, 끝없는 인내다. 1973 法頂
-----
오늘 나의 취미는 끝없는, 끝없는 인내다. 1973 法頂
b는 거의
b는 거의 고정적이라는 말씀은 b는 그대로 두고 a를 바꿔가면서 같은 일을 여러 번 반복한다는 말씀이신지요?
저 데이타들을 데이타베이스에 넣고 join시키는 것이 훨씬 빠를 것 같습니다.
아니면 데이타베이스에서 join할 때 쓰는 알고리즘을 직접 구현하셔도 될 것 같습니다.
begin{signature}
THIS IS SPARTA!!!!!n.
end{signature}
위에서 얘기하셨듯이
위에서 얘기하셨듯이 자료구조 가 매우 중요하겠네요.
A 에 있는 값들을 B에서 찾아야 하는데, B 에 데이타가 BINARY SEARCH TREE 형태로 들어가있다면 자료를 찾기 위한 비교 회수가 LOG2^X번이니까 LOG2^40 이면 30번 정도가 될 것 같네요.
A 에 있는 10만 건 각각에 대해 최대 30번을 비교하게 된다면 최대 300만번의 비교가 필요하겠네요.
그냥 FOR 룹을 두 번 돌릴 때라면 100,000*300,000 = 3억 번이 될테니 bst 를 구성할 경우 이에 비해 33배 이상 빨라지겠군요.
--
오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...
http://mytears.org ~(~_~)~
나 한줄기 바람처럼..
오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...
http://mytears.org ~(~_~)~
나 한줄기 바람처럼..
앞에 답이 다 나왔네요~
제 생각엔,
한번만 하는 작업이라면, 그냥 이중 for loop 돌리시고 기다리시길 추천.
아니라면,
B 가 거의 고정이고 순차적이라는 점을 이용해, A 에 대해서만 loop 를 돌리고 B는 빠른 시간 내게 찾게 해주는
자료구조를 구현해야 합니다.
B 를 참조하는 가장 효율적인 방법은 hash table 인데, B 가 거의 고정이라면 B 에 대한 perfect
hash table 을 만들 경우 자료의 수에 상관 없이 constant time 안에 search 를 할 수 있습니다. 즉 10 만번의
loop 만이 필요합니다. 루즈하게 구현해도 C 로 몇백줄 안으로 할 수 있으니까 저라면 이쪽으로 할 것 같습니다.
Search tree 들도 빠르지만 hash table 만큼 빠르진 않습니다 ( O(log n) vs. O(1) ). 대신 binary search
tree 로는 hash table 로 빠르게 할 수 없는 minimum, maximum, successor (다음으로 큰 원소), predecessor (다음으로
작은 원소) 등이 가능하니 이게 필요하면 binary search tree 의 각종 변형판을 찾아 보시기 바랍니다.
기본적인 변형은 AVL 이나 red-black tree 이고, 유난히 자주 참조되는 원소가 있다면 이녀석들을 빨리 찾게 해
주는 splay tree 가 있고, 자료의 수가 매우 많고 disk I/O 가 부담스러운 상황이라면 DB 에 자주 응용되는
B-tree 를 뒤져보시기 바랍니다.
CPU 에 비해 메모리가 엄청 느린 상황이라면 judy tree 같은 것도 있긴 한데... 구현이 복잡하다고 알고 있습니다.
'자료의 수가 매우
'자료의 수가 매우 많고 disk I/O 가 부담스러운 상황이라면 DB 에 자주 응용되는
B-tree 를 뒤져보시기 바랍니다.'
disk I/O 가 부담스럽지 않은 상황이겠죠? ;)
메모리 상에서만 구현을 한다면 b-tree 보다는 avl 이나 red-black tree 같은 bst 변형판들이 구현하기에나 실제 효율 면에서나 훨씬 좋습니다.
--
오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...
http://mytears.org ~(~_~)~
나 한줄기 바람처럼..
오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...
http://mytears.org ~(~_~)~
나 한줄기 바람처럼..
댓글 달기