Тема: Подвійне хешування
Привіт!
Мені поставили завдання реалізувати хеш-таблицю з використанням подвійного хешування. Моя програма працює, і, здається, без помилок. Але єдине - додавання нових елементів (особливо у великій кількості - потрібно 100 000) виконується дуже повільно.
Чи не могли б ви допомогти розібратися, як краще оптимізувати цю функцію (void DoubleHashing<E, X>::add(const E e[], size_t len))?
Дякую.
Ось код:
DoubleHashing.h - файл з реалізацією
#ifndef DOUBLEHASHING_H
#define DOUBLEHASHING_H
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include "Container.h"
using namespace std;
class EmptyExc : public ContainerException
{
public:
virtual const char* what() const throw()
{
return "empty";
}
};
class PrimExc : public ContainerException
{
public:
virtual const char* what() const throw()
{
return "max_prim";
}
};
template <typename E, size_t X = 7>
class DoubleHashing : public Container<E>
{
size_t nmax;
size_t n;
double maxbelfak;
class HashElement
{
public:
size_t status;
E data;
size_t hash;
HashElement() //: data()
{
status = 0; hash = 0;
}
~HashElement()
{
}
void fill(const E e, unsigned int h)
{
hash = h; status = 1; data = e;
}
};
HashElement * value;
public:
DoubleHashing<E, X>()
{
value = new HashElement[X]; n = 0; nmax = X;
maxbelfak = 0.7;
}
virtual ~DoubleHashing<E, X>()
{
delete[] value;
}
using Container<E>::add;
virtual void add(const E e[], size_t len);
void rehash(const E e[], size_t len);
using Container<E>::remove;
virtual void remove(const E e[], size_t s);
virtual bool member(const E& e) const;
void ocbigger(size_t n, size_t nmax);
virtual size_t size() const
{
return n;
}
void Quicksort(E *a, size_t m) const
{
if (m < 2)
return;
E p = a[m / 2];
E *l = a;
E *r = a + m - 1;
while (r >= l) {
if (p > *l)
{
l++;
continue;
}
if (*r > p)
{
r--;
continue; // we need to check the condition (l <= r) every time we change the value of l or r
}
E t = *l;
*l++ = *r;
*r-- = t;
}
Quicksort(a, r - a + 1);
Quicksort(l, a + m - l);
}
virtual size_t apply(const Functor<E>& f, Order order) const
{
size_t x = 0;
size_t z = 0;
E *copyvalue;
if (n > 0)
{
if (order == dontcare)
{
for (z = 0; z < nmax; z++)
{
if (value[z].status == 1)
{
x++;
if (!f(value[z].data))
{
break;
}
}
}
}
else
{
copyvalue = new E[n];
for (z = 0; z < nmax; z++)
{
if (value[z].status == 1)
{
copyvalue[x] = value[z].data;
x++;
}
}
x = 0;
Quicksort(©value[0], n);
if (order == ascending)
{
for (size_t i = 0; i < n; i++)
{
x++;
if (!f(copyvalue[i]))
{
break;
}
}
}
if (order == descending)
{
for (size_t i = n; i > 0; i--)
{
x++;
if (!f(copyvalue[i - 1]))
{
break;
}
}
}
delete[] copyvalue;
}
}
return x;
}
virtual E min() const
{
if (this->empty()) throw EmptyExc();
else
{
E rc;
size_t j = 0;
for (j = 0; j < nmax; ++j)
{
if (value[j].status == 1)
{
rc = value[j].data;
break;
}
}
for (size_t i = j; i<nmax; i++)
{
if (value[i].status == 1 && rc > value[i].data)
{
rc = value[i].data;
}
}
return rc;
}
}
virtual E max() const
{
if (this->empty()) throw EmptyExc();
else
{
E rc;
size_t j = 0;
for (j = 0; j < nmax; ++j)
{
if (value[j].status == 1)
{
rc = value[j].data;
break;
}
}
for (size_t i = j; i<nmax; i++)
{
if (value[i].status == 1 && value[i].data > rc)
{
rc = value[i].data;
}
}
return rc;
}
}
virtual ostream& print(ostream& o) const;
};
size_t prime(size_t number)
{
size_t a = 2;
while (a < number)
{
if (number % a == 0)
{
return 0;
}
a++;
}
return 1;
}
size_t nextprime(size_t number)
{
size_t a = number + 1;
while (1)
{
if (a < ((size_t)-1))
{
if (!(prime(a) == 1))
{
a++;
}
else
{
break;
}
}
else
{
throw PrimExc();
}
}
return a;
}
template <typename E, size_t X>
void DoubleHashing<E, X>::add(const E e[], size_t len) // ось ця функція працює повільно
{
size_t hash1, hash2, hashg = 0;
size_t newnmax = nmax;
HashElement *a;
size_t q = 0;
if ((n + len) > (newnmax * maxbelfak))
{
HashElement * newvalue;
do
{
newnmax = nextprime(newnmax);
} while (newnmax < ((n + len) * 10));
newvalue = new HashElement[newnmax];
for (size_t i = 0; i < nmax; ++i)
{
if (value[i].status == 1)
{
hash1 = (value[i].hash) % newnmax;
hash2 = 1 + ((value[i].hash) % (newnmax - 2));
while (1)
{
hashg = (hash1 + (q*hash2)) % newnmax;
if (newvalue[hashg].status == 0)
{
newvalue[hashg].fill(value[i].data, value[i].hash);
q = 0;
break;
}
else
{
q++;
}
}
}
}
delete[] value;
value = new HashElement[newnmax];
for (size_t t = 0; t < newnmax; t++)
{
value[t] = newvalue[t];
}
delete[] newvalue;
nmax = newnmax;
}
for (size_t i = 0; i < len; ++i)
{
q = 0;
if (!member(e[i]))
{
hash1 = hashValue(e[i]) % nmax;
hash2 = 1 + (hashValue(e[i]) % (nmax - 2));
while (1)
{
hashg = (hash1 + (q*hash2)) % nmax;
a = &value[hashg];
if (a->status == 0)
{
value[hashg].fill(e[i], hashValue(e[i]));
n++;
break;
}
else
{
q++;
}
}
}
}
}
template <typename E, size_t X>
void DoubleHashing<E, X>::remove(const E e[], size_t s)
{
size_t hash1;
size_t hash2;
size_t hashg;
size_t q = 0;
for (size_t i = 0; i < s; ++i)
{
q = 0;
hash1 = hashValue(e[i]) % nmax;
hash2 = 1 + (hashValue(e[i]) % (nmax - 2));
for (size_t w = 0; w < nmax; w++)
{
hashg = (hash1 + (q*hash2)) % nmax;
if ((value[hashg].status == 1) && (value[hashg].data == e[i]))
{
value[hashg].status = 0;
n--;
break;
}
else
{
q++;
}
}
}
}
template <typename E, size_t X>
bool DoubleHashing<E, X>::member(const E& e) const
{
size_t hashg;
size_t hash1;
size_t hash2;
size_t q = 0;
size_t x = 0;
hash1 = hashValue(e) % nmax;
hash2 = 1 + (hashValue(e) % (nmax - 2));
for (size_t j = 0; j < nmax; ++j)
{
hashg = (hash1 + (q*hash2)) % nmax;
x++;
if (value[hashg].status == 1 && value[hashg].data == e)
{
return true;
}
else
{
q++;
}
}
return false;
}
template <typename E, size_t X>
ostream& DoubleHashing<E, X>::print(ostream& o) const
{
HashElement *p;
o << "Double Hashing [ n=" << n << " nmax=" << nmax << " value=";
for (size_t i = 0; i < nmax; ++i)
{
if (value[i].status == 1)
{
p = &value[i];
o << ' ' << p->data;
}
else
{
o << " .";
}
}
o << " ]";
return o;
}
#endif //DOUBLEHASHING_HContainer.h - допоміжний файл (має залишатися незмінним)
#ifndef CONTAINER_H
#define CONTAINER_H
#include <iostream>
enum Order
{
dontcare, ascending, descending
};
template <typename E> class Functor;
class ContainerException : public std::exception
{
public:
virtual const char* what() const throw() = 0;
};
template <typename E>
class Container
{
Container& operator=(const Container<E>&);
Container(const Container<E>&);
public:
Container()
{
}
virtual ~Container()
{
}
virtual void add(const E& e)
{
add(&e, 1);
}
virtual void add(const E e[], size_t s) = 0;
virtual void remove(const E& e)
{
remove(&e, 1);
}
virtual void remove(const E e[], size_t s) = 0;
virtual bool member(const E& e) const = 0;
virtual size_t size() const = 0;
virtual bool empty() const
{
return size() == 0;
}
virtual size_t apply(const Functor<E>& f, Order order = dontcare) const = 0;
virtual E min() const = 0;
virtual E max() const = 0;
virtual std::ostream& print(std::ostream& o) const = 0;
};
template <typename E>
inline std::ostream& operator<<(std::ostream& o, const Container<E>& c)
{
return c.print(o);
}
template <typename E>
class Functor
{
public:
virtual bool operator( )(const E& e) const = 0;
virtual ~Functor()
{
}
};
template <typename E> inline unsigned long hashValue(const E& e)
{
return (unsigned long)e;
} //e * 47114711UL
template <typename E> inline double doubleValue(const E& e)
{
return double(e);
}
template <typename E> inline unsigned long ordinalValue(const E& e)
{
return (unsigned long)e;
}
#endif //CONTAINER_Hsimpletest.cpp - виконуючий файл (також має залишатися незмінним)
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include "DoubleHashing.h"
#ifndef ETYPE
#define ETYPE int
#endif
//#define str(x) #x
const char helpstr[] =
"new ............................... create new Container\n"
"delete ............................ delete Container\n"
"add <key> [...] ................... add <key>(s) with Container::add( int )\n"
"remove <key> [...] ................ remove <key>(s) with Container::remove( int )\n"
"member <key> ...................... call Container::member( <key> )\n"
"size .............................. call Container::size()\n"
"empty ............................. call Container::empty()\n"
"min ............................... call Container::min()\n"
"max ............................... call Container::max()\n"
"print ............................. print container with operator<<()\n"
"apply [asc|desc|dontcare [<n>]] ... traverse container with PrintN functor\n"
"trace ............................. toggle tracing on/off\n"
"fadd <filename> ................... add values read from file <filename>\n"
"fremove <filename> ................ remove values read from file <filename>\n"
"radd [<n> [<seed>]] ............... add <n> random values, optionally reset generator to <seed>\n"
"rremove [<n> [<seed>]] ............ remove <n> random values, optionally reset generator to <seed>\n"
"quit .............................. quit program\n\n"
"arguments surrounded by [] are optional\n";
template <typename E>
class PrintN : public Functor<E>
{
std::ostream& o;
mutable int n;
public:
explicit PrintN(int n = 0, std::ostream& o = std::cout) : o(o), n(n)
{
}
explicit PrintN(std::ostream& o) : o(o), n(0)
{
}
bool operator()(const E& e) const
{
o << e << ' ';
return n <= 0 || --n;
}
};
void setrandom(int seed)
{
srand(seed);
}
template <typename E> E nextrandom()
{
return E(rand());
}
// Template-Spezialisierungen fuer Klasse std::string
template <> inline double doubleValue(const std::string& e)
{
double rc = 0.; for (size_t i = e.length(); i--;) rc /= 256., rc += e[i]; return rc;
}
template <> inline unsigned long hashValue(const std::string& e)
{
unsigned long rc = 0; for (size_t i = 0; i < e.length(); ++i) rc = rc * 13 + e[i]; return rc;
}
template <> std::string nextrandom()
{
const char* start = helpstr + rand() % sizeof helpstr;
while (!isalpha(*start)) if (*start) ++start; else start = helpstr;
const char* end = start + 1;
while (isalpha(*end)) ++end;
char buf[10];
sprintf(buf, "%d", rand() % 1000);
return std::string(start, end - start) += buf;
}
// Klasse Person mit allen fГјr die Verwendung als Container-Elementdatentyp noetigen Methoden und Funktionen
class Person
{
std::string vorname;
std::string nachname;
public:
Person()
{
}
Person(std::string vorname, std::string nachname) : vorname(vorname), nachname(nachname)
{
}
bool operator==(const Person& p) const
{
return vorname == p.vorname && nachname == p.nachname;
}
bool operator>(const Person& p) const
{
return nachname > p.nachname || (nachname == p.nachname && vorname > p.vorname);
}
std::ostream& print(std::ostream& o) const
{
return o << '[' << nachname << ", " << vorname << ']';
}
std::istream& read(std::istream& i)
{
return i >> vorname >> nachname;
}
friend double doubleValue<Person>(const Person& e);
friend unsigned long hashValue<Person>(const Person& e);
friend unsigned long ordinalValue<Person>(const Person& e);
};
inline std::ostream& operator<<(std::ostream& o, const Person& p)
{
return p.print(o);
}
inline std::istream& operator>>(std::istream& i, Person& p)
{
return p.read(i);
}
// Template-Spezialisierungen fuer Klasse Person
template <> inline double doubleValue(const Person& e)
{
return doubleValue(e.nachname);
}
template <> inline unsigned long hashValue(const Person& e)
{
return hashValue(e.nachname);
}
template <> Person nextrandom()
{
return Person(nextrandom<std::string>(), nextrandom<std::string>());
}
bool match(const std::string& s, const char * c)
{
return c && s.length() <= std::strlen(c) && s.compare(0, s.length(), c, s.length()) == 0;
}
int main()
{
Container<ETYPE>* c = 0;
bool traceIt = false;
std::cout.setf(std::ios_base::boolalpha);
while (true)
{
if (traceIt)
{
if (c)
{
std::cout << std::endl << "container: " << *c;
}
else
{
std::cout << std::endl << "no container";
}
}
std::cout << std::endl << "> ";
std::string cmdline;
if (!std::getline(std::cin, cmdline)) break;
std::istringstream cmdstream(cmdline);
std::string cmd;
cmdstream >> cmd;
try
{
if (cmd.length() == 0)
{
}
else if (match(cmd, "quit"))
{
break;
}
else if (match(cmd, "new"))
{
if (c)
{
std::cerr << "container exists, 'delete' it first";
}
else
{
// c = new DoubleHashing<ETYPE,13>;
c = new DoubleHashing<ETYPE>;
}
}
else if (match(cmd, "help") || cmd == "?")
{
std::cout << helpstr;
}
else if (match(cmd, "trace"))
{
std::cout << "trace " << ((traceIt = !traceIt) ? "on" : "off");
}
else if (!c)
{
std::cout << "no container (use 'new')";
}
else
{
ETYPE key;
if (match(cmd, "delete"))
{
delete c;
c = 0;
}
else if (match(cmd, "add"))
{
while (cmdstream >> key)
{
c->add(key);
}
}
else if (match(cmd, "remove"))
{
while (cmdstream >> key)
{
c->remove(key);
}
}
else if (match(cmd, "member"))
{
cmdstream >> key;
std::cout << "returns " << c->member(key);
}
else if (match(cmd, "size"))
{
std::cout << "returns " << c->size();
}
else if (match(cmd, "empty"))
{
std::cout << "returns " << c->empty();
}
else if (match(cmd, "min"))
{
std::cout << "returns " << c->min();
}
else if (match(cmd, "max"))
{
std::cout << "returns " << c->max();
}
else if (match(cmd, "print"))
{
std::cout << *c;
}
else if (match(cmd, "apply"))
{
int n = 0;
std::string order = "dontcare";
cmdstream >> order >> n;
size_t rc = c->apply(PrintN<ETYPE>(n), match(order, "ascending") ? ascending : match(order, "descending") ? descending : dontcare);
std::cout << "\nreturns " << rc;
}
else if (match(cmd, "fadd"))
{
std::string filename;
cmdstream >> filename;
std::ifstream keystream(filename.c_str());
while (keystream >> key)
{
c->add(key);
}
}
else if (match(cmd, "fremove"))
{
std::string filename;
cmdstream >> filename;
std::ifstream keystream(filename.c_str());
while (keystream >> key)
{
c->remove(key);
}
}
else if (match(cmd, "radd"))
{
int seed = -1, count = 1;
cmdstream >> count >> seed;
if (seed != -1) setrandom(seed);
while (count-- > 0) c->add(nextrandom<ETYPE>());
}
else if (match(cmd, "rremove"))
{
int seed = -1, count = 1;
cmdstream >> count >> seed;
if (seed != -1) setrandom(seed);
while (count-- > 0) c->remove(nextrandom<ETYPE>());
}
else
{
std::cout << cmd << "? try 'help'";
}
}
}
catch (ContainerException& e)
{
std::cout << "ContainerException " << e.what();
}
catch (std::exception& e)
{
std::cout << "Exception " << e.what();
}
catch (...)
{
std::cout << "OOPS!";
}
}
return 0;
}
