Вначале вопрос дизайна: обычно ключ передается только функции и вычисляется хеш внутри. Ваш вариант позволяет пользователю размещать элементы в любом месте хеш-таблицы (используя неверные хеш-значения), чтобы пользователь мог легко разбить его.
Так е. г. 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);
// ...
}
Если вообще, хеш-функцию можно параметризировать, но тогда вы напишите отдельный класс для (обтекание вектора векторов) и предоставите хеш-функцию в конструкторе, чтобы пользователь не мог произвольно обмениваться ею (и снова прерывать хеш-таблица). Класс получит дополнительные преимущества, самое важное: лучшая инкапсуляция (скрытие вектора, поэтому пользователь не сможет изменить его с помощью собственного интерфейса вектора):
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
};
Я не уверен на 100%, насколько на самом деле эффективен std::function, поэтому для высокопроизводительного кода предпочтительнее использовать хеш-функцию h1 напрямую (без реализации конструктора, как показано выше).
Подходит к оптимизации:
Для хэш-ключа я бы предпочел значение без знака: отрицательные индексы в любом случае не имеют смысла, так зачем вообще их разрешать? long long (подписанный или неподписанный) может быть плохим выбором, если система тестирования является 32-битной системой (может быть маловероятно, но все же ...). size_t охватывает обе проблемы одновременно: он не подписан, и его размер выбирается соответствующим образом для данной системы (если интересует подробности: фактически отрегулирован по размеру шины, но в современных системах это равно размеру регистра, что это то, что нам нужно). Выберите тип pow, чтобы быть таким же.
deleteAll реализован неэффективно: с каждым стираемым элементом вы перемещаете все последующие элементы на одну позицию вперед. Если вы удаляете несколько элементов, вы делаете это несколько раз, поэтому один отдельный элемент может перемещаться несколько раз. Лучше:
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());
Это будет перемещать каждый элемент не более одного раза, стирая все избыточные элементы за один раз. Начните с окончательного удаления (которое вы должны сделать явным образом), это более или менее то же, что делают std::remove и std::remove_if из библиотеки алгоритмов . Вам разрешено использовать это? Тогда ваш код может выглядеть так:
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());
и вы получаете прибыль от уже высоко оптимизированного алгоритма.
Небольшой выигрыш в производительности, но все же: вы можете сэкономить инициализацию, присваивание и условную ветвь переменной (последняя может быть относительно дорогой операцией в некоторых системах) в пределах put, если вы просто вернетесь, если найден элемент:
//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);
Опять же, с библиотекой алгоритмов:
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);
}
Тогда менее 100000 операций не означает, что для каждой операции потребуется отдельная пара ключ / значение. Мы можем ожидать, что ключи будут добавлены, удалены, повторно добавлены, ..., поэтому вам, скорее всего, не придется справляться с 100000 различными значениями. Я бы предположил, что ваша карта слишком велика (имейте в виду, что она также требует инициализации 100000 векторов). Я бы предположил, что гораздо меньшего уже должно хватить (возможно, 1009 или 10007? Возможно, вам придется немного поэкспериментировать ...).
Сохранение отсортированных внутренних векторов может также повысить производительность:
put: Вы можете использовать двоичный поиск, чтобы найти два элемента, между которыми должен быть вставлен новый элемент (если один из этих двух равен заданному, конечно, без вставки) delete: используйте бинарный поиск, чтобы найти удаляемый элемент. deleteAll: Найти верхнюю и нижнюю границы удаляемых элементов и стереть сразу весь диапазон. get: найдите нижнюю и верхнюю границу, как для deleteAll, расстояние между ними (количество элементов) является простым вычитанием, и вы можете распечатать текст напрямую (вместо того, чтобы сначала построить длинную строку). Какой из выводов напрямую или создания строки действительно более эффективен, следует выяснить, так как вывод напрямую связан с несколькими системными вызовами, что в итоге может снова стоить ранее достигнутой производительности ...
Учитывая ваш цикл ввода:
Проверка для eof() (только) является критической ! Если в файле есть ошибка, вы окажетесь в бесконечном цикле, так как бит сбоя установлен, operator>> фактически вообще ничего не прочитает, и вы никогда не достигнете конца файл. Это даже может быть причиной неудачного 20-го теста.
Дополнительно: у вас есть ввод на основе строки (каждая команда в отдельной строке), поэтому чтение сразу всей строки и только после этого синтаксический анализ избавят вас от некоторых системных вызовов. Если какой-либо аргумент отсутствует, вы обнаружите его правильно вместо того, чтобы (незаконно) читать следующую команду (например, put) в качестве аргумента, аналогично вы не будете интерпретировать избыточный аргумент как следующую команду. Если по какой-либо причине строка недопустима (неверное количество аргументов, как указано выше, или неизвестная команда), вы можете индивидуально решить, что вы хотите сделать (просто проигнорируйте строку или полностью прервите обработку). Итак:
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!
}