이중 연결 리스트에서의 정렬과 노드값 가져오기.
글쓴이: kleinstein / 작성시간: 화, 2006/09/19 - 3:39오후
안녕하세요..
이중 연결 리스트에서 정렬을 시키려면 어떤방법이 있을까요?
노드의 갯수가 무려 500,000 개가 넘는 이중 연결 리스트가 있는데 할수 있는 가장 빠른 속도로 정렬을 해야합니다.
정렬한 다음에는 원하는 값을 가진 노드를 바로바로 찾아서 뽑아올수 있어야 하구요..
그런데 정렬도 정렬이지만..
이중 연결 리스트에서는 원하는 노드로 곧바로 접근할수 있는 방법은 없지 않나요?
첫 노드에서부터 차례 차례로 다음 노드로 계속 가다가 원하는 노드가 나오면 그 노드의 값을 가지고 오는 방법밖에 없는게 맞나요?
그렇다면 원하는 노드를 가져오기 위해서 매번 전체 리스트를 뒤지게 되니까 속도가 많이 느릴것 같습니다.
이중 연결 리스트에서의 정렬과 원하는 노드를 가져오는 가장 빠른 방법들은 어떤것들이 있나요??
전문 프로그래머님들의 의견이 궁금합니다.
Forums:
두단계를 거치는게 낫지 않을까요
키 - 포인터 테이블을 먼저 작성하고 linked list를 새로 만드는 것이 나을지도(퍽)
Re:
알고 계신 대로가 맞습니다.
더블 링크드 리스트의 경우, 원하는 노드에 바로 접근하는 방법이 없기 때문에 linear search 를 하는 방법밖에는 없고,
어마어마한 퍼포먼스 저하를 가져옵니다.
또한, 더블 링크드 리스트에 있어서 소팅은 위에서 말한 "노드에 바로 접근하는 방법" 이 없기 때문에
익히 알려진 소팅 알고리즘의 사용도 어렵습니다.
더블 링크드 리스트에서 가장 빠른 소팅이라고 한다면 노드를 추가할때마다 소팅된 상태를 유지하게 하는것이 제일 나을 것입니다;;;
굳이 꽁수를 좀 부린다면,
첫번째 노드의 포인터를 array[0], 두번째 노드의 포인터를 array[1], ... 에 넣고,
array 를 소팅하는 방법이 있겠죠.
(물론, array 의 값을 소팅하는것이 아니라 array 의 값을 dereference 해서 노드에 포함되어 있는 key 값을 비교해야겠죠.
소팅과정에 발생하는 위치 교환은 array 의 값만을 교환하면 되겠죠)
원하시는것이 특정 key 값을 가지는 노드를 빠른 속도로 찾기 위해서 소팅을 생각하시는것 같은데...
자료구조를 더블 링크드 리스트 말고 트리 쪽을 고려해 보시는것은 어떤지요...
전체 리스트까지는 아니자만
kleinstein님께서 생각하신 방법으로 해도 매번 전체리스트를 뒤질 필요는 없는거 같은데요? 이미 정렬된 노드는 따로 떼어놓던지 해서
다시 안가게 한다면 시간이 많이 줄거 같네요. 혹 다른 방법이 있다면 다른 분께서 자세히 답해 주실겁니다.
list는 적합하지 않은
list는 적합하지 않은 데이터 구조로군요.
rb tree등의 balanced tree 쓰세요.
제 기억이 맞다면....
500,000개가 넘는 데이타에서 원하는 자료를 빠르게 검색하려면,
데이터 구조를 Binary Search Tree의 한 종류인 Red-Black트리로 변경하는 게 좋을 것 같습니다.
그 다음에 검색을 한다면 만족할만한 수준인 O(logn)으로 빠르게 검색하실 수 있을 겁니다.
만약 C++에서 작업한다면, STL에서 지원하는 map을 사용해 간단히 작업하실 수 있을 겁니다.
토나오게...
댓글 달기