좋은 생각입니다.
많은 자료구조나 알고리즘 서적에서 해시 체인을 링크드 리스트로 구현한다는 얘기만 있습니다만,
사실 링크드 리스트는 길어지면 탐색시간이 오래 걸리는 단점이 있습니다.
그래서 말씀하신 것처럼 힙으로 구현해도 됩니다.
힙도 일종의 트리구조이고 트리구조도 링크드 리스트를 계층적으로 구현한 것이므로,
해시 체인에 사용하시면 됩니다.
뿐만 아니라 대용량으로 가면 갈수록,
해시 체인에 걸리는 속도 저하 문제를 해결하기 위해
BTree와 같이 좀더 효율적인 자료구조로 연결해도 됩니다.
이처럼 자료구조와 알고지즘은 비지니스모델에 맞게끔 가장 적절한 것을
맞춤형으로 적시적소에 응용하는 것이 중요하겠습니다.
즐거운 통신시간 되시길...(^^)
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
"Heap을 링크드 리스트로 만든다"로 생각하셔도 됩니다.
Heap을 직접 구현해 보시면, 이게 링크드 리스트가 기본이 되어 파생된 자료구조라는것을
느끼실 것입니다. 저도 이거 터득하는데 많은 노력과 시간이 들었습니다.
모든 자료구조는 링크드 리스트로 부터 출발합니다.
그리고,
"Hash 테이블의 매 bucket에 heap을 위해 미리 공간을 할당한다면 hashing을 할필요가 없겠지요." --> 링크드 리스트와 Heap과의 관계를 확실히 이해하시면, 이런 말씀을 하지 않습니다.
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
제가 알기로 heap 관련 알고리즘들은 random access를 기반으로 하는데 (뭐 linked list로 못만들거야 없겠지만)
어떻게 linked list가 기본이 되어 파생된 자료구조라는 것을 느끼신 것인지 한 수 가르침 부탁합니다.
> 모든 자료구조는 링크드 리스트로 부터 출발합니다.
array는요? (동적할당한 contiguous memory를 포함해서), rgbi3307 님은 array 베우시기 전에 linked list 먼저 베우셨나봐요.
> 링크드 리스트와 Heap과의 관계를 확실히 이해하시면, 이런 말씀을 하지 않습니다.
제가 이해를 못하고 이런 글을 쓴다고 생각하시는군요. 저는 disk based B+ tree, hash(including chaining, open addressing, rehashing)
이런걸 17, 18년 자료구조, DB시간에 다 구현해보았습니다만 그새 이론이 많이 바뀌었나보군요.
모르면 베워야죠 뭐....
Heap이 linked list array가 아니라 linked list에서 파생된 자료구조라는 것을 먼저 베워보고싶습니다.
네, 자료구조와 알고리즘에 대해서 열정을 가지고 계신분인듯하여 무척 반갑습니다.
말씀하신 것처럼 "heap이 linked list가 기본이 되어 파생된 자료구조"라고
학계의 서적들에서 언급하는걸 저도 본적이 없습니다.
그러나, 제가 여러가지 실습을 하면서 직접 구현해 본결과
모든 자료구조는 링크드 리스트가 기본이고 여기서 부터 파생됩니다.
기본원리가 그렇습니다. 앞으로 제가 책을 쓰면 반드시 이것을 언급하면서 실습예제로 보여드리겠습니다.
실제 코딩해 보시면 압니다.
아직 느끼시지 못했다면, 아래의 링크드 리스트 노드와 힙의 노드를 비교해 보세요.
모두가 link로 연결됩니다. 이것을 저는 중요하게 보는 것입니다.
화면 상단의 정의:
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min-heap.)
번역해 보면:
컴퓨터 과학에서, 힙은 트리를 기반으로 한 데이터 구조를 힙 속성을 만족하도록 특성화 시킨 것이다. 힙 속성은 B가 A의 자식노드라면 key(A) ≥ key(B). (즉, 부모노드의 키가 자식보다 크다). 이것은 루트 노드가 항상 최대 키라는 것을 의미한다. 이러한 속성을 만족하는 힙을 max-heap이라고 부르기도 한다. (또다른 방식으로, 비교를 반대로 하면, 가장 작은 요소들이 항상 루트 노드이므로 이것은 min-heap이 되는 결과가 된다.)
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
Heaps are usually implemented in an "array", and do not require pointers between elements.
이런 문구가 있죠? 더 내려가면 아래와 같은 문구도 있습니다.
"Full and almost full binary heaps may be represented in a very space-efficient way using an "array" alone. The first (or last) element will contain the root. The next two elements of the array contain its children. The next four contain the four children of the two child nodes, etc. Thus the children of the node at position n would be at positions 2n and 2n+1 in a one-based array, or 2n+1 and 2n+2 in a zero-based array. This allows moving up or down the tree by doing simple index computations"
linked list로 구현 못할 이유야 없지만 root escalation 혹은 left, right child의 위치를 random access 해서 찾기 때문에 Heap이 효율적인 자료구조가 되는 것인데 이걸 linked list로 구현할 바에는 다른 알고리듬을 쓰는게 낮지요.
> 실제 코딩해 보시면 압니다.
> 아직 느끼시지 못했다면, 아래의 링크드 리스트 노드와 힙의 노드를 비교해 보세요.
그리고 몇 번 말씀드렸는데, 제가 마치 코딩을 안해봤다고 생각을 하시거나, rgbi3307님께서 실험을 해보니 이렇더라는 식의 답변은 상대를 무시하는 듯한
괜한 오해를 일으킬 수 있습니다.
보여주신 두 node의 구조체는 singly list와 binary tree를 구현할 때 일반적으로 사용하겠지만 일반적으로 heap을 구현할 때 그렇게 구현하지 않기 때문에 제가 답글을 계속 달고 있는거에요. 다른 사람들이 보면 진짜 그런줄 알까봐서 말입니다.
> 모든 자료구조는 링크드 리스트가 기본이고 여기서 부터 파생됩니다.
무슨 생각으로 이렇게 말씀하신지는 충분히 이해하겠는데, 자료구조를 처음 베운 분들이 윗 글을 보면 오해의 여지가 있지 않겠어요?
예를 들어 chaining 기반 hash table 만드실때 hash table자체도 링크드 리스트로 만드세요? random access가 필요한데?
이렇게 표현해야 정확하죠.
모든 자료구조는 array와 linked list를 기본으로 하여 파생된다.
우리가 프로그래밍으로 밥벌어먹고 사는 한 우리가 만든 코드나 우리가 쓰는 글이 군더더기 없이 정확하고 깔끔해야
인생이 덜 고달플거라고 생각해서 그냥 넘어갈 수 있는 부분을 제가 다시 짚고 넘어간겁니다.
그런데 chain 이 얼마나 길어지는지요. 만일 chain이 꽤 길다면 hash table 자체가 의미가 없을 수도 있습니다. 그 상황이라면 hash 함수를 재정의하는 것을 고려해봐야 할 것 같습니다.
최악상황을 고려한다면 생각해볼 수 있지만 만일 그렇다면 처음 선택부터 hash table 이 아니라 balaced tree 계열을 선택하는 것이 나을 겁니다.
hash table과 BTree는 비지니스모델에 맞게끔 응용하시면 됩니다.
그런데, 처음 발제자는 해시 체인이 길어진다면 Heap을 사용하면 어떨까요?라는 질문이고,
이게 아주 좋은 생각(발상)이라는 것입니다.
자료구조와 알고리즘을 깊이 있게 실제로 구현해 보시면,
hash table과 BTree를 각각 따로 생각해서는 문제가 풀리지 않는 경우가 있습니다.
특히, 대용량으로 갈 수록 더더욱 그렇습니다.
이때, 여러가지 자료구조의 특징과 장점을 혼합하여 새롭게 구현할때가 옵니다.
그래서, 처음 발제자께서 말씀하신 생각이 좋은 것이고,
앞으로 많은 발전을 할 수 있을듯 합니다.
개인적으로 좀 친해 지고 싶군요.
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
개인적인 생각이지만 Heap이 아닌 Binary Search Tree를 사용해야 하지않을까 조심스레 추측해봅니다.
만약 hash함수가 f(x)와 g(x) 이렇게 두 개가 있다고 할 경우 pseudo코드를 짜보면..
function get(key):
int code1 = f(key);
BinarySearchTree tree = hashtable[code1];
return tree.find(g(key));
이런식으로 되야할거 같은데,
BinarySearchTree 대신 Heap을 사용한다면 search()를 O(N)만에 해낼 수 없기 때문입니다..(Heap은 getMax()나 getMin(), insert()만 O(logN)을 보장합니다)
결국 hashtable[i]가 List로 구현되어있는 경우와 시간복잡도가 다를 바가 없기 때문입니다.
오랜만에 왔는데, 와 정말 놀랬습니다. 예전 학부시절 그냥 문득 생각에 썼던글에 이렇게 댓글이 많이 달렸을 줄이야...
알고리즘 시간 복잡도까지는 계산해보지 않았지만, 결과적으로 해시 체인이 길어졌을때 그 부분을 힙으로 구현하는건 의미가 없는것 같습니다. ( 이건 제가 그때 실험적으로 해봤습니다. )
사실 학부 졸업 논문에서 해시구현에 체인이 발생해서 느려져 한번 생각했던것 뿐이었습니다.
물론 제가 타겟을 했던 논문에서는 Hash를 채용했지만, 저는 아예 자료구조를 힙으로 구현해서 실험했습니다. ( 그 논문에서는 솔직히 어떤 자료구조를 선택하냐는건 별로 의미가 없었습니다. )
논문은 고속템플렛매칭의 논문이었습니다. 벌써 2년이 지나가네요. 시간 참 빠릅니다.
좋은 생각입니다. 많은 자료구조나 알고리즘 서적에서
좋은 생각입니다.
많은 자료구조나 알고리즘 서적에서 해시 체인을 링크드 리스트로 구현한다는 얘기만 있습니다만,
사실 링크드 리스트는 길어지면 탐색시간이 오래 걸리는 단점이 있습니다.
그래서 말씀하신 것처럼 힙으로 구현해도 됩니다.
힙도 일종의 트리구조이고 트리구조도 링크드 리스트를 계층적으로 구현한 것이므로,
해시 체인에 사용하시면 됩니다.
뿐만 아니라 대용량으로 가면 갈수록,
해시 체인에 걸리는 속도 저하 문제를 해결하기 위해
BTree와 같이 좀더 효율적인 자료구조로 연결해도 됩니다.
이처럼 자료구조와 알고지즘은 비지니스모델에 맞게끔 가장 적절한 것을
맞춤형으로 적시적소에 응용하는 것이 중요하겠습니다.
즐거운 통신시간 되시길...(^^)
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
> 힙도 일종의 트리구조이고 트리구조도 링크드
> 힙도 일종의 트리구조이고 트리구조도 링크드 리스트를 계층적으로 구현한 것이므로,
위에 문장 처럼 글을 쓰시면 Heap을 링크드 리스트로 만든다 뭐 이렇게 생각하기 딱 좋은데
Heap을 링크드 리스트로 만들면 힙의 성능이 나겠습니까?
> 해시 체인에 사용하시면 됩니다.
Hash 테이블의 매 bucket에 heap을 위해 미리 공간을 할당한다면 hashing을 할필요가 없겠지요.
아래 winner님 말씀처럼 Hash function이 잘못되었다고 보거나 rgbi3307님께서 말씀하신 것처럼 " 비지니스모델에 맞게끔 가장 적절한 것"
을 찾아봐야 겠지요
"Heap을 링크드 리스트로 만든다"로 생각하셔도
"Heap을 링크드 리스트로 만든다"로 생각하셔도 됩니다.
Heap을 직접 구현해 보시면, 이게 링크드 리스트가 기본이 되어 파생된 자료구조라는것을
느끼실 것입니다. 저도 이거 터득하는데 많은 노력과 시간이 들었습니다.
모든 자료구조는 링크드 리스트로 부터 출발합니다.
그리고,
"Hash 테이블의 매 bucket에 heap을 위해 미리 공간을 할당한다면 hashing을 할필요가 없겠지요." --> 링크드 리스트와 Heap과의 관계를 확실히 이해하시면, 이런 말씀을 하지 않습니다.
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
떱, heap이 linked list가 기본이 되어
떱, heap이 linked list가 기본이 되어 파생된 자료구조라는걸 처음 듣네요.
제가 알기로 heap 관련 알고리즘들은 random access를 기반으로 하는데 (뭐 linked list로 못만들거야 없겠지만)
어떻게 linked list가 기본이 되어 파생된 자료구조라는 것을 느끼신 것인지 한 수 가르침 부탁합니다.
> 모든 자료구조는 링크드 리스트로 부터 출발합니다.
array는요? (동적할당한 contiguous memory를 포함해서), rgbi3307 님은 array 베우시기 전에 linked list 먼저 베우셨나봐요.
> 링크드 리스트와 Heap과의 관계를 확실히 이해하시면, 이런 말씀을 하지 않습니다.
제가 이해를 못하고 이런 글을 쓴다고 생각하시는군요. 저는 disk based B+ tree, hash(including chaining, open addressing, rehashing)
이런걸 17, 18년 자료구조, DB시간에 다 구현해보았습니다만 그새 이론이 많이 바뀌었나보군요.
모르면 베워야죠 뭐....
Heap이 linked list array가 아니라 linked list에서 파생된 자료구조라는 것을 먼저 베워보고싶습니다.
네, 자료구조와 알고리즘에 대해서 열정을 가지고
네, 자료구조와 알고리즘에 대해서 열정을 가지고 계신분인듯하여 무척 반갑습니다.
말씀하신 것처럼 "heap이 linked list가 기본이 되어 파생된 자료구조"라고
학계의 서적들에서 언급하는걸 저도 본적이 없습니다.
그러나, 제가 여러가지 실습을 하면서 직접 구현해 본결과
모든 자료구조는 링크드 리스트가 기본이고 여기서 부터 파생됩니다.
기본원리가 그렇습니다. 앞으로 제가 책을 쓰면 반드시 이것을 언급하면서 실습예제로 보여드리겠습니다.
실제 코딩해 보시면 압니다.
아직 느끼시지 못했다면, 아래의 링크드 리스트 노드와 힙의 노드를 비교해 보세요.
모두가 link로 연결됩니다. 이것을 저는 중요하게 보는 것입니다.
//링크드 리스트 구조체 typedef struct node { void* data; struct node* link; } NODE; //Heap 구조체 typedef struct node { struct node* left_link; void* data; struct node* right_link; } NODE;그리고, Heap도 종류가 많습니다만,
위키피디아에서 "Heap (data structure)"으로 한번 검색해 보시면,
http://en.wikipedia.org/wiki/Heap_(data_structure)
화면 상단의 정의:
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min-heap.)
번역해 보면:
컴퓨터 과학에서, 힙은 트리를 기반으로 한 데이터 구조를 힙 속성을 만족하도록 특성화 시킨 것이다. 힙 속성은 B가 A의 자식노드라면 key(A) ≥ key(B). (즉, 부모노드의 키가 자식보다 크다). 이것은 루트 노드가 항상 최대 키라는 것을 의미한다. 이러한 속성을 만족하는 힙을 max-heap이라고 부르기도 한다. (또다른 방식으로, 비교를 반대로 하면, 가장 작은 요소들이 항상 루트 노드이므로 이것은 min-heap이 되는 결과가 된다.)
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
설명감사합니다. 그런데 알려주신 그 위키피디아
설명감사합니다. 그런데 알려주신 그 위키피디아 url에 보면
Heaps are usually implemented in an "array", and do not require pointers between elements.
이런 문구가 있죠? 더 내려가면 아래와 같은 문구도 있습니다.
"Full and almost full binary heaps may be represented in a very space-efficient way using an "array" alone. The first (or last) element will contain the root. The next two elements of the array contain its children. The next four contain the four children of the two child nodes, etc. Thus the children of the node at position n would be at positions 2n and 2n+1 in a one-based array, or 2n+1 and 2n+2 in a zero-based array. This allows moving up or down the tree by doing simple index computations"
linked list로 구현 못할 이유야 없지만 root escalation 혹은 left, right child의 위치를 random access 해서 찾기 때문에 Heap이 효율적인 자료구조가 되는 것인데 이걸 linked list로 구현할 바에는 다른 알고리듬을 쓰는게 낮지요.
> 실제 코딩해 보시면 압니다.
> 아직 느끼시지 못했다면, 아래의 링크드 리스트 노드와 힙의 노드를 비교해 보세요.
그리고 몇 번 말씀드렸는데, 제가 마치 코딩을 안해봤다고 생각을 하시거나, rgbi3307님께서 실험을 해보니 이렇더라는 식의 답변은 상대를 무시하는 듯한
괜한 오해를 일으킬 수 있습니다.
보여주신 두 node의 구조체는 singly list와 binary tree를 구현할 때 일반적으로 사용하겠지만 일반적으로 heap을 구현할 때 그렇게 구현하지 않기 때문에 제가 답글을 계속 달고 있는거에요. 다른 사람들이 보면 진짜 그런줄 알까봐서 말입니다.
> 모든 자료구조는 링크드 리스트가 기본이고 여기서 부터 파생됩니다.
무슨 생각으로 이렇게 말씀하신지는 충분히 이해하겠는데, 자료구조를 처음 베운 분들이 윗 글을 보면 오해의 여지가 있지 않겠어요?
예를 들어 chaining 기반 hash table 만드실때 hash table자체도 링크드 리스트로 만드세요? random access가 필요한데?
이렇게 표현해야 정확하죠.
모든 자료구조는 array와 linked list를 기본으로 하여 파생된다.
우리가 프로그래밍으로 밥벌어먹고 사는 한 우리가 만든 코드나 우리가 쓰는 글이 군더더기 없이 정확하고 깔끔해야
인생이 덜 고달플거라고 생각해서 그냥 넘어갈 수 있는 부분을 제가 다시 짚고 넘어간겁니다.
다른 뜻 없으니 기분 나쁘게 생각하지 마시길.
물론 장단점이 있습니다.
그런데 chain 이 얼마나 길어지는지요. 만일 chain이 꽤 길다면 hash table 자체가 의미가 없을 수도 있습니다. 그 상황이라면 hash 함수를 재정의하는 것을 고려해봐야 할 것 같습니다.
최악상황을 고려한다면 생각해볼 수 있지만 만일 그렇다면 처음 선택부터 hash table 이 아니라 balaced tree 계열을 선택하는 것이 나을 겁니다.
hash table과 BTree는 비지니스모델에
hash table과 BTree는 비지니스모델에 맞게끔 응용하시면 됩니다.
그런데, 처음 발제자는 해시 체인이 길어진다면 Heap을 사용하면 어떨까요?라는 질문이고,
이게 아주 좋은 생각(발상)이라는 것입니다.
자료구조와 알고리즘을 깊이 있게 실제로 구현해 보시면,
hash table과 BTree를 각각 따로 생각해서는 문제가 풀리지 않는 경우가 있습니다.
특히, 대용량으로 갈 수록 더더욱 그렇습니다.
이때, 여러가지 자료구조의 특징과 장점을 혼합하여 새롭게 구현할때가 옵니다.
그래서, 처음 발제자께서 말씀하신 생각이 좋은 것이고,
앞으로 많은 발전을 할 수 있을듯 합니다.
개인적으로 좀 친해 지고 싶군요.
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
음..
개인적인 생각이지만 Heap이 아닌 Binary Search Tree를 사용해야 하지않을까 조심스레 추측해봅니다.
만약 hash함수가 f(x)와 g(x) 이렇게 두 개가 있다고 할 경우 pseudo코드를 짜보면..
function get(key):
int code1 = f(key);
BinarySearchTree tree = hashtable[code1];
return tree.find(g(key));
이런식으로 되야할거 같은데,
BinarySearchTree 대신 Heap을 사용한다면 search()를 O(N)만에 해낼 수 없기 때문입니다..(Heap은 getMax()나 getMin(), insert()만 O(logN)을 보장합니다)
결국 hashtable[i]가 List로 구현되어있는 경우와 시간복잡도가 다를 바가 없기 때문입니다.
글쓴이 입니다.
오랜만에 왔는데, 와 정말 놀랬습니다. 예전 학부시절 그냥 문득 생각에 썼던글에 이렇게 댓글이 많이 달렸을 줄이야...
알고리즘 시간 복잡도까지는 계산해보지 않았지만, 결과적으로 해시 체인이 길어졌을때 그 부분을 힙으로 구현하는건 의미가 없는것 같습니다. ( 이건 제가 그때 실험적으로 해봤습니다. )
사실 학부 졸업 논문에서 해시구현에 체인이 발생해서 느려져 한번 생각했던것 뿐이었습니다.
물론 제가 타겟을 했던 논문에서는 Hash를 채용했지만, 저는 아예 자료구조를 힙으로 구현해서 실험했습니다. ( 그 논문에서는 솔직히 어떤 자료구조를 선택하냐는건 별로 의미가 없었습니다. )
논문은 고속템플렛매칭의 논문이었습니다. 벌써 2년이 지나가네요. 시간 참 빠릅니다.
댓글 달기