I need to create MultiMap using hash-table but I get time-limit exceeded error (C++)

Question

I'm trying to solve algorithm task: I need to create MultiMap(key,(values)) using hash-table. I can't use Set and Map libraries. I send code to testing system, but I get time-limit exceeded error on test 20. I don't know what exactly this test contains. The code must do following tasks:

put x y - add pair (x,y).If pair exists, do nothing.

delete x y - delete pair(x,y). If pair doesn't exist, do nothing.

deleteall x - delete all pairs with first element x.

get x - print number of pairs with first element x and second elements.

The amount of operations <= 100000

Time limit - 2s

Example:

multimap.in:

put a a

put a b

put a c

get a

delete a b

get a

deleteall a

get a

multimap.out:

3 b c a

2 c a

0

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

inline long long h1(const string& key) {
    long long number = 0;
    const int p = 31;
    int pow = 1;
    for(auto& x : key){
        number += (x - 'a' + 1 ) * pow;
        pow *= p;
    }
    return abs(number) % 1000003;
}

 inline void Put(vector<vector<pair<string,string>>>& Hash_table,const long long& hash, const string& key, const string& value) {
    int checker = 0;
    for(int i = 0; i < Hash_table[hash].size();i++) {
        if(Hash_table[hash][i].first == key && Hash_table[hash][i].second == value) {
                checker = 1;
            break;
        }
    }
    if(checker == 0){
        pair <string,string> key_value = make_pair(key,value);
        Hash_table[hash].push_back(key_value);
    }
}
 inline void Delete(vector<vector<pair<string,string>>>& Hash_table,const long long& hash, const string& key, const string& value) {
    for(int i = 0; i < Hash_table[hash].size();i++) {
        if(Hash_table[hash][i].first == key && Hash_table[hash][i].second == value) {
            Hash_table[hash].erase(Hash_table[hash].begin() + i);
            break;
        }
    }
}

  inline void Delete_All(vector<vector<pair<string,string>>>& Hash_table,const long long& hash,const string& key) {
    for(int i = Hash_table[hash].size() - 1;i >= 0;i--){
        if(Hash_table[hash][i].first == key){
            Hash_table[hash].erase(Hash_table[hash].begin() + i);
        }
    }
}
inline string Get(const vector<vector<pair<string,string>>>& Hash_table,const long long& hash, const string& key) {
    string result="";
    int counter = 0;
    for(int i = 0; i < Hash_table[hash].size();i++){
        if(Hash_table[hash][i].first == key){
            counter++;
            result += Hash_table[hash][i].second + " ";
        }
    }
    if(counter != 0)
        return to_string(counter) + " " + result + "\n";
    else
        return "0\n";

}

int main() {
    vector<vector<pair<string,string>>> Hash_table;
    Hash_table.resize(1000003);
    ifstream input("multimap.in");
    ofstream output("multimap.out");
    string command;
    string key;
    int k = 0;
    string value;
     while(true) {
        input >> command;
        if(input.eof())
            break;
        if(command == "put") {
            input >> key;
            long long hash = h1(key);
            input >> value;
            Put(Hash_table,hash,key,value);
        }
        if(command == "delete") {
            input >> key;
            input >> value;
            long long  hash = h1(key);
            Delete(Hash_table,hash,key,value);
        } 
        if(command == "get") {
            input >> key;
            long long  hash = h1(key);
            output << Get(Hash_table,hash,key);
        }
        if(command == "deleteall"){
            input >> key;
            long long hash = h1(key);
            Delete_All(Hash_table,hash,key);
        } 
    }  
}

How can I do my code work faster?

Answer 1

At very first, a matter of design: Normally, one would pass the key only to the function and calculate the hash within. Your variant allows a user to place elements anywhere within the hash table (using bad hash values), so user could easily break it.

So e. g. put:

using HashTable = std::vector<std::vector<std::pair<std::string, std::string>>>;

void put(HashTable& table, std::string& key, std::string const& value)
{
    auto hash = h1(key);
    // ...
}

If at all, the hash function could be parametrised, but then you'd write a separate class for (wrapping the vector of vectors) and provide the hash function in constructor so that a user cannot exchange it arbitrarily (and again break the hash table). A class would come with additional benefits, most important: better encapsulation (hiding the vector away, so user could not change it with vector's own interface):

class HashTable
{
public:
    // IF you want to provide hash function:
    template <typename Hash>
    HashTable(Hash hash) : hash(hash) { }

    void put(std::string const& key, std::string const& value);
    void remove(std::string const& key, std::string const& value); //(delete is keyword!)
    // ... 
private:
    std::vector<std::vector<std::pair<std::string, std::string>>> data;

    // if hash function parametrized:
    std::function<size_t(std::string)> hash; // #include <functional> for
};

I'm not 100% sure how efficient std::function really is, so for high performance code, you preferrably use your hash function h1 directly (not implenting constructor as illustrated above).

Coming to optimisations:

For the hash key I would prefer unsigned value: Negative indices are meaningless anyway, so why allow them at all? long long (signed or unsigned) might be a bad choice if testing system is a 32 bit system (might be unlikely, but still...). size_t covers both issues at once: it is unsigned and it is selected in size appropriately for given system (if interested in details: actually adjusted to address bus size, but on modern systems, this is equal to register size as well, which is what we need). Select type of pow to be the same.

deleteAll is implemented inefficiently: With each element you erase you move all the subsequent elements one position towards front. If you delete multiple elements, you do this repeatedly, so one single element can get moved multiple times. Better:

auto pos = vector.begin();
for(auto& pair : vector)
{
    if(pair.first != keyToDelete)
        *pos++ = std::move(s); // move semantics: faster than copying!
}
vector.erase(pos, vector.end());

This will move each element at most once, erasing all surplus elements in one single go. Appart from the final erasing (which you have to do explicitly then), this is more or less what std::remove and std::remove_if from algorithm library do as well. Are you allowed to use it? Then your code might look like this:

auto condition = [&keyToDelete](std::pair<std::string, std::string> const& p)
                 { return p.first == keyToDelete; };
vector.erase(std::remove_if(vector.begin(), vector.end(), condition), vector.end());

and you profit from already highly optimised algorithm.

Just a minor performance gain, but still: You can spare variable initialisation, assignment and conditional branch (the latter one can be relatively expensive operation on some systems) within put if you simply return if an element is found:

//int checker = 0;
for(auto& pair : hashTable[hash]) // just a little more comfortable to write...
{
    if(pair.first == key && pair.second == value)
        return;
}
auto key_value = std::make_pair(key, value);
hashTable[hash].push_back(key_value);

Again, with algorithm library:

auto key_value = std::make_pair(key, value);
// same condition as above!
if(std::find_if(vector.begin(), vector.end(), condition) == vector.end();
{
    vector.push_back(key_value);
}

Then less than 100000 operations does not indicate that each operation will require a separate key/value pair. We might expect that keys are added, removed, re-added, ..., so you most likely don't have to cope with 100000 different values. I'd assume your map is much too large (be aware that it requires initialisation of 100000 vectors as well). I'd assume a much smaller one should suffice already (possibly 1009 or 10007? You might possibly have to experiment a little...).

Keeping the inner vectors sorted might give you some performance boost as well:

• put: You could use a binary search to find the two elements in between a new one is to be inserted (if one of these two is equal to given one, no insertion, of course)
• delete: Use binary search to find the element to delete.
• deleteAll: Find upper and lower bounds for elements to be deleted and erase whole range at once.
• get: find lower and upper bound as for deleteAll, distance in between (number of elements) is a simple subtraction and you could print out the texts directly (instead of first building a long string). Which of outputting directly or creating a string really is more efficient is to be found out, though, as outputting directly involves multiple system calls, which in the end might cost previously gained performance again...

Considering your input loop:

Checking for eof() (only) is critical! If there is an error in the file, you'll end up in an endless loop, as the fail bit gets set, operator>> actually won't read anything at all any more and you won't ever reach the end of the file. This even might be the reason for your 20th test failing.

Additionally: You have line based input (each command on a separate line), so reading a whole line at once and only afterwards parse it will spare you some system calls. If some argument is missing, you will detect it correctly instead of (illegally) reading next command (e. g. put) as argument, similarly you won't interpret a surplus argument as next command. If a line is invalid for whatever reason (bad number of arguments as above or unknown command), you can then decide indiviually what you want to do (just ignore the line or abort processing entirely). So:

std::string line;
while(std::getline(std::cin, line))
{
    // parse the string; if line is invalid, appropriate error handling
    // (ignoring the line, exiting from loop, ...)
}
if(!std::cin.eof())
{
    // some error occured, print error message!
}