패트리샤 트리

프로그래밍 일반에 관한 포럼입니다.

Moderator: 류광

Locked
비회원

Re: 프로그래머의 사랑 노래

Post by 비회원 »

비회원 wrote: stl map 이라면, red-black 이진 트리로 구현되어 있을테니, O(1)이 아닌 O(log_2 n) 이므로, map 보다는 hash_map 을 사용하시는걸 추천합니다.
비회원 wrote: 그대의 map에 나를 넣어 주세요.
나의 key를 "연인" 으로 잡아 주세요.

그대가 어디에서든 "연인"을 부르면
나는 O(1)로 달려갈 것입니다.
음 hash_map도 있겠으나 Patricia trie ADT를 강력추천합니다. std::map보다는 5배이상
hash_map보다도 더 빨리 님의 곁으로 달려 갈수 있을듯...
이 패트리샤 알고리즘의 이름을 지은 원 저작자도 이 글 시작하신분의 마음과 같았지 않나 싶읍니다.
비회원

패트리샤 트리..

Post by 비회원 »

패트리샤 트리라는 것이 있었군요..

몰랐습니다. 방금 검색해보니 관련 예제소스가 있네요.

당장 테스트 해봐야겠습니다. !!!

혹시 패트리샤 검색알고리즘으로 실제 응용소스 제작하신분 있나요..

있으시면 속도비교나 소감좀...
비회원

Re: 프로그래머의 사랑 노래

Post by 비회원 »

Patricia 도 이진트리로 알고 있는데, 정말 해시보다 빠른가요? 해시의 버킷 사이즈가 충분하고 해싱함수만 빠르다면, 배열참조에 근접한 속도일텐데요. 이론적으로는 트리가 더 빠르다는 것이 잘 이해가 안 갑니다. 혹시 속도비교에 대한 자료나 문서가 있을까요?
비회원 wrote: 음 hash_map도 있겠으나 Patricia trie ADT를 강력추천합니다. std::map보다는 5배이상
hash_map보다도 더 빨리 님의 곁으로 달려 갈수 있을듯...
이 패트리샤 알고리즘의 이름을 지은 원 저작자도 이 글 시작하신분의 마음과 같았지 않나 싶읍니다.
비회원

Re: 프로그래머의 사랑 노래

Post by 비회원 »

비회원 wrote:Patricia 도 이진트리로 알고 있는데, 정말 해시보다 빠른가요? 해시의 버킷 사이즈가 충분하고 해싱함수만 빠르다면, 배열참조에 근접한 속도일텐데요. 이론적으로는 트리가 더 빠르다는 것이 잘 이해가 안 갑니다. 혹시 속도비교에 대한 자료나 문서가 있을까요?
비회원 wrote: 음 hash_map도 있겠으나 Patricia trie ADT를 강력추천합니다. std::map보다는 5배이상
hash_map보다도 더 빨리 님의 곁으로 달려 갈수 있을듯...
이 패트리샤 알고리즘의 이름을 지은 원 저작자도 이 글 시작하신분의 마음과 같았지 않나 싶읍니다.
사용한 nPatriciTrie는 string key만을 사용하는 것입니다.
아시다시피 map,hash_map은 범용 키를 사용하죠.
=========== 다음은 테스트 결과입니다. ===============
--------------------------
size = 8628 size = 0

std::hash_map = 6451

--------------------------
size = 8628 size = 0

nPatriciaTrie = 3106

Press any key to continue


============ 테스트 한 코드 ======================
int main(int argc, char* argv[]) {

fname_t buf;
uint s,e;
int idx[10000*10];
for(int i=0 ; i < 10000*10; i++)
{
idx=rand();
}
{
printf("----------------------------\n");

RDTSC(s);

std::map<std> p;
// insert some (first,second) pairs into the structure.

for(int i=0 ; i < 10000; i++)
{
sprintf(buf, "%das%usdl%xkfjweoidf%d",idx,idx+29,idx+3,idx+10);
p[buf]=i;
}

for(int i=0 ; i < 10000; i++)
{
sprintf(buf, "%das%usdl%xkfjweoidf%d",idx,idx+29,idx+3,idx+10);
int asdf = p[buf];
asdf++;
int b= asdf+asdf;
}
printf(" size = %d",p.size());
for(int i=0 ; i < 10000; i++)
{
sprintf(buf, "%das%usdl%xkfjweoidf%d",idx,idx[i]+29,idx[i]+3,idx[i]+10);
p.erase(buf);
}
printf(" size = %d",p.size());

RDTSC(e);

printf("\n\nstd::map = %u\n\n", (e-s)/100000);
}

{
printf("----------------------------\n");

RDTSC(s);

std::hash_map<std> p;
// insert some (first,second) pairs into the structure.

for(int i=0 ; i < 10000; i++)
{
sprintf(buf, "%das%usdl%xkfjweoidf%d",idx[i],idx[i]+29,idx[i]+3,idx[i]+10);
p[buf]=i;
}

for(int i=0 ; i < 10000; i++)
{
sprintf(buf, "%das%usdl%xkfjweoidf%d",idx[i],idx[i]+29,idx[i]+3,idx[i]+10);
int asdf = p[buf];
asdf++;
int b= asdf+asdf;
}
printf(" size = %d",p.size());
for(int i=0 ; i < 10000; i++)
{
sprintf(buf, "%das%usdl%xkfjweoidf%d",idx[i],idx[i]+29,idx[i]+3,idx[i]+10);
p.erase(buf);
}
printf(" size = %d",p.size());

RDTSC(e);

printf("\n\nstd::hash_map = %u\n\n", (e-s)/100000);
}
{
printf("----------------------------\n");

RDTSC(s);

nPatriciaTrie<int> p;
// insert some (first,second) pairs into the structure.

for(int i=0 ; i < 10000; i++)
{
sprintf(buf, "%das%usdl%xkfjweoidf%d",idx[i],idx[i]+29,idx[i]+3,idx[i]+10);
p[buf]=i;
}

for(int i=0 ; i < 10000; i++)
{
sprintf(buf, "%das%usdl%xkfjweoidf%d",idx[i],idx[i]+29,idx[i]+3,idx[i]+10);
int asdf = p[buf];
asdf++;
int b= asdf+asdf;
}
printf(" size = %d",p.size());
for(int i=0 ; i < 10000; i++)
{
sprintf(buf, "%das%usdl%xkfjweoidf%d",idx[i],idx[i]+29,idx[i]+3,idx[i]+10);
p.erase(buf);
}
printf(" size = %d",p.size());

RDTSC(e);

printf("\n\nnPatriciaTrie = %u\n\n", (e-s)/100000);
}


return 0;
}

=============== nPatriciaTrie 원본 소스 ======================


//----------------------------------------------------------------------------
//
// PATRICIA Trie Template Class
//
// Released into the public domain on February 3, 2005 by:
//
// Radu Gruian
// web: http://www.gruian.com
// email: [email protected]
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to:
//
// Free Software Foundation, Inc.
// 59 Temple Place, Suite 330
// Boston, MA 02111-1307
// USA
//
//----------------------------------------------------------------------------
//
// File: nPatriciaTrie.h
// Date: 02/03/2005
// Purpose: Patricia trie ADT.
//
//----------------------------------------------------------------------------

#ifndef nPatriciaTrieH
#define nPatriciaTrieH

#include <tchar>
#include <stdlib>
#include <string>

typedef char * nPatriciaTrieKey_t;
typedef const char* nPatriciaTrieKey_ct;


//----------------------------------------------------------------------------
//
// Class: nPatriciaTrieNode
// Purpose: A node in a PATRICIA trie.
// Each node stores one first, and the second associated with that first.
//
//----------------------------------------------------------------------------
template <class>
class nPatriciaTrieNode
//----------------------------------------------------------------
{
public:
int bit_index;
nPatriciaTrieKey_t first; // key
TTT second; // data
nPatriciaTrieNode<TTT>* left;
nPatriciaTrieNode<TTT>* right;

nPatriciaTrieNode()
{
Initialize(NULL, TTT() , -1, this, this);
}
//----------------------------------------------------------------------------

void Initialize
(
nPatriciaTrieKey_ct k
,const TTT &d
, int bi
,nPatriciaTrieNode<TTT>* l
,nPatriciaTrieNode<TTT>* r
)
{
if (k)
first = (nPatriciaTrieKey_t)strdup(k);
else
first = const_cast<nPatriciaTrieKey_t>(k);
second = d;
left = l;
right = r;
bit_index = bi;
}

//----------------------------------------------------------------------------

~nPatriciaTrieNode() {
if (first) {
free(first);
first = NULL;
}
}

//----------------------------------------------------------------------------

TTT GetData() {
return second;
}

//----------------------------------------------------------------------------

bool SetData(const TTT &d) {
second = d;
//memcpy(&second, &d, sizeof(TTT));
return true;
}

//----------------------------------------------------------------------------

nPatriciaTrieKey_ct GetKey() {
return first;
}

//----------------------------------------------------------------------------

nPatriciaTrieNode<TTT>* GetLeft() {
return left;
}

//----------------------------------------------------------------------------

nPatriciaTrieNode<TTT>* GetRight() {
return right;
}


};

//----------------------------------------------------------------------------
//
// Class: nPatriciaTrie
// Purpose: Implements a PATRICIA trie structure with keys of
// type nPatriciaTrieKey_t (currently char*, but can be changed, see
// the definition of nPatriciaTrieKey_t above).
//
//----------------------------------------------------------------------------
template <class> class nPatriciaTrie
{
public:
typedef nPatriciaTrieNode<TTT>* iterator;
nPatriciaTrieNode<TTT>* head;
size_t m_iSize;
public:


//----------------------------------------------------------------------------

nPatriciaTrie() {
// Create the head of the structure. The head is never moved
// around in the trie (i.e. it always stays at the top of the structure).
// This prevents further complications having to do with node removal.
head = new nPatriciaTrieNode<TTT>();
#define ZEROTAB_SIZE 256
head->first = (char*)calloc(ZEROTAB_SIZE, 1);
m_iSize=0;

}

//----------------------------------------------------------------------------

~nPatriciaTrie() {
clear();
}

//----------------------------------------------------------------------------

iterator insert(nPatriciaTrieKey_ct k, const TTT &d) {

nPatriciaTrieNode<TTT> *p, *t, *x;

// Start at the root
p = head;
t = (iterator)(p->right);

// Navigate down the tree and look for the first
while (p->bit_index <t>bit_index) {
p = t;
t = (iterator)(bit_get(k, t->bit_index) ? t->right : t->left);
}

// Is the first already in the tree?
if (key_compare(k, t->first))
return NULL; // Already in the tree!

// Find the first bit that does not match.
int i = bit_first_different(k, t->first);

// Find the appropriate place in the tree where
// the node has to be inserted
p = head;
x = (iterator)(p->right);
while ( ( p->bit_index <x>bit_index ) &&
( x->bit_index <i>bit_index) ? x->right : x->left);
}

// Allocate a new node and initialize it.
t = new nPatriciaTrieNode<TTT>();
++m_iSize;
t->Initialize(k, d, i, (bit_get(k, i) ? x : t), (bit_get(k, i) ? t : x));

// Rewire
if (bit_get(k, p->bit_index))
p->right = t;
else
p->left = t;

// Return the newly created node
return t;

}

//----------------------------------------------------------------------------

TTT& Lookup(nPatriciaTrieKey_ct k) {

// Lookup the node
iterator node = find(k);

// Failed?
if (!node)
{
return insert(k,TTT())->second;
}

// Return the second stored in this node
return node->second;

}

TTT& operator [](nPatriciaTrieKey_ct k)
{
return Lookup(k);
}

//----------------------------------------------------------------------------

iterator find(nPatriciaTrieKey_ct k) {

iterator p;
iterator x;

// Start at the root.
p = head;
x = (iterator)(head->right);

// Go down the Patricia structure until an upward
// link is encountered.
while (p->bit_index <x>bit_index) {
p = x;
x = (iterator)(bit_get(k, x->bit_index) ? x->right : x->left);
}

// Perform a full string comparison, and return NULL if
// the first is not found at this location in the structure.
if (!key_compare(k, x->first))
return NULL;

// Return the node
return x;

}

//----------------------------------------------------------------------------

bool erase(nPatriciaTrieKey_ct k) {

nPatriciaTrieNode<TTT> *p, *t, *x, *pp, *lp;
int bp, bl, br;
char* first = NULL;

// Start at the root
p = head;
t = (iterator)(p->right);

// Navigate down the tree and look for the first
while (p->bit_index <t>bit_index) {
pp = p;
p = t;
t = (iterator)(bit_get(k, t->bit_index) ? t->right : t->left);
}

// Is the first in the tree? If not, get out!
if (!key_compare(k, t->first))
return false; // The first could not be found!

// Copy p's first to t
if (t != p)
key_copy(p, t);

// Is p a leaf?
bp = p->bit_index;
bl = ((iterator)(p->left))->bit_index;
br = ((iterator)(p->right))->bit_index;

if ((bl > bp) || (br > bp)) {

// There is at least one downward edge.

if (p != t) {

// Look for a new (intermediate) first
first = strdup(p->first);

lp = p;
x = (iterator)(bit_get(first, p->bit_index) ? p->right : p->left);

while (lp->bit_index <x>bit_index) {
lp = x;
x = (iterator)(bit_get(first, x->bit_index) ? x->right : x->left);
}

// If the intermediate first was not found, we have a problem..
if (!key_compare(first, x->first)) {
free(first);
return false; // The first could not be found!
}

// Rewire the leaf (lp) to point to t
if (bit_get(first, lp->bit_index))
lp->right = t;
else
lp->left = t;

}

// Rewire the parent to point to the real child of p
if (pp != p) {
iterator ch = (iterator)(bit_get(k, p->bit_index) ? p->left : p->right);
if (bit_get(k, pp->bit_index))
pp->right = ch;
else
pp->left = ch;
}

// We no longer need 'first'
free(first);
first = NULL;

} else {

// Both edges (left, right) are pointing upwards or to the node (self-edges).

// Rewire the parent
if (pp != p) {
iterator blx = (iterator)(p->left);
iterator brx = (iterator)(p->right);
if (bit_get(k, pp->bit_index))
pp->right = (((blx == brx) && (blx == p)) ? pp : ((blx==p)?brx:blx));
else
pp->left = (((blx == brx) && (blx == p)) ? pp : ((blx==p)?brx:blx));
}

}

// Deallocate p (no longer needed)
delete p;
--m_iSize;

// Success!
return true;

}

//----------------------------------------------------------------------------

void recursive_remove(iterator root)
{
iterator l = (iterator)root->left;
iterator r = (iterator)root->right;

// Remove the left branch
if ( (l->bit_index >= root->bit_index) && (l != root) && (l != head) )
recursive_remove(l);

// Remove the right branch
if ( (r->bit_index >= root->bit_index) && (r != root) && (r != head) )
recursive_remove(r);

// Remove the root
delete root;
--m_iSize;

}

//----------------------------------------------------------------------------

int bit_get(nPatriciaTrieKey_ct bit_stream, int n) {
if (n <0>> 3))) >> k) & 0x1;
}

//----------------------------------------------------------------------------

bool key_compare(nPatriciaTrieKey_ct k1, nPatriciaTrieKey_ct k2) {
if (!k1 || !k2)
return false;
return (strcmp((char*)k1, (char*)k2) == 0);
}

//----------------------------------------------------------------------------

int bit_first_different(nPatriciaTrieKey_ct k1, nPatriciaTrieKey_ct k2) {
if (!k1 || !k2)
return 0; // First bit is different!
int n = 0;
int d = 0;
while ( (k1[n] == k2[n]) &&
(k1[n] != 0) &&
(k2[n] != 0) )
n++;
while (bit_get(&k1[n], d) == bit_get(&k2[n], d))
d++;
return ((n <<3>first) <strlen>first))
dest->first = (nPatriciaTrieKey_t)realloc(dest->first, 1 + strlen(src->first));
strcpy(dest->first, src->first);

// Copy the second from src to dest
dest->second = src->second;

// How about the bit index?
//dest->bit_index = src->bit_index;

}

size_t size(){ return m_iSize; }
void clear()
{
if(!head) return;
recursive_remove(head);
head=0;
m_iSize=0;
}

iterator end(){ return 0; }
iterator begin(){ return head;}

};
비회원

Re: 프로그래머의 사랑 노래

Post by 비회원 »

[quote="비회원"]Patricia 도 이진트리로 알고 있는데, 정말 해시보다 빠른가요? 해시의 버킷 사이즈가 충분하고 해싱함수만 빠르다면, 배열참조에 근접한 속도일텐데요. 이론적으로는 트리가 더 빠르다는 것이 잘 이해가 안 갑니다. 혹시 속도비교에 대한 자료나 문서가 있을까요?

radix tree 라고도 하는데, O(k) (k는 스트링의 길이) 입니다.
1 ~ k 번의 비교 연산이 필요하므로 항상 해시 (버킷 크기에 따라 1~n이지만 대개 1) 보다 빠르다고는 할 수 없겠네요.

저라면 해시를 쓰겠습니다. k번의 비교는 너무 많아요.
비회원

Re: 프로그래머의 사랑 노래

Post by 비회원 »

위에 어느 분이 속도 비교하신 걸 올리셨는데, 아래에 링크를 보시면 좀 더 구체적인 비교가 되어 있습니다.

http://gcc.gnu.org/onlinedocs/libstdc++ ... _test.html
http://gcc.gnu.org/onlinedocs/libstdc++ ... tests.html

patricia 와 hash 기반은 비슷한 검색속도를 보이지만, Insert 시에는 hash 보다 성능이 떨어지는 것으로 보입니다(map 이랑 비슷).
Locked