Forum Programowanie c++, delphi Ostatnio aktywny: Nigdy
Nie zalogowany [Zaloguj ]
Pokaż koniec
Wersja do druku | Zapisz | Dodaj do Ulubionych   Wyślij nową wiadomość Sonda:
Autor: Temat: [C++] HashSet()
Sorror
Coder
***


Avatar


Postów: 229
Zarejestrowano: 17-12-2005
Miasto: New York/Wrocław
Offline


[*] wysłano w 25-1-2006 o godz. 13:00 Odpowiedz cytując
[C++] HashSet()



A oto Cepepowa implementacja hashsetu, zaczerpnięta z javy. Implementacja kubełkowa, po referencję zapraszam do doca javowego hashsetu.


timer.h


Kod:

#ifndef a_timer
#define a_timer

class timer_class{

double priv_all_time;
long priv_go, priv_stop;
double priv_difference_time;

public:
timer_class();
void clear_();
void go_();
void stop_();
double difference_time();
double all_time()
};

#endif



randomize.h


Kod:

#ifndef randomize_h
#define randomize_h

class randomize_
{

private:
static int priv_go_randomize;
public:

randomize_();

randomize_(int seed);

int randomize_integer(int up);

double randomize_custom(double down, double up);

int randomize_integer(int down, int up);

double randomize_custom();
};

#endif



HashSet.cpp


Kod:

#include <iostream>
#include <math>
#include <fstream>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <cstring>

#include "timer.h"
#include "randomize.h"


using namespace std;


class HashSet
{

struct bytes_link{
char * byte_pointer;
bytes_link * next;
bytes_link(char * s, bytes_link * link){
byte_pointer = s;
next = link;
}
};

unsigned int code(char *);
static const int hash_table = 2000; //i don't know how big may it be, se rox
bytes_link * handle_table[hash_table];

int handle_weight;

public:
HashSet();
bool add(char * s);
int weight() const;

char ** getArray() const;
};

HashSet::HashSet()
{

for(int k=0; k < hash_table; k++){
handle_table[k] = NULL;
}
handle_weight = 0;
}


unsigned int HashSet::code(char * s){

int code = 0;
int len = strlen(s);
for (int k = 0; k < len; k++) {
code = 32*code + s[k];
}
return code;
}


bool HashSet::add(char * s){

int mod = code(s) % hash_table;
bytes_link * list = handle_table[mod];
while (list != 0){
if (strcmp(s,list->byte_pointer) == 0){
return false;
}
list = list->next;
}

char * copy = new char[strlen(s)+1];
strcpy(copy,s);
handle_table[mod] = new bytes_link(copy,handle_table[mod]);
handle_weight++;
return true;
}

int HashSet::size() const{
return handle_weight;
}

char ** HashSet::getArray() const {

char ** array = new char *[handle_weight];
int count = 0;
for(int k=0; k < hash_table; k++){
bytes_link * list = handle_table[k];
while (list != 0){
array[count++] = list->byte_pointer;
list = list->next;
}
}
if (count != handle_weight){
cout << "cant cp " << count
<< " weight = " << handle_weight << endl;
}
return array;
}

class searching_
{
private:
char ** bool_strings;
int handle_weight;
randomize_ priv_randomize;

public:
void go_init(char * filename);
void geometric_search(int counting);
void binary_search(int counting);
};

static bool stringcompare(char * a, char * b){
return strcmp(a,b) < 0;
}


void searching_::go_init(char * filename){

timer_class timer;
timer.go_();
ifstream input(filename);
int total = 0;
char buffer[2000];
int count = 0;
HashSet the_one;
bool string_input = false;
char strun;
while (input.get(strun)){
strun = tolower(strun);
if (isspace(strun)){
if (string_input){
buffer[count++] = '';
the_one.add(buffer);
string_input = false;
total++;
count = 0;
}
}
else {
string_input = true;
buffer[count++] = strun;
}
}
if (string_input){
buffer[count++] = '';
the_one.add(buffer);
total++;
}
bool_strings = the_one.getArray();
handle_weight = the_one.weight();
timer.stop_();
int ulen = the_one.weight();
cout << "go read " << total << " strings " << ulen << " uni" << endl;
cout << "time " << timer.priv_difference_time() << endl;
timer.go_();

sort(bool_strings, bool_strings+ulen,stringcompare);
timer.stop_();
cout << "sorting time " << timer.priv_difference_time() << endl;
}

void searching_::geometric_search(int counting) {
timer_class timer;
timer.go_();
for(int k=0; k < counting; k++){
int index = priv_randomize.randomize_integer(handle_weight);
char * key = bool_strings[index];
for(int j=0; j < handle_weight; j++){
if (strcmp(bool_strings[j],key) == 0) {
if (j != index){
cout << "error at " << index << endl;
}
break;
}
}
}
timer.stop_();
cout << "time of " << counting << " the_one searching " << timer.priv_difference_time() << endl;
}

void searching_::binary_search(int counting){
timer_class timer;
timer.go_();
for(int k=0; k < counting; k++){
int index = priv_randomize.randomize_integer(handle_weight);
char ** it = lower_bound(bool_strings, bool_strings+handle_weight,
bool_strings[index], stringcompare);
if (strcmp(*it,bool_strings[index]) != 0){
cout << "error at " << index << endl;
}
}
timer.stop_();
cout << "time of " << counting << " binary string searching " << timer.priv_difference_time() << endl;
}


int main(int argc, char *argv[])
{
string filename,line, w;
if (argc != 3)
{
cerr << "adr " << argv[0] << "bufffile count" << endl;
exit(1);
}

searching_ main_search;
main_search.go_init(argv[1]);
int count = atoi(argv[2]);
main_search.binary_search(count);
main_search.geometric_search(count);


return 0;
}


CC License.




Pokaż profil użytkownika Pokaż wszystkie wiadomości użytkownika Użytkownik U2U Ten użytkownik posiada komunikator Gadu-Gadu
Wyślij nową wiadomość Sonda:


Pokaż początek

Sitemap
Copyright © 2005-2007 by coding-portal.com
Programowaniedla każdego. Programowanie w c++, java, delphi, pascal, perl oraz innych językach. Tworzenie stron w html, xhtml, php z użyciem mysql, css oraz ich pozycjonowanie. Zapraszamy do udziału w życiu naszego forum!
[zapytań: 15]
[PHP: 61.2% - SQL: 38.8%]