GpgStudy 게시판 인덱스 GpgStudy
Game Programming Gems 토론
 
 FAQFAQ   검색검색   멤버리스트멤버리스트   사용자 그룹사용자 그룹  이미지 자료실이미지 자료실   사용자 등록하기사용자 등록하기 
 개인 정보개인 정보   쪽지(개인 메시지)를 확인하려면 로그인하십시오쪽지(개인 메시지)를 확인하려면 로그인하십시오   로그인로그인 
GpgStudy 홈으로

[팁?] Hashed string
페이지로 1, 2  다음
 
잠김[?]    GpgStudy 게시판 인덱스 -> 프로그래밍 일반
이전 주제 보기 :: 다음 주제 보기  
글쓴이 메시지
Gamza



가입: 2001년 10월 11일
올린 글: 610
올리기[팁?] Hashed string 올려짐: 2002-08-17 15:06
인용과 함께 답변 이 게시물을 del.icio.us에 추가
게임을 만들다 보면 오브젝트를 이름으로 얻어와야 할때가 있습니다.

보통 속도를 위해 오브젝트를 정렬해놓게되죠..(로그시간 검색)

음...그런데도....좀 껄끄러운것이....스트링비교를 해야한다는 겁니다.

오브젝트의 이름에 해쉬코드를 넣어두면 스트링비교마저 거의 없앨수 있게됩니다.

코드: 
class GameObject
{
public:
	void SetName( const char*Name )
	{
		m_Name = Name;
		m_HashCode = GetHashCode( Name );
	}
	inline virtual bool operator < ( const GameObject& Obj ) const
	{
		if( m_HashCode != Obj.m_HashCode )
			return m_HashCode < Obj.m_HashCode;
		return strcmp( m_Name, Obj.m_Name ) < 0;
	}
...
}

70000개의 파일명을 테스트 해본결과 문자열 비교횟수가

최대17/평균16.15 회이던것이, 최대4/평균1.01 회 로 줄어들었습니다.

검색된 문자열이 정확한지 확인하기위한 '최종1회'의 문자열 비교만 일어난 셈이죠.

제가 테스트한 해쉬 함수는 이렇습니다.
코드: 
unsigned long GetHashCode( const char* String )
{
	unsigned long i,len;
	unsigned long ch;
	unsigned long result;
	unsigned long XOR;

	len		= strlen( String );
	result	= 0;
	XOR		= 0;
	for( i=0; i

_________________
HOME: http://www.Gamza.net

Gamza 가 2002-08-18 13:50에 수정함, 총 1 번 수정됨
위로
사용자 정보 보기 쪽지 보내기 글 올린이의 웹사이트 방문 MSN 메신저
Xine



가입: 2002년 8월 12일
올린 글: 252
올리기 올려짐: 2002-08-17 16:25
인용과 함께 답변 이 게시물을 del.icio.us에 추가
이..이렇게좋은... 꼭필요한 시기에 이렇게 좋은 내용을
올려주시다니...
해쉬를 쓸생각을 못하고있었네요..
잘쓰겠습니다~ 지금 당장 붙여야겠어요... texture manager등등.. ^.^
정수ID를 둘려고도 했는데... 역시나 프로그램이 커지면 커질수록
문자열이름을 오브젝트에 붙인다는게 아주 편한데...
이렇케해서 쓰면 두가지 잇점을 모두얻겠네요..
_________________
이덕희
위로
사용자 정보 보기 쪽지 보내기 이메일 보내기
Zho



가입: 2001년 8월 2일
올린 글: 328
소속: 취미게임개발자
올리기지호의 해쉬 테이블 소스 공개!!! 올려짐: 2002-08-18 02:16
인용과 함께 답변 이 게시물을 del.icio.us에 추가
해쉬알고리즘은 요걸 참조했습니다. 빠르고 쓸만하다고 하더라구요. 저는 개인적으로 특별히 테스트는 안 해봤습니다. 남들이 좋다고 하니 쓰는거죠..^^

http://www.cs.yorku.ca/~oz/hash.html

아래는 제가 만든 극비 코드의 일부분.... ^^

코드: 
/** 
 * @file zz_hash_table.h
 * @brief hash table class.
 * @author Jiho Choi (zho@korea.com)
 * @version 1.0
 * @date    20-jun-2002
 *
 * $Id: zz_hash_table.h,v 1.4 2002/07/13 20:32:05 zho Exp $
 */

#ifndef	__ZZ_HASH_TABLE_H__
#define __ZZ_HASH_TABLE_H__

#define ZZ_HASH_DEFAULT_SIZE 64

#include 
#include "zz_mem.h"
#include "zz_log.h"

/*
bucket#0 : slot#1<->slot#2<->slot#3<->....<->slot#n->NULL
bocket#1 : slot#1<->....
.....
bucket#n : ....

bucket# = hash_function(string);
*/

template 
class zz_hash_table {
private:
	struct _slot {
		char * key; // string name

		_slot * prev; // link in slot list
		_slot * next;

		_slot * list_prev; // double link list to traverse
		_slot * list_next;

		T data;

		_slot () : key(NULL), next(NULL), prev(NULL), list_prev(NULL), list_next(NULL) {}

		~_slot () {
			if (key) { // if allocated name exist, delete it.
				zz_delete[] key; // newed in set_key()
			}
			if (prev) {
				prev->next = next;
			}
			if (next) {
				next->prev = prev;
			}
			if (list_prev) {
				list_prev->list_next = list_next;
			}
			if (list_next) {
				list_next->list_prev = list_prev;
			}
		}

		void set_key (const char * key_to_set) {
			key = zz_new char[strlen(key_to_set)+1]; // will be deleted in ~_slot()
			strcpy(key, key_to_set);
		}
	};

	_slot ** _bucket; // bucket. comprises slot pointers
	int _bucket_size; // bucket size. the number of slot lists

	_slot * _head, * _tail; // for sequential access

	int _count; // total allocated slot number

	// find slot with same key
	_slot * _find_slot (const char * key) {
		_slot * found_slot = _bucket[_hash(key)];

		while (found_slot) {
			if (!strcmp(found_slot->key, key)) {
				return found_slot;
			}
			found_slot = found_slot->next;
		}
		return NULL;
	}

	// slot initialize
	void _init (void) {
		_head = NULL;
		_tail = NULL;
		_count = 0;
		_bucket = zz_new _slot * [_bucket_size]; // * means pointer. not multiplication

		for (int i = 0; i < _bucket_size; i++) {
			_bucket[i] = NULL;
		}
	}

	int _hash (const char * key_to_hash) {
		// [ref] djb2 hash algorithm
		//  http://www.cs.yorku.ca/~oz/hash.html
		unsigned long hash_code = 5381;
		int c;

		while (c = *key_to_hash++)
			hash_code = ((hash_code << 5) + hash_code) + c; // hash * 33 + c

		return (hash_code % _bucket_size);

		//unsigned char c;
		//int i = 0;
		//long hash_code = 0;
		//while (c = (unsigned char)key_to_hash[i++]) {
		//	hash_code += c*i; // i >= 1
		//}
		//return (hash_code % _bucket_size);
	}

public:
	zz_hash_table(void) : _bucket_size(ZZ_HASH_DEFAULT_SIZE) {
		_init();
	}
	
	// size : bucket size
	zz_hash_table(int size) : _bucket_size(size) {
		_init();
	}

	~zz_hash_table(void) {
		for (int i = 0; i < _bucket_size; i++) {
			if (_bucket[i]) {
				zz_delete _bucket[i];
				_count--;
			}
		}
		assert(_count == 0);
		zz_delete _bucket;
	}

	bool insert (const char * key, T value) {
		_slot * end_slot, * new_slot = NULL;
		
		if (find(key)) {
			return false; // already exist same key
		}
			
		int hash_code = _hash(key);

		end_slot = _bucket[hash_code];

		while (end_slot && end_slot->next) {
			end_slot = end_slot->next;
		}

		new_slot = zz_new _slot;

		if (new_slot == NULL) {
			return false;
		}

		new_slot->set_key(key);
		new_slot->data = value;

		if (end_slot) {
			new_slot->prev = end_slot;
			end_slot->next = new_slot;
		}
		else {
			_bucket[hash_code] = new_slot;
		}
		
		// for list, add to tail slot
		if (_tail) {
			new_slot->list_prev = _tail;
			_tail->list_next = new_slot;
			_tail = new_slot;
		}
		if (!_head) { // if thi
			assert(!_tail);
			_head = new_slot;
			_tail = new_slot;
		}
		
		++_count;

		return true;
	}

	bool remove (const char * key) {
		_slot * found_slot = _find_slot(key);

		assert(!strcmp(found_slot->key, key));

		if (!found_slot) 
			return false; // not found

		int hash_code = _hash(key);

		if (!strcmp(found_slot->key, _bucket[hash_code]->key)) { // if it is the head of the slot
			_bucket[hash_code] = found_slot->next;
		}

		if (_head == found_slot) { // if it is the head of the list
			_head = found_slot->list_next;
		}

		zz_delete found_slot;

		--_count;

		return true;
	}

	T find (const char * key) {
		_slot * found_slot = _find_slot(key);
		
		if (!found_slot) {
			return NULL;
		}
		return found_slot->data;
	}
	
	void dump (void) {
		_slot * found_slot = _head;

		ZZ_LOG("hash_table: dump(), size(%d)\n", _count);
		while (found_slot) {
			ZZ_LOG("%s, ", found_slot->key);
			found_slot = found_slot->list_next;
		}
		ZZ_LOG("\n\n");
	}

	int size (void) {
		return _count;
	}

	class iterator {
		friend zz_hash_table;
	private:
		_slot * _current;

	public:
		iterator() : _current(NULL) {}
		~iterator() {}

		iterator& operator++() {
			if (_current) {
				_current = _current->list_next;
			}
			return *this;
		}

		iterator& operator++(int i) {
			if (_current) {
				_current = _current->list_next;
			}
			return *this;
		}

		iterator& operator--() {
			if (_current) {
				_current = _current->list_prev;
			}
			return *this;
		}

		iterator& operator--(int i) {
			if (_current) {
				_current = _current->list_prev;
			}
			return *this;
		}

		bool operator!=(iterator& it) {
			return (it._current != _current);
		}

		bool operator==(iterator& it) {
			return (it._current == _current);
		}	

		T operator*() {
			if (_current) {
				return _current->data;
			}
			return NULL;
		}
	};

	iterator begin (void) {
		iterator it;
		it._current = _head;
		return it;
	}

	iterator end (void) {
		iterator it;
		it._current = NULL;
		return it;
	}

	void erase (iterator it) {
		remove(it._current->key);
	}

	void clear (void) {
		iterator it = begin();
		
		while (it != end()) {
			erase(it);
			it = begin();
		}
		assert(_count == 0);
		assert(!_tail && !_head);
	}
};


// usage:
/*
zz_hash_table tab(100);

tab.insert("one", 1);
tab.insert("two", 2);
tab.insert("three", 3);
tab.insert("four", 4);
tab.insert("five", 5);

int zho;

if (tab.find("five", zho)) {
	ZZ_LOG("main: tab.find (three = %d)\n", zho);
}
tab.remove("five");

if (!tab.find("five", zho)) {
	ZZ_LOG("main: tab.find failed.\n");
}
*/	
#endif // __ZZ_HASH_TABLE_H__
위로
사용자 정보 보기 쪽지 보내기 이메일 보내기 글 올린이의 웹사이트 방문
toki



가입: 2002년 4월 13일
올린 글: 151
소속: 대한민국
올리기음 성능 비교 좀 한 번 해주세요. 올려짐: 2002-08-18 20:37
인용과 함께 답변 이 게시물을 del.icio.us에 추가
저는 그냥 manager작성할때, stl::map사용해서 key값으로 string을
넣어서 쓰는데 그렇게 검색이 느리다고 생각이 되지는 않는데, 감자님
의 헤쉬알고리즘을 사용한 비교와 어느정도의 차이가 나는지 한 번쯤
성능 비교를 해주셨으면 감사하겠습니다.
이거 너무 염치가 없나요?
위로
사용자 정보 보기 쪽지 보내기 이메일 보내기
Gamza



가입: 2001년 10월 11일
올린 글: 610
올리기 올려짐: 2002-08-18 21:57
인용과 함께 답변 이 게시물을 del.icio.us에 추가
굳이 성능비교라 한다면 평균10회이던 문자열 비교가 1회로 줄어든다..정도..

단순한 이진탐색이 아닌 적흑트리를 사용하는 map일경우엔 평균적으로는 좀더 적은 비

교가 일어난다고하니 10회까지는 안갈지도 모르겠습니다.

어쨌든 오브젝트를 검색할때마다 10번 정도의 문자열비교라.....

프로파일러 돌려보고 문제가 안된다면 그냥 쌩까면 그만이지만....

그냥 좀 껄끄럽다는거죠.....

괜히 숫자ID같은걸 붙이고도 싶어지고....

숫자ID쓰기전에 해쉬를 한번 생각해 봄직하지 않을까 싶네요.
(문자열로 실컷짜놓구선 프로파일링해봤더니 걸리더라...이럴때도 간단히 적용이 되죠. 숫자ID로 바꾸려면 시스템 전체가 수정되어야 하는 사태가...)

^.^

감자 성수올림...@~

PS. 사실 문자열의 해쉬검색을 적용하게 된건....
회사에서 개발중이던 임베디드 시스템에서 파일시스템을 만들때 fopen이 느리다는
보고가 들어왔었기 때문입니다. ( 일본측... )
(아무래도 오락실에서 now loading....따위는......T.T)
그때도 문자열비교,이진탐색을 쓰긴했었는데....
어쨌든 해쉬를 쓰고나니 그에대해선 한번도 불평이 안나오더군요.

GPG에 나온 리소스를 하나의 파일에 넣는것 같은걸 구현할때도 응용할수 있지 않을까 싶습니다.
(파일내부에 있는 파일을 문자열로 검색해야 하니...)
_________________
HOME: http://www.Gamza.net
위로
사용자 정보 보기 쪽지 보내기 글 올린이의 웹사이트 방문 MSN 메신저
붉은미르
손님
올리기Good 올려짐: 2002-08-19 10:26
인용과 함께 답변 이 게시물을 del.icio.us에 추가
현재 게임적으로 심심풀이로 만들고 있는 코드에서 모든 것을 string으로 처리하고 있었습니다. 보기에 좋다는 이유만으로....
string으로 하면서도 한쪽으로 속도에 대한 불안감을 가지고 있습니다.

감자님에 한방으로 이런 불안감을 잠재워주시는 군요.
소스를 수정해야 겠습니다.


붉은미르는 반성해야 합니다.
해쉬 함수, 해쉬 테이블이라는 용어에만 익숙해져서 나태함에 빠졌습니다. 용어만 알면 아는 것 처럼 생각하다니....
감자님의 해쉬 함수로 해쉬라는 것에 대해서 함 공부해볼까하는 생각이 들었습니다. 비전산인의 비애....TT


붉은미
위로
toki



가입: 2002년 4월 13일
올린 글: 151
소속: 대한민국
올리기재미있네요. 올려짐: 2002-08-19 11:22
인용과 함께 답변 이 게시물을 del.icio.us에 추가
같은 내용이 flipcode ToTD란에 떠 있네요. -같다는 말이 코드가 똑같다라는 말이 아니라는 것은 다들 아시겠죠. 이상한 오해를 하시는 분들이 없겠죠. 너무 많이 당해서리 흑흑...

http://www.flipcode...forum=totd&id=-1

한 번 확인들 해보세요.
위로
사용자 정보 보기 쪽지 보내기 이메일 보내기
Gamza



가입: 2001년 10월 11일
올린 글: 610
올리기질문 올려짐: 2002-08-19 11:51
인용과 함께 답변 이 게시물을 del.icio.us에 추가
toki님이 링크해 놓으신곳에 가봤습니다.

아직은 공력이 부족한지..... 해쉬함수(size_t)가 언제 호출되는지 잘 모르겠네요..^.^;;

자칫잘못해서 비교할때마다 해쉬함수가 호출되거나 하면 큰일이라...

비교연산자(operator <,==) 안에 해쉬값이 전혀 사용되지 않는것 처럼 보이는것도 궁금..

마지막으로 그밑에 있는 리플은 문제가 좀 있는듯...

코드: 
then create a map 
to add: 
map[ Hash( "XBOX" ) ] = 20;


이것은 모든 스트링이 다른 해쉬값을 갖는다는 전제하에서만 제대로 동작할것 같은데...
_________________
HOME: http://www.Gamza.net
위로
사용자 정보 보기 쪽지 보내기 글 올린이의 웹사이트 방문 MSN 메신저
toki



가입: 2002년 4월 13일
올린 글: 151
소속: 대한민국
올리기implict conversion이네요 올려짐: 2002-08-19 13:16
인용과 함께 답변 이 게시물을 del.icio.us에 추가
operator size_t() const

일반적으로 type cast에 관한 overload라고 하죠. - 아닌가?

만약 임의의 class A작성하고서

내부 멤버중에 int멤버가 있는데 integer로 conversion했을때,

이 값을 주고 싶다면

operator int() const { return m_int; }이런식으로 하고

A a; ...
int i = a; 라고 하면 자동적으로 operator int()가 호출되지요.

모양을 보니 이것 같은데 size_t를 쓸 때가 있는지?
위로
사용자 정보 보기 쪽지 보내기 이메일 보내기
soaringhs



가입: 2001년 7월 30일
올린 글: 230
올리기hash_map<>의 hash functor 인듯... 올려짐: 2002-08-19 13:47
인용과 함께 답변 이 게시물을 del.icio.us에 추가
functor가 맞는 용어던가요? 아직도 C를 주로 쓰다보니 했갈리는군요. 책이 어디 있더라...... --;

STL Port의 _hash_fun.h 보니까...

코드: 
template  struct hash { };

inline size_t __stl_hash_string(const char* __s)
{
  _STLP_FIX_LITERAL_BUG(__s)
  unsigned long __h = 0; 
  for ( ; *__s; ++__s)
    __h = 5*__h + *__s;
  
  return size_t(__h);
}

_STLP_TEMPLATE_NULL struct hash
{
  size_t operator()(const char* __s) const { _STLP_FIX_LITERAL_BUG(__s) return __stl_hash_string(__s); }
};


flipcode의 HashString은 단지 __stl_hash_string(const char* __s)를 대신하겠다는것인데 그럼 VC7의 STL 해쉬함수가 더 비싸다는 예기밖에 안되는것 같네요.

VC7 사용하시는분들이 확인해 주시는것이...

-----
나중에 추가

flipcode에 있는것 다시 읽어보니 hash_map<std::string, int> map에서 키로 사용되는 std::string의 임시생성의 오버해드만 해결한것이군요.

해쉬함수하곤 상관 없는문제였네요...
위로
사용자 정보 보기 쪽지 보내기
Gamza



가입: 2001년 10월 11일
올린 글: 610
올리기해시함수 성능 테스트 올려짐: 2002-12-22 20:35
인용과 함께 답변 이 게시물을 del.icio.us에 추가
할일없어서....디렉토리를 뒤적뒤적거리다....전에 좀 찜찜했던 부분이 생각나서...

테스트를 해 보았습니다.

제일 위에 제가 만들어 사용했다던 해시함수와

지호님이 사용하신(플립코드에도 나와있는)해시 함수의 성능 비교죠..

아무래도 제가 날림으로 만든것 보다는 성능이 좋으리라 생각은 했습니다만....

....테스트 해보니 역시....공인된(?)것이 확실히 좋더군요

괜히 잔머리 굴리지 말고 퍼다 쓸걸 그랬나 봅니다.

70000개의 파일명을 벡터에 정렬해서 넣어두고 모든 문자열을 한번씩 검색해

보는 테스트를 해보았습니다. 아래는 문자열 비교 횟수입니다.

해시함수 사용안함: 최대17 / 평균16.15 회
제가 만들었다던 해시함수: 최대 4 / 평균1.012 회
플립코드에 나온 해시함수: 최대 2 / 평균1.000028 회

만들기전에 이미 충분히 연구되어 사용되는것이 있는지 알아보라는것을

다시한번 깨닫는 순간이었습니다.

괜히 찾아다니지 않게 함수도 같이 올리죠..
(사실 지호님 소스에도...지호님글 링크에도...위에 링크된 플립코드에도...다 있습니다만...ㅡ.ㅡ;;; )

코드: 
unsigned long GetHashCode( const char* pString )
{
	unsigned long i,len;
	unsigned long ch;
	unsigned long result;
	
	len     = strlen( pString );
	result = 5381;
	for( i=0; ihash * 33 + ch
	}	

	return result;
}


PS. 이거 테스트 하면서 이것과 더불어 올렸던 binary_find 의 구현상 주의할점도 발견하게 되었습니다.
그건 binary_find에 따로 올리죠.
_________________
HOME: http://www.Gamza.net
위로
사용자 정보 보기 쪽지 보내기 글 올린이의 웹사이트 방문 MSN 메신저
류광



가입: 2001년 7월 25일
올린 글: 3413
소속: GPGstudy
타 사이트 ID(?):
docbook.kr::류광
올리기 올려짐: 2002-12-23 01:26
인용과 함께 답변 이 게시물을 del.icio.us에 추가
역시 찾아다니는 수고를 덜기 위해.... 감자님의 binary_find 관련 글은 http://www.gpgstudy...opic.php?p=4232#4232 입니다.

처음에 이 주제를 읽었을 때에는 이해가 잘 안 되었는데 binary_find 글의 compare()를 다시 보니 이제 조금 이해가 될 것 같습니다... 위에 나온 해시함수의 핵심은 "해시코드가 문자열의 순서와 일치한다"라는 것이죠?

추가:

아 여전히 잘 모르겠습니다... 위의 질문은 전적으로 compare()만 보고 한 이야기이구요... ( 그렇지 않다면 compare()의 로직이 이상한 것일테니까요..)

왼쪽으로 계속 5 비트씩 시프트하다보면 한 바퀴 돌 경우가 생길텐데 아리송...
위로
사용자 정보 보기 쪽지 보내기 글 올린이의 웹사이트 방문
Gamza



가입: 2001년 10월 11일
올린 글: 610
올리기 올려짐: 2002-12-23 09:45
인용과 함께 답변 이 게시물을 del.icio.us에 추가
해시코드 순서와 문자열 순서는 연관성없습니다.

문자열 검색시 같은 해시 코드를 갖는 문자열끼리만 문자열 비교를 사용하자는게 해시코드의 목적이죠.
(해시코드로 문자열을 일단분류......우편번호 같은......)

문자열 정렬이 필요하다면 Hashed string을 사용하면 곤란.

binary_find 역시 문자열 검색시 STL을 사용할경우 최소 2회의 문자열

비교를 해야하는 문제를 해결하려는 일관된 목적하에 생겨난 겁니다.
_________________
HOME: http://www.Gamza.net
위로
사용자 정보 보기 쪽지 보내기 글 올린이의 웹사이트 방문 MSN 메신저
류광



가입: 2001년 7월 25일
올린 글: 3413
소속: GPGstudy
타 사이트 ID(?):
docbook.kr::류광
올리기 올려짐: 2002-12-24 16:04
인용과 함께 답변 이 게시물을 del.icio.us에 추가
그래도.. 그래도...

해시코드가 같은 원소들은 문자열 순서로 들어 있어야 하지 않나요????(binary_find 관련해서요)

맞다고 해주세요ㅠ.ㅠ

추가: 원소들을 정렬할 때 반드시 binary_find에 사용하는 비교함수를 사용해야 한다는 전제조건이 존재하는지 확인해 주시길!
위로
사용자 정보 보기 쪽지 보내기 글 올린이의 웹사이트 방문
Gamza



가입: 2001년 10월 11일
올린 글: 610
올리기 올려짐: 2002-12-24 16:58
인용과 함께 답변 이 게시물을 del.icio.us에 추가
맞습니다....^^

binary_find를 사용하려면 compare를 가지고 정렬을 해야하죠

해시코드가 같은 넘끼리 정렬되어 들어가는건 compare가 그렇게 되어있기 때문에 자연히 그렇게 들어감..

말씀드리려고 했던건 '해시코드가 문자열의 순서와 일치하지는 않는다.' 는것.
_________________
HOME: http://www.Gamza.net
위로
사용자 정보 보기 쪽지 보내기 글 올린이의 웹사이트 방문 MSN 메신저
손님
손님
올리기감자님... 올려짐: 2003-01-07 17:17
인용과 함께 답변 이 게시물을 del.icio.us에 추가
< 연산자를 재정의 한것은... 얻어진
해쉬값이 strcmp에서 리턴되는... -1, 0, 1의...
그러니까.. 크기(문자열상의...음.. 스펠링으로 인한 크느냐 작느냐..무슨뜻인지..
아시겠져?? ^^)를 보장한다는 뜻인가요?
해쉬값을 가지고 크기검사를 하면 strcmp의 만약 작다면 -1이 오는 똑같은
구현을 할수있는지.... 보통 문자열소트할때 쓰이는...
그것이 보장되는지요?
위로
zelong
손님
올리기스트링 비교속도 올려짐: 2003-01-07 18:00
인용과 함께 답변 이 게시물을 del.icio.us에 추가
음, 저희 게임에서도 리소스관리를 할 때 문자열이냐 ID냐 라는 문제에 봉착한 적이 있는데, 결론은 문자열이었습니다.

당시 테스트를 한 결과

AMD Athlon XP 1700+ 정도의 컴퓨터에서
평균문자열재검사 회수가 10.446746 번이라고 하면
한 번의 검사에 걸리는 평균시간이 0.000011초 로 나오더군요.

사실 저 수가 너무 작아서 -게다가 평균치이고- 오히려 저것보다
빠르리라는 생각도 가능하게 했습니다. 참고로 1번검사부터 10번검사
모두 저 비슷한 숫자가 나오는 걸로 봐서 실제 부하보다는 다른 부하가
끼인 시간이 아닌가 생각되더군요.

물론 0.000011 이라는 숫자도 아까우리만치 엄청난 DB를 자랑하는
게임이라면-_-; 할 말 없습니다만. (그 때는 정말로 DB를 쓰든지 설계해야...)

감자 님께서 올려주신 해쉬... 그러니까 std::map 정도만 써도 충분히 빠르리라
생각되네요. (워낙 머신스피드가 올라가놔서...)



..음-_-; 테스트가 잘못 되었을지도 모르지만... 어쨌든 빠릅니다.
위로
opaque
손님
올리기그래도.. ^^ 올려짐: 2003-01-07 18:58
인용과 함께 답변 이 게시물을 del.icio.us에 추가
저는 조금 고생해서라도 가능하면 배열 index로 접근할 수 있는 코드를 만드는게 좋다고 생각합니다.

1. hash table 관련 function 호출 overhead (여러 함수가 호출되겠죠)
2. bucket collision 처리 (eg> 2차 hash, binary search, linear search)

흐흐.. 속도 차가 1000배쯤 나지 않을까요?
위로
Gamza



가입: 2001년 10월 11일
올린 글: 610
올리기문자열비교 속도문제 올려짐: 2003-01-08 06:24
인용과 함께 답변 이 게시물을 del.icio.us에 추가
전에 말씀드렸듯이
숫자ID쓰기전에 해쉬를 한번 생각해 보자....
라는정도로만 생각해 주세요.

문자열로 실컷짜놓구선 프로파일링해봤더니 걸리더라...
이럴때도 간단히 적용할수 있으니...

프로파일러 돌려보고 문자열비교가 문제가 없다 판단되면 그냥 문자열 비교하면 그만입니다.

PS. PC가 아닌 임베디드 시스템에서는 가능하면 숫자ID를 써야 겠지만...
경우에 따라 그렇지 못한경우도 있습니다. 이럴때도 유용하겠죠.
(위에 말씀드린 파일시스템 구성이라던가...)
_________________
HOME: http://www.Gamza.net
위로
사용자 정보 보기 쪽지 보내기 글 올린이의 웹사이트 방문 MSN 메신저
zelong
손님
올리기선택 올려짐: 2003-01-08 11:11
인용과 함께 답변 이 게시물을 del.icio.us에 추가
듣고보니, PC가 아닌 시스템에서는 약간 불편할지라도 분명 유용하겠네요. 기계성능이 워낙 떨어질테니 코드 자체의 덩치도 크지 않을테고, 데이타의 흐름도 훨씬 단순명확할테고 말입니다. 그러하다면 숫자탐색은 쓸만한 것 같습니다.

파일 시스템 말인데요. 사실 엄청나게 늘어날 온라인게임 리소스파일들의 개수를 감안해서 파일시스템 자체를 그룹화시켰더니 많아야 300-400개의 리스트를 탐색하게 되더군요. 그룹의 탐색속도는 그룹수 자체가 많지 않아 거의 시간이 들지 않고, 많아야 300-400개인 리스트에서 이진탐색에는 6-7회, 해쉬로 만들면 그것조차도 거의 줄여버리니... (실수로 프로그래머가 그룹을 너무 많이 읽는 걸 방지하기 위해 Managed 모드도-_-

여튼, 스트링 탐색 좋십니다 >.<;
숫자기반 탐색도 멋들어진 시스템이 존재하면 그것도 멋있을듯; (하지만 쉽지 않...)
위로
이전 글 표시:   
잠김[?]    GpgStudy 게시판 인덱스 -> 프로그래밍 일반 시간대: GMT + 9 시간(한국)
페이지로 1, 2  다음
페이지 1 중 2

이 주제에 대한 트랙백 주소: (참고)

글 잇기(시험중): |

 
건너뛰기:  
새로운 주제를 올릴 수 없습니다
답글을 올릴 수 없습니다
주제를 수정할 수 없습니다
올린 글을 삭제할 수 없습니다
투표를 할 수 없습니다


Powered by phpBB © 2001, 2005 phpBB Group