сортировка вектора пары эффективным способом

Я пытаюсь решить проблему сортировки, но всегда получаю 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 ответ
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::):

  1. Пробел теперь представляет собой отдельный символ, а не строку. Теоретически это должно быть намного быстрее, потому что один символ – это один символ … в то время как строка требует чтения нескольких символов с помощью цикла и условного выражения (для поиска NUL). (На самом деле компилятор, вероятно, все равно оптимизирует это за вас.)
  2. Не использовать 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");
}

Затем вам просто понадобится еще пара тестов, чтобы убедиться, что сортировка дает правильный результат, и что вы распечатываете правильный результат для медианы. После этого вы можете добавить больше тестов с другими тестовыми данными для проверки различных потенциальных проблем. Возьмите за привычку тестировать свой код. Вы даже можете найти преимущества с этой самой программой….

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *