|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vladimir A. Pertzel 2:5020/400 30 Jun 2002 13:14:05
To : All
Subject : Re: поиск подстpоки в таблице
--------------------------------------------------------------------------------
Вот вам два алгоритма: стандартный, STL-овский, с hash_set и дерево,
где алфавит хеширован (для экономии памяти). Решается задача проверки
поступившего на вход интернет-адреса в таблице 30000 интернет-адресов
Две тестовых программы hashstr и stree (компилировалось на LINUX)
Дерево вдвое быстрее, а кто жрет больше памяти, сказать трудно.
Для подгонки к своим нуждам, менять прежде всего, hashTable[256].
=================================================
g++ -O -c -o stree.o stree.cpp
g++ -O -c -o StrTree.o StrTree.cpp
g++ -O -o stree stree.o StrTree.o
g++ -O -o hashstr hashstr.cpp
=================================================
// file hashstr.cpp
#include <stdlib.h>
#include <sys/time.h>
#include <unistd.h>
#include <set>
#include <hash_set>
struct eqstr {
bool operator()(const char* s1, const char* s2) const {
return strcmp(s1, s2) == 0;
}
};
int main(int argc, char* argv[])
{
struct timeval time1, time2;
int i,j;
char teststrings[60000][20];
////////////////////////////////
cout << "preparing random strings... " ;
for ( i=0; i<30000; ++i ) {
for ( j=0 ; j<19 ; ++j ) {
teststrings[i][j]=j='a'+(int) (26.0*rand()/(RAND_MAX+1.0));
}
teststrings[i][19]=0;
}
cout << "finished!" << endl;
////////////////////////////////
cout << "started insertion into a hash... ";
gettimeofday(&time1, 0);
hash_set<const char*, hash<const char*>, eqstr> strDataHash;
for ( i=0; i<30000; ++i )
strDataHash.insert(teststrings[i]);
gettimeofday(&time2, 0);
cout << "finished!" << endl;
cout << (( time2.tv_usec - time1.tv_usec ) > 0 ?
time2.tv_sec - time1.tv_sec : time2.tv_sec - time1.tv_sec -1 )
<< " seconds " << (( time2.tv_usec - time1.tv_usec > 0 ) ?
time2.tv_usec - time1.tv_usec :
1000 - time2.tv_usec + time1.tv_usec)
<< " milliseconds." << endl;
cout << "started lookup in the hash correct strings ... ";
gettimeofday(&time1, 0);
for ( i=0; i<30000; ++i )
strDataHash.find(teststrings[i]);
gettimeofday(&time2, 0);
cout << "finished!" << endl;
cout << (( time2.tv_usec - time1.tv_usec ) > 0 ?
time2.tv_sec - time1.tv_sec : time2.tv_sec - time1.tv_sec -1 )
<< " seconds " << (( time2.tv_usec - time1.tv_usec > 0 ) ?
time2.tv_usec - time1.tv_usec :
1000 - time2.tv_usec + time1.tv_usec)
<< " milliseconds." << endl;
cout << "started lookup in the hash wrong strings ... ";
gettimeofday(&time1, 0);
for ( i=30000; i<60000; ++i )
strDataHash.find(teststrings[i]);
gettimeofday(&time2, 0);
cout << "finished!" << endl;
cout << (( time2.tv_usec - time1.tv_usec ) > 0 ?
time2.tv_sec - time1.tv_sec : time2.tv_sec - time1.tv_sec -1 )
<< " seconds " << (( time2.tv_usec - time1.tv_usec > 0 ) ?
time2.tv_usec - time1.tv_usec :
1000 - time2.tv_usec + time1.tv_usec)
<< " milliseconds." << endl;
////////////////////////////////
return 0;
}
// file hashstr.cpp ends
=================================================
// file stree.cpp
#include "StrTree.hpp"
#include <stdlib.h>
#include <sys/time.h>
#include <unistd.h>
int main(int argc, char* argv[])
{
struct timeval time1, time2;
int i,j;
char teststrings[60000][20];
////////////////////////////////
cout << "preparing random strings... " ;
for ( i=0; i<30000; ++i ) {
for ( j=0 ; j<19 ; ++j ) {
teststrings[i][j]=j='a'+(int) (26.0*rand()/(RAND_MAX+1.0));
}
teststrings[i][19]=0;
}
cout << "finished!" << endl;
////////////////////////////////
cout << "started insertion into a tree... ";
gettimeofday(&time1, 0);
StrTree strDataBase;
for ( i=0; i<30000; ++i )
strDataBase.insert(teststrings[i]);
gettimeofday(&time2, 0);
cout << "finished!" << endl;
cout << (( time2.tv_usec - time1.tv_usec ) > 0 ?
time2.tv_sec - time1.tv_sec : time2.tv_sec - time1.tv_sec -1 )
<< " seconds " << (( time2.tv_usec - time1.tv_usec > 0 ) ?
time2.tv_usec - time1.tv_usec :
1000 - time2.tv_usec + time1.tv_usec)
<< " milliseconds." << endl;
cout << "started lookup in the tree correct strings ... ";
gettimeofday(&time1, 0);
for ( i=0; i<30000; ++i )
strDataBase.lookup(teststrings[i]);
gettimeofday(&time2, 0);
cout << "finished!" << endl;
cout << (( time2.tv_usec - time1.tv_usec ) > 0 ?
time2.tv_sec - time1.tv_sec : time2.tv_sec - time1.tv_sec -1 )
<< " seconds " << (( time2.tv_usec - time1.tv_usec > 0 ) ?
time2.tv_usec - time1.tv_usec :
1000 - time2.tv_usec + time1.tv_usec)
<< " milliseconds." << endl;
cout << "started lookup in the tree wrong strings ... ";
gettimeofday(&time1, 0);
for ( i=30000; i<60000; ++i )
strDataBase.lookup(teststrings[i]);
gettimeofday(&time2, 0);
cout << "finished!" << endl;
cout << (( time2.tv_usec - time1.tv_usec ) > 0 ?
time2.tv_sec - time1.tv_sec : time2.tv_sec - time1.tv_sec -1 )
<< " seconds " << (( time2.tv_usec - time1.tv_usec > 0 ) ?
time2.tv_usec - time1.tv_usec :
1000 - time2.tv_usec + time1.tv_usec)
<< " milliseconds." << endl;
////////////////////////////////
return 0;
}
// file stree.cpp ends
=================================================
// file StrTree.cpp
#if !defined(_STRTREE_H__INCLUDED_)
#define _STRTREE_H__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include <iostream>
#include <list>
using namespace std;
class StrTree
{
typedef struct STB_Node { STB_Node* _node[39]; int _code; };
typedef list <STB_Node*> STB_Node_List;
STB_Node* _ready; // to be alloted next
STB_Node* _last; // the last of all nodes
STB_Node_List _toBeDestroyed;
long unsigned int _blocksize;
STB_Node* _root;
public:
StrTree();
virtual ~StrTree();
int insert(char*);
int lookup(char*);
};
#endif // !defined(_STRTREE_H__INCLUDED_)
// file StrTree.hpp ends
=================================================
// file StrTree.cpp
#include "StrTree.hpp"
StrTree::StrTree()
{
_blocksize=65536;
_root=(STB_Node*)calloc(_blocksize,sizeof(STB_Node));
_last=&(_root[_blocksize]);
_ready=_root;
_blocksize*=2;
_toBeDestroyed.push_front(_ready);
}
StrTree::~StrTree()
{
STB_Node_List::iterator it;
for ( it=_toBeDestroyed.begin() ; it!=_toBeDestroyed.end() ; ++it) {
if(*it)
free (*it);
}
}
static unsigned char hashTable[256]=
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 1, 38, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0,
0, 0, 0, 0, 0, 0, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37,
0, 0, 0, 0, 0, 0, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 };
int StrTree::insert(char* pattern) {
STB_Node* tmp =_root;
register char c;
for ( ; c = hashTable[*pattern] ; ++pattern ) {
register STB_Node* tmp1;
if ((tmp1=(STB_Node*)tmp->_node[c])!=0) {
tmp=tmp1;
}
else {
tmp->_node[c]=_ready;
tmp=(STB_Node*)tmp->_node[c];
++_ready;
if (_ready==_last) {
if ((_ready=(STB_Node*)calloc(_blocksize,sizeof(STB_Node)))==0)
return 0;
_last=&(_ready[_blocksize]);
_blocksize*=2;
_toBeDestroyed.push_front(_ready);
}
}
}
tmp->_code=1;
return 1;
}
int StrTree::lookup(char* pattern) {
STB_Node* tmp =_root;
register char c;
for ( ; c = hashTable[*pattern] ; ++pattern ) {
if ((tmp=tmp->_node[c])==0)
return 0;
}
return (tmp->_code);
}
// file StrTree.cpp ends
=================================================
--- ifmail v.2.15dev5
* Origin: Sent via Graf's Inn at news://news.relhum.org (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: поиск подстpоки в таблице 