Я пытаюсь решить проблему сортировки, но всегда получаю TLE (Time Limit Exceeded / 1s), так что … можете ли вы предложить более эффективный способ решения этой проблемы? (я не могу связать упражнение, потому что оно находится на закрытом сервере)
код считывает количество тестов т , <интервал, строка> пары затем сортируются по целое число в порядке возрастания и печатает медиана
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char *argv[]) {
vector< pair <int,string> > median;
int t; cin >> t;
int num; string name;
for(int i=0;i<t;i++) {
cin>>name; cin>>num;
median.push_back( make_pair(num,name));
}
sort(median.begin(), median.end());
if(t%2!=0){
cout << median[t/2].second << " " << median[t/2+1].first << endl;
}else{
cout << median[t/2-1].second << " " << median[t/2+1].first << endl;
cout << median[t/2].second << " " << median[t/2+1].first << endl;
}
}
Вход:
Gilbert 35
Anna 35
Anna 15
Mary 15
Joseph 40
выход:
Anna 35
1 ответ
Я не занимаюсь программированием, поэтому мой обзор будет больше с точки зрения написания достойного C ++, чем с точки зрения мышления, связанного с программированием (которое, по моему скромному мнению, поощряет ужасные методы кодирования). Тем не менее, если вам нужна производительность, я могу дать вам несколько советов, как добиться значительного увеличения скорости.
Итак, приступим.
#include <bits/stdc++.h>
Я слышал, что это стандартная практика в кругах по программированию. Тем не менее, в реальной жизни это ужасная практика. Вместо этого просмотрите все компоненты стандартной библиотеки, которые вы используете, и включите для них заголовки. В вашем случае вы используете cin/cout, векторы, строки, пары и функция сортировки, поэтому вам понадобятся их заголовки. Включая Только эти заголовки должны заметно ускорить компиляцию, но я не знаю, считается ли время компиляции общим временем, поэтому я не знаю, насколько это поможет.
using namespace std;
Никогда не делайте этого, даже если вы занимаетесь программированием. Это просто ужасная привычка, которая со временем укусит вас за задницу. Просто положи std:: где нужно. Просто привыкните к этому.
int main(int argc, char *argv[]) {
Поскольку вы на самом деле не читаете командную строку, вы можете просто использовать более простую форму main().
Теперь вы упаковали всю свою программу в main(). Это нормально для этой очень тривиальной программы, но вы действительно должны иметь привычку писать лучший код. В конце концов, разве не для этого нужны задачи программирования?
Разбейте программу на логические шаги и поместите каждый важный шаг в отдельную функцию. Это ничего не стоит; даже самый базовый уровень оптимизации устранит все накладные расходы (и все, что не стоит устранять).
Первый шаг — прочитать количество пар в наборе данных… так что это должна быть функция с именем read_dataset_size(), или что-то вроде того. Это могло выглядеть примерно так:
auto read_dataset_size() -> int;
Или, что еще лучше, в качестве параметра возьмите входной поток:
auto read_dataset_size(std::istream&) -> int;
Почему ты бы так поступил? Потому что это упрощает тестирование функции. Вам следует всегда программа с учетом тестирования, даже для такого нестандартного кода, как этот. Потому что, если что-то не работает — а мы все совершаем глупые ошибки — вы хотите иметь возможность проводить тесты, чтобы выяснить, в чем проблема. С помощью функции, написанной, как указано выше, вы можете читать ввод из файла или даже непосредственно из памяти и смотреть, получите ли вы ожидаемый результат.
Итак, реорганизованный таким образом read_dataset_size() функция выглядит так:
auto read_dataset_size(std::istream& in) -> int
{
int t; in >> t;
return t;
}
(Это просто ваш код в точности так, как вы его написали, за исключением того, что я заменил cin с in. И, конечно же, добавлен оператор возврата.)
Вы никогда не должны писать два оператора в одной строке. Пространство ничего не стоит, но возможность четко читать код — это разница между наличием глупых скрытых ошибок или их отсутствием. Так:
auto read_dataset_size(std::istream& in) -> int
{
int t;
in >> t;
return t;
}
Еще лучше было бы дать переменным четкие имена:
auto read_dataset_size(std::istream& in) -> int
{
int size;
in >> size;
return size;
}
Обычно вы выполняете проверку ошибок, чтобы убедиться, что вы действительно читаете правильный номер и все такое … но ладно, я понимаю, что это просто код вызова. Так что пропустим проверку ошибок.
Для этого достаточно.
Ваша следующая функция должна выглядеть примерно так read_data_pairs() или что-то. Это должно выглядеть примерно так:
auto read_data_pairs(std::istream&, int) -> std::vector<std::pair<int, std::string>>;
И с рефакторингом вашего кода:
auto read_data_pairs(std::istream& in, int size) -> std::vector<std::pair<int, std::string>>
{
std::vector< std::pair <int,std::string> > median;
int num; std::string name;
for(int i=0;i<size;i++) {
in>>name; in>>num;
median.push_back( std::make_pair(num,name));
}
return median;
}
(Обратите внимание, что это именно ваш код с std::добавлено, cin заменен на in, и t заменен на size, и, конечно же, добавлен оператор return.)
Хорошо, а теперь поговорим о производительности.
Вот в чем проблема: vector автоматически изменяет размер, чтобы вместить больше данных. Когда это произойдет, он должен выделить новый кусок памяти (обычно в два раза больше существующей емкости), а затем скопировать все старые данные в новую память. Если в векторе 1000 пар, то вектор должен выделить место для 2000 пар, а затем сделать 1000 копий (технически, ходов). В современном C ++ все это происходит очень быстро… но все равно не бесплатно; есть еще цена. И если у тебя есть миллионы пар….
Хуже того, это, вероятно, будет происходить много-много раз, когда вы читаете данные. Ваш вектор будет пустым, а затем вам нужно будет выделить место для пары элементов. Вы прочитаете пару элементов, а затем снова закончите пространство … поэтому вектору придется выделить новый блок памяти и скопировать все заново. Теперь вы прочтете еще несколько элементов … но вскоре снова закончится место. Таким образом, вектор придется перераспределить и скопировать опять таки. И ему придется повторять это снова и снова. По мере того, как количество элементов становится огромным, все их выделение и копирование быстро накапливаются.
Вот ключ к решению этой проблемы. Вы уже знаете размер входных данных. Таким образом, вы можете просто заранее выделить все необходимое пространство и избежать необходимости в этом перераспределении и копировании. Технически правильный способ сделать это:
auto read_data_pairs(std::istream& in, int size) -> std::vector<std::pair<int, std::string>>
{
std::vector< std::pair <int,std::string> > median; // median probably
// isn't a great name
// for this variable,
// because it isn't
// the median... it's
// all the input data
//
// maybe call it
// "pairs" instead?
median.reserve(size); // this is the magical line that will probably fix
// all your performance problems
int num;
std::string name;
for(int i=0; i < size; ++i)
{
in >> name;
in >> num;
median.push_back( std::make_pair(num,name));
}
return median;
}
Одна только эта строка, вероятно, исправит ваши ошибки тайм-аута.
Но мы можем сделать даже лучше.
Несмотря на то, что мы резервируем всю память, которая нам понадобится, мы по-прежнему помещаем элементы в вектор. Теперь это будет очень быстро… но, опять же, не бесплатно.
Поэтому вместо того, чтобы просто зарезервировать место, а затем снова и снова вставлять элементы в вектор … почему бы не создать элементы сразу, а затем прочитать данные напрямую в них? Никаких дополнительных копий не требуется.
Это технически не хороший практика в целом … но это действенный прием для повышения эффективности. А эффективность — это то, к чему вы стремитесь.
Так:
auto read_data_pairs(std::istream& in, int size) -> std::vector<std::pair<int, std::string>>
{
std::vector<std::pair<int,std::string>> median;
median.resize(size); // note: reSIZE, not reSERVE
// this will fill the entire vector with the
// right number of pairs in a single shot
// note: no more need for temporaries to read input!
// we'll be reading *directly* into the proper place
// note: we can use the much safer range-for loop now
for (auto&& element : median)
{
in >> element.first;
in >> element.second;
}
return median;
}
Думаю, это настолько быстро, насколько это возможно.
Сортировка — это просто вызов std::sort()… Мы мало что можем сделать, чтобы это улучшить или ускорить.
Теперь способ печати вывода немного странный. Почему вы делаете median[t/2].second а потом median[t/2+1].first? Вы уверены, что это правильно? Вы тестировали его с большим количеством данных, чем показано? (Серьезно, ПРОВЕРЬТЕ КОД !!! Это самое главное, что отличает дерьмовых программистов от хороших. Вы должны протестировать свой код с несколькими наборами данных, включая крайние случаи, которые могут вызвать проблемы (например, набор данных с одним элементом).)
У меня есть подозрение, что у вас есть ошибка, но я не могу быть уверен, потому что вы не указали фактические требования к программе. Поэтому я просто предполагаю, что ваш код не сломан (но я думаю, что это так!).
Теперь вывод может быть немного быстрее. Вместо:
cout << median[t/2].second << " " << median[t/2+1].first << endl;
Вы могли сделать:
std::cout << median[t / 2].second << ' ' << median[(t / 2) + 1].first << 'n';
Я изменил две вещи (кроме интервала, чтобы сделать его более читабельным, и добавления символа std::):
- Пробел теперь представляет собой отдельный символ, а не строку. Теоретически это должно быть намного быстрее, потому что один символ — это один символ … в то время как строка требует чтения нескольких символов с помощью цикла и условного выражения (для поиска
NUL). (На самом деле компилятор, вероятно, все равно оптимизирует это за вас.) - Не использовать
std::endl.std::endlпечатает новую строку … и затем сбрасывает поток, который дорогой. В любом случае поток будет сброшен автоматически, поэтому нет смысла платить за него несколько раз.
Я могу придумать еще один последний трюк, который может немного увеличить скорость: std::ios::sync_with_stdio(false);. Это высокоуровневый трюк, но за него приходится платить: если вы сделаете это, вы не можете использовать ни один из C stdio библиотека. Это значит нет printf(), нет fopen(), ничего подобного. Что происходит, так это то, что по умолчанию потоки ввода-вывода C ++ будут синхронизироваться с C stdio потоки. Это удобное средство, позволяющее смешивать std::cout и printf(). НО! Это дорого обходится. Замедляется std::cin и std::cout а МНОГО. Если вы никогда не используете C stdio вещи, то вы можете выключить эту синхронизацию и получить огромный повышение производительности. Это может иметь значение для вас, а может и нет. В любом случае, просто придерживайся std::ios::sync_with_stdio(false); сразу после начала main().
Ладно, в общем, я думаю, что причина, по которой вы получаете тайм-ауты, связана с тем, как вы читаете ввод. К нет предварительно выделяя вектор, он вынужден постоянно перераспределять и копировать (перемещать) все его содержимое, снова и снова и снова. Просто предварительно выделите вектор с помощью reserve(), вы избавите себя от всех этих потерь, выполнив одно-единственное выделение и полностью исключив копирование (перемещение). Более того, вы можете просто предварительно изменить размер вектора, а затем прочитать данные. напрямую в его элементы, так что теперь вам даже не нужно читать во временные, а затем копировать в вектор.
Добавление std::ios::sync_with_stdio(false); май тоже помогите.
Но самое главное: ПРОВЕРЬТЕ СВОЙ КОД !!! я считать у вас есть ошибка. Вы говорите, что ваш код работает, поэтому я предполагаю, что вы знаете, что делаете … но я все еще скептически отношусь к этому. ПРОВЕРЬТЕ СВОЙ КОД !!! Убедитесь сами, действительно ли это работает так, как вы думаете. Вам просто нужны простые тесты, подобные этому (используя Catch2 тестовая среда):
TEST_CASE("dataset size is read correctly")
{
auto const test_data = R"(
3
1 Alice
2 Bob
3 Carol
)";
auto iss = std::istringstream{test_data};
CHECK(read_dataset_size(iss) == 3);
}
TEST_CASE("simple data is read correctly")
{
auto const test_data = R"(
3
1 Alice
2 Bob
3 Carol
)";
auto iss = std::istringstream{test_data};
// just assume this works and throw the result away, because it is tested
// in the other test case
[[maybe_unusued]] auto const data_size = read_dataset_size(iss);
auto const data = read_data_pairs(iss, 3);
CHECK(data.size() == 3);
CHECK(data.at(0) == "Alice");
CHECK(data.at(1) == "Bob");
CHECK(data.at(2) == "Carol");
}
Затем вам просто понадобится еще пара тестов, чтобы убедиться, что сортировка дает правильный результат, и что вы распечатываете правильный результат для медианы. После этого вы можете добавить больше тестов с другими тестовыми данными для проверки различных потенциальных проблем. Возьмите за привычку тестировать свой код. Вы даже можете найти преимущества с этой самой программой….