1

Всем привет. Сделал маленькую прогу по добавлению и проверке синонимов для курса Яндекса. Как раз контейнер set прохожу. Задание тут Ссылка на задание курса если вдруг важно.

#include <iostream>
#include <string>
#include <set>
using namespace std;
void Count_sin(const set<set<string>>& sinon, const string& word) {
    int key = 0;
    for (const auto& z : sinon) { //роемся в "большом" множестве
        for (const auto& y : z) { //и в каждом слове "маленького" множества
            if (y == word) { //ищем совпадение со словом, и если нашли
                key++; //плюсанули себе за то что нашли
            }
        }
    }
    cout << key << endl; //выводим сколько раз плюсанули себе 
}
void Check_sin(const set<set<string>>& sinon, const string& word1, const string& word2) {
    set<string> sett = { word1, word2 }; //создаем из слов "маленькое" множество
    int key = 0; //объявили ключ для проверки наличия синонима
    for (const auto& z : sinon) { //в каждом множестве "большого" множества
        if (z == sett) { //ищем совпадение
            cout << "YES" << endl; //и если нашли, то пишем ДА
            key++; //плюсанули себе
        }
    }
    if (key == 0) { //если не плюсанули себе, то
        cout << "NO" << endl; //пишем НЕТ
    }
}
int main() {
    int i;
    string comand, word1, word2;
    set<set<string>> sinon; //создадим "большое" множество "маленьких" множеств
    cin >> i; //количество строк запросов
    for (i; i > 0; i--) {
        cin >> comand; //считываем команду
        if (comand == "ADD") { //проверяем какая команда пришла
            cin >> word1 >> word2; //считываем слова
            sinon.insert({ word1, word2 }); //вставляем слова в "большое" множество
        }
        else if (comand == "COUNT") {
            string word;
            cin >> word; //считываем слово
            Count_sin(sinon, word); //узнаем сколько синонимов у слова
        }
        else if (comand == "CHECK") {
            string word1, word2;
            cin >> word1 >> word2; //считали слова
            Check_sin(sinon, word1, word2); //проверяем, есть ли такая пара
        }
    }
    return 0;
}

На одном из его тестов прога выполняется дольше 1 секунды. (Failed case #8/16: time limit exceeded (Time used: 1.99/1.00)) Нужно не более 1 секунды. На простых тестах отрабатывает быстро (менее 0,04 сек). Где может быть потеря времени, и почему?

Новый код:

#include <iostream>
#include <string>
#include <set>
using namespace std;        
int main() {
    int i, key;
    string comand, word1, word2, word;
    set<set<string>> sinon;
    cin >> i;
    for (i; i > 0; i--) {
        cin >> comand;
        if (comand == "ADD") {
            cin >> word1 >> word2;
            sinon.insert({ word1, word2 });
        }
        else if (comand == "COUNT") {
            cin >> word;
            key = 0;
            for (auto& z : sinon) { //ссылка есть
                key += z.count(word); //и функция
            }
            cout << key << endl;
        }
        else if (comand == "CHECK") {
            cin >> word1 >> word2;
            if (sinon.count({word1, word2})){ //и тут функция
                cout << "YES" << endl;
            }
            else cout << "NO" << endl;
        }
    }
    return 0;
}    

Все равно долго считает. Уже не знаю что делать.

Само задание...

Два слова называются синонимами друг друга, если они имеют похожие значения. Реализуйте следующие операции над словарём синонимов: ADD word1 word2 — добавить в словарь пару синонимов (word1, word2). COUNT word — узнать количество синонимов слова word. CHECK word1 word2 — проверить, являются ли слова word1 и word2 синонимами. Слова word1 и word2 считаются синонимами, если среди запросов ADD был хотя бы один запрос ADD word1 word2 или ADD word2 word1.

Формат ввода

Сначала вводится количество запросов Q, затем Q строк с описаниями запросов. Гарантируется, что в каждом запросе CHECK и ADD слова word1 и word2 различны. Все слова состоят лишь из латинских букв, цифр и символов подчёркивания.

Формат вывода

Для каждого запроса в соответствующей строке выведите ответ на него: В ответ на запрос COUNT word выведите единственное целое число — количество синонимов слова word. В ответ на запрос CHECK word1 word2 выведите строку YES, если word1 и word2 являются синонимами, и NO в противном случае.

Итоговое решение

#include <iostream>
#include <string>
#include <set>
#include <map>
using namespace std;
using sorted_pair = pair<string, string>;
sorted_pair make_sorted_pair(const std::string& word1, const string& word2) {
    return (word1 <= word2) ? make_pair(word1, word2) : make_pair(word2, word1);
}
bool check(const set<sorted_pair>& synonyms, const string& word1, const string& word2) {
    return synonyms.count(make_sorted_pair(word1, word2)) != 0;
}
void add(set<sorted_pair>& synonyms, map<string, unsigned>& synonyms_count, const string& word1, const string& word2) {
    if (check(synonyms, word1, word2)) return;  // синоним уже есть
    ++synonyms_count[word1];
    ++synonyms_count[word2];
    synonyms.insert(make_sorted_pair(word1, word2));

}
int main() {
    set<sorted_pair> synonyms;  // пары синонимов  
    map<string, unsigned> synonyms_count;  // количество синонимов
    int i;
    string comand, word1, word2;
    cin >> i; //количество запросов
    for (i; i > 0; i--) {
        cin >> comand; //считываем комманду
        if (comand == "ADD") { //проверяем какая комманда пришла
            cin >> word1 >> word2; //считываем слова
            add(synonyms, synonyms_count, word1, word2);
        }
        else if (comand == "COUNT") {
            string word;
            cin >> word; //считываем слово
            cout << synonyms_count[word] << endl;
        }
        else if (comand == "CHECK") {
            string word1, word2;
            cin >> word1 >> word2; //прочитали слова

            if (check(synonyms, word1, word2)){
                cout << "YES" << endl; //пишем Да
            }
            else cout << "NO" << endl; //иначе НЕТ
        }
    }
    return 0;
}
5
  • Да, действительно получается быстрее. Но все равно не проходит.
    – Acmades
    28 июл 2017 в 20:52
  • Чтобы посмотреть полное задание, требуется записаться на курсы :( Вы бы не могли его привести тут? Чтобы не оказалось, что мы пытаемся решить, как лучше держать микроскоп для забивания гвоздя...
    – Harry
    29 июл 2017 в 4:32
  • Добавил описание задания
    – Acmades
    31 июл 2017 в 11:47
  • Вы не пробовали использовать multimap? Как по мне, прямо просится сюда...
    – Harry
    31 июл 2017 в 11:53
  • Нет не пробовал multimap. Обошелся обычным. Решение дописал в текст вопроса. Всем спасибо. Каждому ответил.
    – Acmades
    31 июл 2017 в 23:23

3 ответа 3

2

По условию задачи Вам надо две структуры данных:

using sorted_pair = std::pair<std::string, std::string>;
std::set<sorted_pair> synonyms;  // пары синонимов  
std::map<std::string, unsigned> synonyms_count;  // количество синонимов

Проверка синонима - это

sorted_pair make_sorted_pair(const std::string& word1, const std::string& word2) {
  return (word1 <= word2) ? std::make_pair(word1, word2) : std::make_pair(word2, word1);
}

bool check(const std::string& word1, const std::string& word2) {
  return synonyms.count(make_sorted_pair(word1, word2)) != 0;
}

Добавление:

void add(const std::string& word1, const std::string& word2) {
  auto r = synonyms.insert(make_sorted_pair(word1, word2));
  if (r.second) return;  // синоним уже есть
  ++synonyms_count[word1];
  ++synonyms_count[word2];
}

И количество - это просто synonyms_count[word].


Если строки невероятно длинны, то в synonyms надо хранить не сами строки, а указатели на элементы synonyms_count. Элементы set и map не перемещаются при добавлении других элементов, значит не перемещаются и сами указатели.

using map = std::map<std::string, unsigned>;
using sorted_pair = std::pair<map::value_type*, map::value_type*>;
map synonyms_count;
std::set<sorted_pair> synonyms;
void add(const std::string& word1, const std::string& word2) {
  auto iter1 = synonyms_count.find(word1);
  auto iter2 = synonyms_count.find(word2);
  if (iter1 == synonyms_count.end()) iter1 = synonyms_count.emplace(word1, 0).first;
  if (iter2 == synonyms_count.end()) iter2 = synonyms_count.emplace(word2, 0).first;

  auto r = synonyms.insert(make_sorted_pair(&*iter1, &*iter2));
  if (r.second) return;  // синоним уже есть
  ++iter1->second;
  ++iter2->second;
}
1
  • Спасибо за помощь. Решение немного изменил, но суть вы правильно подсказали. Самая ошибка моя была , что пытался массив массивов перебрать. Особо тяжко проходил запрос COUNT. Самое верное решение - разделить на map и set. Тогда не нужно перебирать всё и поиск быстрее происходит. Плюсану чуть позже пройдет когда репутацию сделаю.
    – Acmades
    31 июл 2017 в 23:32
2

Используйте функции-члены set, а не циклы для поиска. Ваши циклы ищут совпадение за линейное время, тогда как встроенные средства set будут делать это за логарифм.

1
  • Самый простой вариант для проверки - sinon.count(sett) > 0;. Для ускорения можно ещё unordered_set использовать
    – int3
    28 июл 2017 в 18:58
1

Быстрее, чем за линию обойти все set не получится(тебе нужно посмотреть на каждый). Попробуй for (auto & z : sinon). Без ссылки каждое z будет копироваться, а на это будет уходить доп время.


UPD: Попробуй выводить через printf. cout содержит много разных проверок, поэтому работает медленнее. Также, вместо i--(аналогично для инкремента) лучше использовать --i(i-- создает новую переменную и возвращает ее, а --i уменьшает собственное значение и его же возвращает).

3
  • Попробовал, не дало эффекта. Чего же я не понимаю?
    – Acmades
    29 июл 2017 в 2:23
  • @Acmades не зная условий задачи, нельзя точно сказать как лучше оптимизировать. По ссылке выше требует регистрации. Увольте. :) 29 июл 2017 в 17:29
  • За подсказку с инкрементом отдельное спасибо.
    – Acmades
    31 июл 2017 в 23:34

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.