6
से धीमी है, मैंने प्रत्येक बार जटिलता की तुलना करने के लिए बाइनरी खोज, रैखिक खोज और एक हैश तालिका लागू की है। समस्या यह है कि किसी भी तरह, मेरी हैश तालिका बाइनरी खोज से बहुत धीमी है जब मैं प्राइम नंबर खोजने के लिए समय मापता हूं।मेरी हैश तालिका द्विआधारी खोज
// Make the hash table 20 times the number of prime numbers
HashTable::HashTable(std::vector<int> primes)
{
int tablesize = primes.size() * 20;
table = new std::list<int>[tablesize];
size = tablesize;
for (auto &prime : primes)
this->insert(prime);
}
// Hash function
int HashTable::hash(int key)
{
return key % size;
}
// Finds element
int HashTable::find(int key)
{
// Get index from hash
int index = hash(key);
// Find element
std::list<int>::iterator foundelement = std::find(table[index].begin(), table[index].end(), key);
// If element has been found return index
// If not, return -1
if (foundelement != table[index].end())
return index;
else
return -1;
}
// Adds element to hashtable
void HashTable::insert(int element)
{
// Get index from hash and insert the element
int index = hash(element);
table[index].push_back(element);
}
HashTable.h
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include <list>
#include <iostream>
#include <vector>
class HashTable
{
private:
// Each position in Hashtable has an array of lists to store elements in case of collision
std::list<int>* table;
// Size of hashtable
int size;
// Hashfunction that returns the array location for the given key
int hash(int key);
public:
HashTable(int tablesize);
HashTable(std::vector<int> primes);
// Adds element to hashtable
void insert(int element);
// Deletes an element by key
void remove(int key);
// Returns an element from hashtable for a given key
int find(int key);
// Displays the hashtable
void printTable();
// Display histogram to illustrate elements distribution
void printHistogram();
// Returns the number of lists in hash table
int getSize();
// Returns the total number of elements in hash table
int getNumberOfItems();
// De-allocates all memory used for the Hash Table.
~HashTable();
};
#endif
मैं पहले से ही टकराव को खत्म करने के तालिका आकार के आकार को पार करने की कोशिश की है, लेकिन मैं किसी भी अंतर नोटिस नहीं किया: नीचे मेरी कोड है।
यह एक बहुत अच्छा ग्राफ है। ऐसा लगता है कि कोई उम्मीद करेगा: हैश खोज में निरंतर समय जटिलता है, और बाइनरी में लॉगरिदमिक है। यह सिर्फ हैश टेबल की स्थिरता काफी बड़ी है। वेक्टर कैश के साथ बहुत अच्छी तरह से खेलते हैं। – PSkocik
बेंचमार्क से शायद असंबंधित; लेकिन कन्स्ट्रक्टर को संदर्भ –
द्वारा 'primes' स्वीकार करना चाहिए यदि आप 'table' के प्रकार को' std :: vector *' में बदलते हैं तो आपके समय का क्या होता है? –
msandiford